Permutation Normalforms for 0/1-matrices

You can listen to this music while reading.


Let's define an equivalence relation on matrices with 0/1-entries and then pick a representantive of every equivalence class.
Then we write a program to enumerate the representatives, which can then be used for other shizzle.

\(\mathbb{F}_2=\{0,1\}\) denotes the field of order \(2\) ,
\(\mathbb{F}_2^{m\times n}\) the set of all matrices  with \(m\) rows and \(n\) columns with entries from \(\mathbb{F}_2\)

Define the equivalence relation \(\sim\) on \(\mathbb{F}_2^{m\times n}\) via
\(A \sim B\) :iff
\(A\) can be transformed into \(B\) via row and column permutations, i.e. there are permutation matrices \(P,Q\) so that \(B=PAQ\).

What would be an easily computable normalform for matrices under this equivalence relation?

For an \(m\times n\)-matrix \(A\) and sets of indices \(I\subseteq \{1,\ldots,m\}, J\subseteq\{1,\ldots,n\}\) let
\(A(I,J)\) be the \(|I|\times|J|\)-sub-matrix of \(A\) that consists of the rows in \(I\) and columns in \(J\).
We use the following notations
\(A(i,j):=A(\{i\},\{j\})\)
\(A(I,-):=A(I,\{1,\ldots,n\})\)
\(A(-,J):=A(\{1,\ldots,m\},J)\).

Let \(|z|=|\{i | z(i)=1\}|\) be the number of \(1\)-entries in a vector \(z\in\mathbb{F_2}^{1\times n}\).

Denote by \(\prec\) the lexicographic order on bit vectors, i.e.
for \(v=(b_1 \ldots b_n), w=(c_1 \ldots c_n)\in\mathbb{F}_2^{1\times n}\) we define
\(v\prec w\) :iff 
\(b_i < c_i \) for the smallest \(1\leq i \leq n\) with \(b_i \neq c_i\).

Row vectors can now be ordered as follows:
For \(w,v \in \mathbb{F}_2^{1\times n}\)
\(w < v\) iff:
\(|w|<|v|  \vee ( |w|=|v| \wedge w\prec v)\)

And finally matrices can be linearly ordered by comparing the concatenation of their rows lexicographically with respect to <:
For \(A,B \in \mathbb{F}_2^{m\times n}\)
\(A<B\) iff:
\( A(i,-)  <  B(i,-) \) for the smallest \(1\leq i \leq m\) such that  \( A(i,-) \neq B(i,-) \)

 Having defined a linear order < on the set of all matrices, we can now simply pick the <-least element from each equivalence class as its representative.

\(A\in\mathbb{F}_2^{m\times n}\) is in Permutation Normalform if
\(A\leq B\) for all \(B\in\mathbb{F}_2^{m\times n}\) with \(A\sim B\).

In general any linear order < on \( \mathbb{F}_2^{m\times n} \) induces a Permutation Normalform (the <-smallest matrix in each ~-equivalence class) and
any linear order \(\prec\) on \(\mathbb{F}_2^{1\times n}\) induces a linear order on matrices by comparing their rows lexicographically with respect to the order on  row vectors.
There are are also many other possibilities to order matrices. There are \(2^{mn}!\) many ways to order \(\mathbb{F}_2^{m\times n}\), each defining a choice function on the ~-equivalence classes and thus a normalform on matrices.

Is there a normalform, which isn't induced by any order at all? (No, to every choice function corresponds a linear order < on the set of matrices so that the choice function always chooses the <-least element of every equivalence class.)

A permutation normalform  is a set of choice functions \(f_{m,n}\colon \mathbb{F}_2^{m\times n}/\sim \to \mathbb {F}_2^{m\times n}\) for all \(m,n\in\mathbb{N}\) on the set of all ~-equivalence classes, that pick a unique representatives from each ~-equivalence class.

The number of different choice functions \(f_{m,n}\) there are for fixed \(m,n\) depends on the size of the ~-equivalence classes, which doesn't seem so easy to calculate a priori. That's where a normalform could be of help.

What i am interested in however is the normalform/choice function that is the most efficient computable. Associated with each normalform are two different computationally tasks.

1. Given a matrix \(A\) compute its normalform
2. Given natural numbers \(m,n\) output a list of all \(m\times n\)-matrices in normalform.

2. is often computationally easier than 1.
For instance it is easy to output a list of all square matrices in Jordan-Normalform, but it is harder to compute the Jordan-Normalform to a given matrix \(A\).

Matrices in Jordan-Normalform are representatives of the equivalence relation \(\sim\) on \(n\times n\)-matrices  defined by
\(A \sim B\) iff
\(A=P^{-1}BP\) for an invertible matrix \(P\)

Another interesting problem would be to compute the normal forms of 0/1-matrices under the equivalence relation \(A,B\in\mathbb{F_2}^{n\times n}\)
\(A \sim B\) iff
\(A=P^t B P\) for a permutation matrix \(P\)
(\(P^t\) denotes the transposition of \(P\).)

This equivalence relation is a refinement of the permutation equivalence relation (\(A\sim B \Leftrightarrow A=PBQ\) defined above, where A results from any row and column permutations of B that can be chosen independently from each other.
Multiplying a matrix B with a permutation matrix P from the left has the effect of permuting the rows of B, whereas multiplying B with a permutation matrix Q from the right has the effect of permuting its columns.
In the matrix \(P^t B P\) the same permutation is applied to the rows and columns of B, thus if for example P permutes the first and second row of B,  then \(P^t\) permutes the first and second column of B.
It is also a refinement of the Jordan-Normalform equivalence relation, because \(P^t=P^{-1}\) for permutation matrices.

There is also a nice connection to graph theory:
A symmetric \(n\times n\)-matrix with 0/1-entries is always the adjacency matrix of a graph \(G_A=(\{1,\ldots,n\},E_A\)) with \(n\) vertices.
There is an edge from \(i\) to \(j\) iff \(A(i,j)=1\).
Applying the same permutation \(P\) to the rows and columns of \(A\) corresponds to a permutation of its vertices. Two graphs with adjacency matrices \(A\) and \(B\) are isomorphic iff \(A=P^t B P\) for some permutation matrix \(P\). The permutation on the vertices that is induced by \(P\) corresponds then to an isomorphism between the graphs with adjacency matrices \(B\) and \(A\),
i.e. \(A \sim B\) if and only if \(G_A\) and \(G_B\) are isomorphic.

Thus any algorithm that solves task 1. , i.e. computes a normalform with respect to ~ of a given adjacency matrix \(A\) would thereby choose a unique representative from the isomorphism class of \(G_A\). This is known as the Graph canonization problem and any efficient graph canonication procedure could also be used to efficiently test whether two graphs are isomorphic  by computing the normalforms of their adjacency matrices and checking whether they are equal. It is not known however whether there is an efficient procedure for the graph isomorphy test, although recently it was shown that  graphy isomorphy can be tested in quasi-polynomial time. 
(Quasi-polynomial time means the algorithm needs \(2^{\mathcal{O}(\log(n)^c)}\) steps for a constant \(c\geq 1\). (c=1 would be polynomial time) )
A solution to task 2. would correspond to an algorithm that outputs to a given number \(n\) a list of representatives of the isomorphism class of all graphs with \(n\) vertices. I don't know how easy or hard this is.

So, interestingly many problems are similar in form to our initial problem. This doesn't necessarily suggest that there would be a universal solution though.

For now let's stay with the problem of merely computing a permutation normalform for the initial equivalence relation, because that seems easier and is also interesting.

Update:
I just read that the problem to decide whether a 0/1-matrix can be transformed into a lower triangle matrix via column and row permutations is in "NP-Limbo", i.e. another one of those NP-problems that have neither been proven to be NP-hard nor in P.
This might have implications for the complexity of computing permutation normal forms/choice functions. It means that choice functions that always pick a lower triangle matrix from an equivalence class, if there exists one, are at least as hard to compute. And it seems that the choice function i defined above that always picks the <-smallest element does exactly this. So task 1. for this choice function is difficult. Task 2. is easy though.