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, ..., 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

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

     RowColours: SeqEnum[RngIntElt]      Default: 

     ColColours: SeqEnum[RngIntElt]      Default: 

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.

     Subgroup: GrpPerm                   Default: 

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.

     Al: MonStgElt                       Default: "Default"

The parameter Al is kept for backward compatibility.

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

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

     LeftRowColours: SeqEnum[RngIntElt]  Default: 

     LeftColColours: SeqEnum[RngIntElt]  Default: 

     RightRowColours: SeqEnum[RngIntElt] Default: 

     RightColColours: SeqEnum[RngIntElt] Default: 

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.

> 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 @}
]

> 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