Simple Representation of Matrices with the Given Equivalence Relationship

Question

I'm currently working on an algorithm that requires me to come up with unique matrices. Two matrices are considered equivalent if one's rows and columns can be swapped to make it match the other. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix} \equiv \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}$. I think it would be immensely helpful to find a nice way to represent each matrix so that equivalent matrices have the same representation. The best I could come up with is just making a list of the rows and columns and comparing them. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}=>\{R:((0, 0), (1, 1))\}, \{C:((0, 1), (0, 1))\} $ $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}=>\{R:((0, 1), (0, 1))\}, \{C:((0, 1), (0, 1))\}$ $\begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}=>\{R:((0, 1), (0, 1))\}, \{C:((0, 0), (1, 1))\}$

but I feel like there's a better way because this looks messy. Any suggestions?

Edit: This is not always binary matrix. Numbers can range from 0-19.

Answer 1

When you are dealing with binary matrices, this is the problem of graph canonization. There is no known polynomial-time algorithm for this problem, and determining whether it can be done in polynomial time is a famous open problem, but there are techniques that are often reasonably efficient in practice (e.g., Nauty). (The relationship is that every graph corresponds to a binary matrix, namely, it adjacency matrix, and versa.)

When you have non-binary matrices, you can think of this as a graph with labels on the edges. There are standard techniques for reducing this to the standard graph canonization problem, by converting each labelled edge to a small subgraph. See, e.g., Graph isomorphism problem for labeled graphs, On graph isomorphism for weighted graphs, What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?.