How to encode matrices uniquely

Question

Given a square matrix $A=[a_{ij}]_{n \times n}$, an operation $swap(A, i, j)$ is defined to swap row $i$ and $j$ of $A$ and do the same thing with the corresponding columns. For example, in the following example, we can see the $swap(A, 1, 3)$:

$$A=\left[ \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \right] ~~~~~\Rightarrow~~~~~ swap(A,1,3)=\left[ \begin{array}{ccc} i & h & g \\ f & e & d \\ c & b & a \end{array} \right]$$

For a matrix $A$, let $swap^k(A)$ be the set of matrices produced by exactly $k$ swaps. For example $B \in swap^3(A)$ means that there is a sequence of 3 swaps that can convert $A$ into $B$.

A unique encoding $\phi$ of this matrix is a function of $A$ such that:

$$\phi(A)=\phi(B) ~~~~ \Leftrightarrow ~~~~ \exists k ~:~ B \in swap^k(A)$$

For simplicity, we can assume that the matrix is symetric and its elements are in $\{0,1\}$. I am interested to know whether there exist such encoding for this case of matrices or if there is a proof for its non-existence.

Edit. What is the most efficient way to do this?

Answer 1

Such an encoding exists and is finite. Whether or not it is tractable is a much harder question.

$\phi(A)$ can be defined to be an encoding of the span of the swaps of $A$:

$$\text{SwapSpan}(A) = \cup_{k=0}^{\infty} \text{swap}^k(A)$$ $$\phi(A) = \text{Encoding}(\text{SwapSpan}(A))$$

Since there are $n^2$ elements of the matrix, there is an upper bound of $(n^2)!$ number of matrices in $\text{SwapSpan}(A)$. Explicitly writing out the list of matrices in lexicographical order is a valid canonical $\text{Encoding}$.

Note that if $A \in \text{SwapSpan}(B)$ then $\text{SwapSpan}(A) = \text{SwapSpan}(B)$ since the order of the swaps can simply be reversed.

The span can also be computed, since a breadth first search of all the swaps is guaranteed to terminate.

Whether or not this is tractable depends on your computing power and the size of your matrices.

Answer 2

You can encode rows and columns with multisymmetric functions (one set of generators for the rows, and one set of generators for the columns). This paper is quite a good source.

For example, a 2-by-2 matrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ can be encoded as $$ (ad, a+d, bc, b+c). $$ This is by no means the most efficient encoding, but it should do the job.

[I made an edit because I just realize I misunderstood the problem.]

Answer 3

The problem of finding a canonical form for ${0,1}$ symmetric square matrices using simultaneous row and column swaps is one of the approaches for solving the Graph Isomorphism Problem via graph canonization. There are algorithms that do this is polynomial average time, the best $O$-complexity algorithm is still superpolynomial. So, step 1 is to canonize your matrix/graph.

From here, you may compress the data to make it space efficient. If your elements were in ${0,1}$, then you could make a binary blob, listing the rows in order. If you had very few $1$'s (or $0$'s, really), you could store it as a sparse matrix (linked list of elements and their positions in each row). Or, if you have some infinitesimal amount of tolerance for error, you could take your current encoding and send it through a hashing algorithm (like MD5). Then, equality of the hash values indicates equality of the original matrices (modulo row swaps) with high probability. This comparison would happen in constant time.