Re: [math-fun] classes of sq matrices closed under matrix multiply ?
Thanks, Victor! The article looks quite interesting, but also quite tough sledding... At the topmost level, are there any classes of matrices other than upper triangular, lower triangular, both/diagonal, and/or block versions of same, that preserve the overall pattern of zeros? From a directed graph adjacency matrix perspective, triangular matrices are partial orders forced into a linear order; block matrices have subsets of vertices with cyclic orders (equivalence classes). It seems to me that these might exhaust the classes of matrices with patterns of zeros. At 06:25 AM 9/7/2017, Victor Miller wrote:
Henry, This may be more than you bargained for, but this is a well-studied problem. To make your question more precise, you can ask for algebraic subgroups of matrices -- i.e. subsets of matrices that are the set of solutions to a bunch of polynomials in their coordinates (think determinant = 1, for example). These polynomials are said to "cut out" the group, The following paper surveys the classification of such: https://www.dpmms.cam.ac.uk/~nd332/alg_gps.pdf
Besides the ones that you mentioned, you can also have the set of matrices that preserve a quadratic form: x --> x^T Q x. So you'd want all matrices, A, such that A^T Q A = Q. If A is the identity you get the orthogonal group, If A has dimension 2n and has n +1, and n -1 on the diagonal and 0 everywhere else, you get the Symplectic group.
The nice thing about algebraic groups, is that you can restrict their coordinates to lie in a field which is a subfield of the coefficients used to define the polynomials that cut out the group, you get a subgroup.
Victor
On Wed, Sep 6, 2017 at 9:12 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Is there an encyclopedia/catalog somewhere of classes of square matrices closed under matrix multiply?
I'm interested in generic classes -- e.g., things that work for arbitrary n, e.g., diagonal matrices, orthogonal matrices, upper triangular, lower triangular, etc.
As far as patterns of zeros, I don't know. That sounds like the kind of thing that Dick Stanley must have studied. Victor On Thu, Sep 7, 2017 at 10:53 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Thanks, Victor!
The article looks quite interesting, but also quite tough sledding...
At the topmost level, are there any classes of matrices other than upper triangular, lower triangular, both/diagonal, and/or block versions of same, that preserve the overall pattern of zeros?
From a directed graph adjacency matrix perspective, triangular matrices are partial orders forced into a linear order; block matrices have subsets of vertices with cyclic orders (equivalence classes).
It seems to me that these might exhaust the classes of matrices with patterns of zeros.
At 06:25 AM 9/7/2017, Victor Miller wrote:
Henry, This may be more than you bargained for, but this is a well-studied problem. To make your question more precise, you can ask for algebraic subgroups of matrices -- i.e. subsets of matrices that are the set of solutions to a bunch of polynomials in their coordinates (think determinant = 1, for example). These polynomials are said to "cut out" the group, The following paper surveys the classification of such: https://www.dpmms.cam.ac.uk/~nd332/alg_gps.pdf
Besides the ones that you mentioned, you can also have the set of matrices that preserve a quadratic form: x --> x^T Q x. So you'd want all matrices, A, such that A^T Q A = Q. If A is the identity you get the orthogonal group, If A has dimension 2n and has n +1, and n -1 on the diagonal and 0 everywhere else, you get the Symplectic group.
The nice thing about algebraic groups, is that you can restrict their coordinates to lie in a field which is a subfield of the coefficients used to define the polynomials that cut out the group, you get a subgroup.
Victor
On Wed, Sep 6, 2017 at 9:12 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Is there an encyclopedia/catalog somewhere of classes of square matrices closed under matrix multiply?
I'm interested in generic classes -- e.g., things that work for arbitrary n, e.g., diagonal matrices, orthogonal matrices, upper triangular, lower triangular, etc.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A stronger condition is that the matrices form a group. For example, consider the largest group of matrices (of a particular size) where all matrix elements are non-negative. -Veit
On Sep 7, 2017, at 10:53 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Thanks, Victor!
The article looks quite interesting, but also quite tough sledding...
At the topmost level, are there any classes of matrices other than upper triangular, lower triangular, both/diagonal, and/or block versions of same, that preserve the overall pattern of zeros?
From a directed graph adjacency matrix perspective, triangular matrices are partial orders forced into a linear order; block matrices have subsets of vertices with cyclic orders (equivalence classes).
It seems to me that these might exhaust the classes of matrices with patterns of zeros.
Or even a semi-group: Integer matrices whose entries are all divisible by 2 are closed under matrix multiplication, or indeed, divisible by any n, for n>=1. Also, Markov/stochastic matrices are closed under matrix multiplication. At 07:38 AM 9/8/2017, Veit Elser wrote:
A stronger condition is that the matrices form a group.
For example, consider the largest group of matrices (of a particular size) where all matrix elements are non-negative.
-Veit
On Sep 7, 2017, at 10:53 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Thanks, Victor!
The article looks quite interesting, but also quite tough sledding...
At the topmost level, are there any classes of matrices other than upper triangular, lower triangular, both/diagonal, and/or block versions of same, that preserve the overall pattern of zeros?
From a directed graph adjacency matrix perspective, triangular matrices are partial orders forced into a linear order; block matrices have subsets of vertices with cyclic orders (equivalence classes).
It seems to me that these might exhaust the classes of matrices with patterns of zeros.
These "Pattern algebras" or "incidence algebras" as I recall can be constructed by taking any finite poset (P,<=) and then considering the algebra spanned by the matrix units e_{i,j} where i <= j Barry Mitchell (of category fame) also studied these in a slightly more general setting. He called this homological tic tac toe since he was interested (as was I at one time) in relating the "global dimension" of such an algebra to properties of the corresponding poset. If you play around a bit with matrix units semigroups (that is set of matrix units, e_{i,j} that are closed under multiplication) you will quickly convince yourself of the plethora of such "pattern algebra". Back to Victor's suggestion concerning "algebraic" groups much work has also been done on "algebraic" semigroups (algebraic varieties of matrices closed under multip.)--mostly as I recall by Mohan Putcha. Before him I played around with "affine semigroups" which are linear varieties of matrices closed under multiplication. Of course most "classical" groups are most easily described as sets of matrices that are closed under multiplication (and inversion). Note also that any finite semigroup can be faithfully represented as a semigroup of matrices--as can every finite group. Generally restricting semigroups to semigroups of matrices doesn't buy very much without further hypotheses. On 9/7/17, Henry Baker <hbaker1@pipeline.com> wrote:
Thanks, Victor!
The article looks quite interesting, but also quite tough sledding...
At the topmost level, are there any classes of matrices other than upper triangular, lower triangular, both/diagonal, and/or block versions of same, that preserve the overall pattern of zeros?
From a directed graph adjacency matrix perspective, triangular matrices are partial orders forced into a linear order; block matrices have subsets of vertices with cyclic orders (equivalence classes).
It seems to me that these might exhaust the classes of matrices with patterns of zeros.
At 06:25 AM 9/7/2017, Victor Miller wrote:
Henry, This may be more than you bargained for, but this is a well-studied problem. To make your question more precise, you can ask for algebraic subgroups of matrices -- i.e. subsets of matrices that are the set of solutions to a bunch of polynomials in their coordinates (think determinant = 1, for example). These polynomials are said to "cut out" the group, The following paper surveys the classification of such: https://www.dpmms.cam.ac.uk/~nd332/alg_gps.pdf
Besides the ones that you mentioned, you can also have the set of matrices that preserve a quadratic form: x --> x^T Q x. So you'd want all matrices, A, such that A^T Q A = Q. If A is the identity you get the orthogonal group, If A has dimension 2n and has n +1, and n -1 on the diagonal and 0 everywhere else, you get the Symplectic group.
The nice thing about algebraic groups, is that you can restrict their coordinates to lie in a field which is a subfield of the coefficients used to define the polynomials that cut out the group, you get a subgroup.
Victor
On Wed, Sep 6, 2017 at 9:12 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Is there an encyclopedia/catalog somewhere of classes of square matrices closed under matrix multiply?
I'm interested in generic classes -- e.g., things that work for arbitrary n, e.g., diagonal matrices, orthogonal matrices, upper triangular, lower triangular, etc.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Henry Baker -
Veit Elser -
Victor Miller -
W. Edwin Clark