[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.
Victor
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