Automorphisms of Matrices

Matrices may be regarded as defining a design with the entry of a matrix in a particular row and column defining the incidence of the row and column. The automorphism group of a matrix is the set of permutations of the rows and columns of the matrix that leave the matrix unchanged.

M ^ x: Mtrx, GrpPermElt -> Mtrx

The action of a permutation on a matrix by permuting rows and columns. If \(M\) has \(r\) rows and \(c\) columns then \(x\) must have degree \(r+c\) and fix the set \(R = \{1, \ldots, r\}\). The action of \(x\) on \(R\) gives the permutation of the rows of the matrix. The remainder of \(x\) gives the action on columns.

AutomorphismGroup(M : parameters): Mtrx -> GrpPerm

RowColours: SeqEnum[RngIntElt]                    Default: 
ColColours: SeqEnum[RngIntElt]                    Default: 
Subgroup  : GrpPerm                               Default: 
Al        : MonStgElt                             Default: "Default"

Computes the group of all permutations \(x\) such that \(M^x= M\). The method used is a backtrack search as described by J. Leon.

If \(M\) has \(r\) rows then RowColours may be set to a sequence of integers with length \(r\). This defines a partition of the rows of \(M\) where a block is the set of rows with the same number in the sequence. The group found in this case will be the subgroup of the automorphism group of \(M\) that fixes this row partition. The ColColours parameter may be used to partition the columns of the matrix.

The Subgroup parameter may be set to a known subgroup of the automorphism group. This may speed the backtrack search. The default value is the trivial subgroup.

The parameter Al is kept for backward compatibility.

IsIsomorphic(M, N: parameters): Mtrx, Mtrx -> BoolElt, GrpPermElt

LeftRowColours : SeqEnum[RngIntElt]                    Default: 
LeftColColours : SeqEnum[RngIntElt]                    Default: 
RightRowColours: SeqEnum[RngIntElt]                    Default: 
RightColColours: SeqEnum[RngIntElt]                    Default: 

Finds a permutation \(x\) such that \(M^x= N\), if such exists. If a permutation is found return values are true and the permutation, otherwise returns false. The algorithm used is a backtrack search as for AutomorphismGroup above.

Parameters

may be used to describe partitions of the rows and columns of \(M\) (Left) and of \(N\) (Right) that are to be preserved by \(x\).

The user may also supply subgroups of the automorphism groups of \(M\) (as LeftSubgroup) and of \(N\) (as RightSubgroup), if such subgroups are known. These may speed the course of the algorithm.

Example: Fano Auto (ex-5ad3a5)

We construct a matrix from a Fano polytope and compute its automorphism group.

> M := VertexFacetHeightMatrix(PolytopeSmoothFanoDim3(10)); M;
[1 0 0 0 2 1 2 2]
[0 0 0 1 1 2 2 2]
[0 0 1 2 0 2 2 1]
[2 0 1 0 2 0 2 1]
[0 2 0 1 1 2 0 2]
[1 2 0 0 2 1 0 2]
[0 2 1 2 0 2 0 1]
[2 2 1 0 2 0 0 1]
[2 2 2 1 1 0 0 0]
[1 2 2 2 0 1 0 0]
[1 0 2 2 0 1 2 0]
[2 0 2 1 1 0 2 0]
> A := AutomorphismGroup(M); A;
Permutation group A acting on a set of cardinality 20
Order = 24 = 2^3 * 3
  (2, 4)(3, 12)(5, 8)(7, 9)(13, 18)(15, 16)(17, 20)
  (1, 5)(2, 6)(3, 8)(4, 7)(9, 11)(10, 12)(13, 16)(14, 19)(17, 18)
  (1, 2)(3, 4)(5, 6)(7, 8)(9, 10)(11, 12)(13, 16)(17, 18)
> Nrows(M), Ncols(M);
12, 8
> Orbits(A);
[
  GSet{@ 14, 19 @},
  GSet{@ 13, 18, 16, 17, 15, 20 @},
  GSet{@ 1, 5, 2, 8, 6, 4, 3, 7, 12, 9, 10, 11 @}
]

Run in calculatorCopy input

The automorphism group is transitive on the rows of the matrix. Now dualize the matrix and test for isomorphism.

> D := Matrix(12, 8, [2-x:x in Eltseq(M)]);
> f, x := IsIsomorphic(M, D); f, x;
true (2, 4)(3, 12)(5, 8)(7, 9)(14, 19)(15, 17)(16, 20)
> M^x eq D;
true

Run in calculatorCopy input