**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?

5more comments