8
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Jan 23, 2018 at 23:47
  • $\begingroup$ Isn't this a version of the graph isomorphism problem, for which there is no provably efficient algorithm? $\endgroup$
    – Igor Rivin
    Commented Jan 24, 2018 at 0:44
  • 13
    $\begingroup$ It’s basically isomorphism of bipartite graphs. $\endgroup$
    – Chris Godsil
    Commented Jan 24, 2018 at 1:32
  • 2
    $\begingroup$ 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). $\endgroup$
    – Florian Lehner
    Commented Jan 24, 2018 at 14:44
  • 4
    $\begingroup$ @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. $\endgroup$
    – Brendan McKay
    Commented Jan 25, 2018 at 2:01

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Nice. What about the determinant(s) of those 4 matrices??? $\endgroup$
    – Wolfgang
    Commented Jan 25, 2018 at 8:43
  • $\begingroup$ 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. $\endgroup$
    – Wolfgang
    Commented Jan 25, 2018 at 11:58
  • $\begingroup$ The (in)equality of the determinants sounds like an interesting problem. Perhaps make it a separate question? Also the permanent could be interesting, since it is connected to the number of (perfect) matchings in the incidence graph of the projective plane, which is regular bipartite. A slightly related question: mathoverflow.net/questions/131279. $\endgroup$
    – Jan Kyncl
    Commented Jan 25, 2018 at 19:53
  • $\begingroup$ 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. $\endgroup$
    – Wolfgang
    Commented Jan 26, 2018 at 15:56
  • 1
    $\begingroup$ Your first 3 terms should be $dx^2−2dx+\color{red }d$, not $d^2$ for the 3rd term. :) :) $\endgroup$
    – Wolfgang
    Commented Jan 28, 2018 at 9:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .