# Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?

Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and columns (and possibly reflection).
For each line or column of a matrix $M\in\mathcal M_n$, we define its weight as the number of $x$'s occurring in it. The signature of $M$ is the set of the two vectors of row weights and column weights, wlog both in non-increasing order. (And wlog we'll reorder the rows and columns accordingly.)
We can further define two "incidence matrices", $R=R(M)$ and $C=C(M)$, where $r_{ij}$ is the number of $x$'s which are at the same position in both row $i$ and row $j$, likewise $c_{ij}$ for columns. For an equivalence class of a matrix in $\mathcal M_n$, those are well-defined up to simultaneous permutations of rows and columns (i.e. maintaining the entries on the main diagonal, which are the two sets of the signature).

By definition, equivalent matrices have the same incidence structure. I think the converse doesn't hold, at least not for $n$ big enough. For instance I am thinking of adjacency matrices of strongly regular graphs, which are not necessarily unique for a given parameter set. Now the strong regularity is not exactly captured by the incidence matrices, and those adjacency matrices are symmetric, so this is only a heuristic argument. For directed graphs with loops allowed, the equivalence classes w.r.t. swapping two lines or columns in the adjacency matrix seem rather hard to characterize. So probably graph theory won't be of much help for a rigorous argument.

What would be a counterexample of the smallest size, i.e. two matrices which have the same incidence structure but are not equivalent?

This question has occurred when I found a second extremal matrix for n=7 here. Both have the same incidence structure (any two lines have two $x$'s in common, and so have any two columns) and, up to sign, the same determinant, but very different (visible) symmetries. To reproduce them here,

$M_1=\begin{pmatrix} x&1&1&\color{blue}x&1&x&x\\ 1&x&1&\color{blue}x&x&1&x\\ 1&1&x&\color{blue}x&x&x&1\\ \color{blue}x&\color{blue}x&\color{blue}x&\color{blue}x&\color{blue}1&\color{blue}1&\color{blue}1\\ 1&x&x&\color{blue}1&1&x&x\\ x&1&x&\color{blue}1&x&1&x\\ x&x&1&\color{blue}1&x&x&1\\ \end{pmatrix},\qquad M_2=\begin{pmatrix} x&x&x&1&x&1&1\\ 1&x&x&x&1&x&1\\ 1&1&x&x&x&1&x\\ x&1&1&x&x&x&1\\ 1&x&1&1&x&x&x\\ x&1&x&1&1&x&x\\ x&x&1&x&1&1&x \end{pmatrix}.$

The blue row and column of $M_1$ are not distinguishable from the others, as it is easy to obtain an identical matrix with the blue row and column elsewhere by certain swappings of lines and columns.

But is there a somewhat efficient algorithm allowing to check whether a pair like $M_1$ and $M_2$ are equivalent?

• I don't think so. Miodrag Zivkovic in his 2005 classification paper (see ArXiv) spent a lot of computer cycles counting equivalence classes of various types. I think his work can be extended to one or two higher orders now, but I do not know who has done it. I did some enumeration by computer back in the 90's, and doing orders up to 6 by hand (for full rank) was quite manageable. You might for example prove that 1 does not occur in a signature of interest. Gerhard "Fun With Combinatorial Matrix Theory" Paseman, 2018.01.23. – Gerhard Paseman Jan 23 '18 at 23:47
• Isn't this a version of the graph isomorphism problem, for which there is no provably efficient algorithm? – Igor Rivin Jan 24 '18 at 0:44
• It’s basically isomorphism of bipartite graphs. – Chris Godsil Jan 24 '18 at 1:32
• I agree with Chris Godsil's comment. Let me explain: You can define a bijection between matrices and labelled bipartite graphs with bipartition $A \cup B$, where $|A|=|B|=n$, $A$ has labels $1, \dots, n$, and $B$ has labels $1', \dots, n'$. Simply draw an edge from $i$ to $j'$ if $M_{ij} = 1$. Now swapping rows means swapping labels in $A$, swapping columns means swapping labels in $B$, and reflection means exchanging the roles of $A$ and $B$. In particular, two matrices are equivalent if and only if their corresponding bipartite graphs are isomorphic (after removing labels). – Florian Lehner Jan 24 '18 at 14:44
• @FlorianLehner There is a minor correction needed. If the graph is disconnected, the colours in one component can be flipped without flipping colours in the other components. This is an operation not allowed for the matrices. To make the correspondence complete there are ways to first convert the graph to a connected bipartite graph in an isomorphism-invariant way. – Brendan McKay Jan 25 '18 at 2:01

Regarding the first question: there is a counterexample of size $91$.
There are four non-isomorphic finite projective planes of order $9$: https://doi.org/10.1016/0012-365X(91)90280-F, http://oeis.org/A001231.
Take the incidence matrices of non-isomorphic finite projective planes of order $9$, and replace each $1$ by $x$ and each $0$ by $1$. These matrices have $91$ rows and $91$ columns, and their incidence structure has all $r_{ij}$ and $c_{ij}$ equal to $1$.
• At least for the Desarguesian ("standard") projective plane, the determinant should be $(3x-3)^{90}(10x+81)$, by educated guessing based on the planes of order 3 and 4. – Wolfgang Jan 25 '18 at 11:58
• In fact, the incidence structure is encoded in the matrices $M^TM$ and $MM^T$. For a projective plane of order $d$, we have $n=d(d+1)+1$ and get $M^TM=MM^T=fI_n+gJ_n$ with quadratic polynomials $f=d(x-1)^2$ and $g=(x+d)^2-d$; here $I_n$ is the identity and $J_n$ the all-1-matrix. So $\det^2(M)=\det(M^TM)=f^{n-1}\cdot(f+ng)=d^{d(d+1)}(x-1)^{2d(d+1)}[(d+1)x+d^2]^2$ is the same for all projective planes. I think this approach works for any other incidence structure as well, so the determinant.should only depend on the incidence structure. – Wolfgang Jan 26 '18 at 15:56
• I see, $MM^T$ is the same for all finite projective planes, and thus the determinant is the same as well. I guess the diagonal entries of this matrix should be equal to $(d+1)x^2 + d^2$, so I think $f$ should be smaller by $d^2-d$. – Jan Kyncl Jan 27 '18 at 1:24