# 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`

```magma
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`

```magma
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.

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

```

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

```magma
> 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

```