Re: [math-fun] classes of sq matrices closed under matrix multiply ?
Thanks, Edwin! It would appear that if matrix multiplication is closed in a set S of square matrices, then (M^^-1).S.M = S' is another closed set of square matrices, where M is any invertible matrix whose elements come from an extension ring of the element ring of S. Indeed, if S1, S2 are elements of S, then ((M^^-1).S1.M).((M^^-1).S2.M) = (M^^-1).S1.(M.(M^^-1)).S2.M = (M^^-1).(S1.S2).M Thus, S1,S2 should be considered equivalent. This means that there are a number of classes of matrices that are "equivalent" to upper triangular matrices, even though they aren't upper triangular themselves; ditto for other classes. "Upper triangular" -- by itself -- doesn't completely specify a unique representative of the class; other restrictions are needed. At 09:08 AM 9/10/2017, W. Edwin Clark wrote:
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.
At 01:04 PM 9/10/2017, Henry Baker wrote:
Thanks, Edwin!
It would appear that if matrix multiplication is closed in a set S of square matrices, then (M^^-1).S.M = S' is another closed set of square matrices, where M is any invertible matrix whose elements come from an extension ring of the element ring of S. Indeed, if S1, S2 are elements of S, then
((M^^-1).S1.M).((M^^-1).S2.M) = (M^^-1).S1.(M.(M^^-1)).S2.M = (M^^-1).(S1.S2).M
Thus, S1,S2 should be considered equivalent.
Typo, should be: S, S' should be considered equivalent.
This means that there are a number of classes of matrices that are "equivalent" to upper triangular matrices, even though they aren't upper triangular themselves; ditto for other classes.
"Upper triangular" -- by itself -- doesn't completely specify a unique representative of the class; other restrictions are needed.
At 09:08 AM 9/10/2017, W. Edwin Clark wrote:
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.
participants (1)
-
Henry Baker