[seqfan] Re: [math-fun] Re: EXACT matrix factorizations

Victor Miller victorsmiller at gmail.com
Thu May 23 23:07:14 CEST 2013

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.


On Wed, May 22, 2013 at 5:12 PM, Victor Miller <victorsmiller at 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 at 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 at mailman.xmission.com
>> http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>

More information about the SeqFan mailing list