[math-fun] EXACT matrix factorizations
The numerical linear algebra folks have ruined the term 'factorization', because essentially all of their work involves _approximations_ to exact factors. However, if one is interested in _exact_ matrix factorization -- e.g., matrices of integers -- what is known? I wrote a simple Maxima function that removes gcd's of rows & columns, but I was wondering if I (easily) could go any further. Clearly, there are lots of questions: e.g., even for square nxn matrices, the factors might be nxm & mxn. Is this allowed? Does it help? One can always use (integer) permutation matrices to reorder rows & columns, so we won't worry about that, unless we can come up with an appropriate sorting rule. I'm sure there must be a literature on this problem, but I did a quick Google search & couldn't find the appropriate terminology.
That's related to several questions that have interested me for decades. Here's a simple version: choose your favorite matrix ring R, e.g. real matrices with entries that are 0 or 1. What is a(n) := number of nxn matrices in R that have a square root in R? About the question of whether non-square factors help, of course they sometimes do. One situation where they do is when you are given an nxn Gram matrix A for a lattice, with integer entries, and you want to know if there is an mxn matrix B with integer entries such that B transpose(B) = A. There is a lot about this in a paper I wrote with John Conway: Low-Dimensional Lattices V: Integral Coordinates for Integral Lattices, J. H. Conway and N. J. A. Sloane, Proc. Royal Soc. London, Series A, 426 (1989), pp. 211-232. (available as #151 on my pub. list on my home page, see below) If n = 1, the answer is you can do it with m = 4: this is exactly Jacobi's 4-square theorem! Neil On Tue, May 7, 2013 at 12:38 PM, Henry Baker <hbaker1@pipeline.com> wrote:
The numerical linear algebra folks have ruined the term 'factorization', because essentially all of their work involves _approximations_ to exact factors.
However, if one is interested in _exact_ matrix factorization -- e.g., matrices of integers -- what is known?
I wrote a simple Maxima function that removes gcd's of rows & columns, but I was wondering if I (easily) could go any further.
Clearly, there are lots of questions: e.g., even for square nxn matrices, the factors might be nxm & mxn. Is this allowed? Does it help?
One can always use (integer) permutation matrices to reorder rows & columns, so we won't worry about that, unless we can come up with an appropriate sorting rule.
I'm sure there must be a literature on this problem, but I did a quick Google search & couldn't find the appropriate terminology.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On 07/05/2013 18:08, Neil Sloane wrote:
That's related to several questions that have interested me for decades. Here's a simple version: choose your favorite matrix ring R, e.g. real matrices with entries that are 0 or 1. What is a(n) := number of nxn matrices in R that have a square root in R?
That doesn't look like a ring. Are you intending the entries to be taken mod 2, or are you using (max,min) instead of (+,*) or something like that, or what? -- g
Brute force gives the following for 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. On Tue, May 7, 2013 at 1:08 PM, Neil Sloane <njasloane@gmail.com> wrote:
That's related to several questions that have interested me for decades. Here's a simple version: choose your favorite matrix ring R, e.g. real matrices with entries that are 0 or 1. What is a(n) := number of nxn matrices in R that have a square root in R?
Edwin, Thanks, I will enter that sequence this afternoon. I was wrong of course in calling it a ring (the result of too many years working in the "mod 2" world - and there the same sequence is also of interest but is probably in the OEIS already: number of nxn matrices over GF(2) that are squares). It is just a set. On Tue, May 7, 2013 at 2:17 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
Brute force gives the following for 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.
On Tue, May 7, 2013 at 1:08 PM, Neil Sloane <njasloane@gmail.com> wrote:
That's related to several questions that have interested me for decades. Here's a simple version: choose your favorite matrix ring R, e.g. real matrices with entries that are 0 or 1. What is a(n) := number of nxn matrices in R that have a square root in R?
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
Sorry, Edwin did do the GF(2) version, which is now A225371 (and could use more terms). The real-valued (0,1} version - where it is a set not a ring - may or may not be in the OEIS. On Tue, May 7, 2013 at 2:37 PM, Neil Sloane <njasloane@gmail.com> wrote:
Edwin, Thanks, I will enter that sequence this afternoon.
I was wrong of course in calling it a ring (the result of too many years working in the "mod 2" world - and there the same sequence is also of interest but is probably in the OEIS already: number of nxn matrices over GF(2) that are squares). It is just a set.
On Tue, May 7, 2013 at 2:17 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
Brute force gives the following for 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.
On Tue, May 7, 2013 at 1:08 PM, Neil Sloane <njasloane@gmail.com> wrote:
That's related to several questions that have interested me for decades. Here's a simple version: choose your favorite matrix ring R, e.g. real matrices with entries that are 0 or 1. What is a(n) := number of nxn matrices in R that have a square root in R?
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
-- Dear Friends, I have now retired from AT&T. New coordinates:
Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
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
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>
What are the conditions for a ring of matrices over a field to have Jordan form? I know the theorem over the complexes and imagine that algebraic completeness of the field is at least sufficient, if not necessary. --Dan On 2013-05-22, at 2:12 PM, Victor Miller wrote: ----- . . . . . . I look at all possible Jordan canonical forms for an n by n matrix, . . . -----
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>
Hmmm... I wasn't aware of Hermite normal forms. Smith Normal Form also looks interesting. Thanks! At 10:49 AM 5/7/2013, Veit Elser wrote:
On May 7, 2013, at 12:38 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm sure there must be a literature on this problem, but I did a quick Google search & couldn't find the appropriate terminology.
Try "Hermite normal form".
-Veit
participants (8)
-
Dan Asimov -
Gareth McCaughan -
Giovanni Resta -
Henry Baker -
Neil Sloane -
Veit Elser -
Victor Miller -
W. Edwin Clark