I've now been able to calculate through a(30). I also calculated a sequence in which, in addition, the squared matrix must be invertible. The interesting thing is that the ratio between the two tends to 0.4306. Notice that the probability that a random n by n matrix over GF(2) is invertible tends to prod_{j=1}^{\infty} (1-2^j) which is about 0.288, so that you're a lot more likely to be a square if you're invertible. Also the proportion of the squared matrices to all matrices tends to 0.6755. All of this empirically. Victor On Wed, May 22, 2013 at 5:12 PM, Victor Miller <victorsmiller@gmail.com>wrote:
I developed a method of pushing this sequence much further. I can now calculate through a(25). The idea is the following:
whether or not B is the square of a matrix is solely a function of its conjugacy class. So I look at all possible Jordan canonical forms for an n by n matrix, and determine which ones of these can occur in the square of a matrix. After enumerating these, I calculate the cardinality of the centralizer of each, which, divided into the cardinality of the general linear group of invertible matrices, gives the number of such. In order to avoid combinatorial explosion, I actually look at multisets of such matrices, and then multiply them by the appropriate multinomial coefficient corresponding to choices of distinct (actually non-conjugate) eigenvalues of a given degree above GF(2). I also have a very hand-wavy proof that
lim log_2 (a(n))/n^2 = 1. That is the the set of matrices which aren't squares is a negligible proportion. In the process of doing this I also found two sequences which aren't in OEIS (even with superseeker).
Victor
On Wed, May 8, 2013 at 5:48 AM, Giovanni Resta <g.resta@iit.cnr.it> wrote:
a(n) = number of squares in M(n,2) =
ring of nxn matrices over GF(2), beginning with n = 1: 2,10,260,31096 which is not in the OEIS. Perhaps some interested soul can extend this.
I've added a(5) = 13711952 and in about 3.5 hours I can add a(6).
Giovanni
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>