The canonisation problem for boolean matrices

For more clarity let me first restate the problem the algorithm is to supposed to solve in simpler terms than in the previous article
(everything will become more refined and clearer from article to article):

I call two matrices A and B permutation equivalent, if you can get B from A by permuting the rows and columns of A.

Write A~B if A and B are permutation equivalent
~ is an equivalence relation, i.e.  for all matrices A,B,C it holds that:
1. A~A
2. If A~B then B~A
3. If A~B and B~C then A~C

Here is an example:
\[
A=
\begin{bmatrix} 
1 & 0 & 1\\
0 & 1 & 0\\
0 & 1 & 1
\end{bmatrix},
B=
\begin{bmatrix} 
0 & 1 & 1\\
1 & 0 & 0\\
1 & 0 & 1
\end{bmatrix},
C=
\begin{bmatrix} 
1 & 1 & 0\\
1 & 0 & 0\\
0 & 1 & 1
\end{bmatrix},
D=
\begin{bmatrix} 
0 & 0 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}
\]

A~B , because you get B from A by swapping the first two columns.
B~C , because you get C from B by first swapping rows 1 and 3, then swapping columns 2 and 3
therefore also A~C and so A,B,C are all permutation equivalent, i.e. in the same equivalence class,
but D isn't permutation equivalent to any of the others, because it has two rows that have two 0's and one 1, whereas the others have only one such row and no matter how you permute their rows and columns, you will never get two rows with two 0's and one 1. Because if you swap two columns, then the number of 1s and 0s in each row remains the same and no new row can be created by swapping rows. So this is an invariant under permutations.

Now I want to program a function N(X) which given any 0/1-matrix A as an input computes a matrix N(A) with the following two properties:

1.  N(A)~A
2.  A~B \(\Leftrightarrow\) N(A)=N(B) , for any A,B

The matrix N(A) is then what i call the permutation normal form of A.  All matrices in the same equivalence class have the same permutation normal form. Non-equivalent matrices have different normal forms. So N picks a unique representantive from every equivalence class. It is a choice function on the equivalence classes of ~. Also called canonisation function.

There are infinitely many choice functions on the set of all matrices though. Ultimately i want to find the one that is easiest to compute.

In the last article i have defined a specific function N.

N is defined with the help of a linear order < on the set of mxn-matrices.
I.e. all mxn-matrices can be arranged in some linear order
\(A_0 < A_1 < A_2 <....<A_n\)

Then N can simply pick the <-maximal one from each equivalence class , i.e.
N(A):="the <-maximal B with B~A"

< is defined by the following comparison algorithm:
Given two mxn-matrices A and B.
Compare the matrices row for row from top to bottom and
find the smallest row-index i, so that A's i-th row is different from B's i-th row.
If there is no such i, then A=B.
If there is such an i, then count the number of ones in the i-th row of A and the i-th row of B.
If there are more ones in A's i-th row, then A>B.
If there are more ones in B's i-th row, then A>B.
Otherwise the number of ones are equal.
Then compare A and B's i-th rows from left to right and find the smallest column-index j, so that A(i,j) \(\neq\) B(i,j).
If A(i,j)=1 and B(i,j)=0 then A>B
If A(i,j)=0 and B(i,j)=1 then A<B



Example:
\[
A=
\begin{bmatrix} 
1 & 0 & 1\\
0 & 0 & 1\\
0 & 1 & 1
\end{bmatrix},
B=
\begin{bmatrix} 
1 & 0 & 1\\
0 & 0 & 0\\
1 & 1 & 1
\end{bmatrix}
\]

The first row where A and B differ is the second one => i=2
In that row the first column where they differ is the third one => j=3
A(2,3)=1 and B(2,3)=0 , thus A>B

Here is how < orders for example all 16 2x2 matrices:
\[
\begin{array}{c}
\begin{bmatrix} 
0 & 0 \\
0 & 0
\end{bmatrix}<
\begin{bmatrix} 
0 & 0 \\
0 & 1
\end{bmatrix}<
\begin{bmatrix} 
0 & 0 \\
1 & 0
\end{bmatrix}<
\begin{bmatrix} 
0 & 0 \\
1 & 1
\end{bmatrix}<
\begin{bmatrix} 
0 & 1 \\
0 & 0
\end{bmatrix}<
\begin{bmatrix} 
0 & 1 \\
0 & 1
\end{bmatrix}<
\begin{bmatrix} 
0 & 1 \\
1 & 0
\end{bmatrix}<
\begin{bmatrix} 
0 & 1 \\
1 & 1
\end{bmatrix}\\
<\begin{bmatrix} 
1 & 0 \\
0 & 0
\end{bmatrix}<
\begin{bmatrix} 
1 & 0 \\
0 & 1
\end{bmatrix}<
\begin{bmatrix} 
1 & 0 \\
1 & 0
\end{bmatrix}<
\begin{bmatrix} 
1 & 0 \\
1 & 1
\end{bmatrix}<
\begin{bmatrix} 
1 & 1 \\
0 & 0
\end{bmatrix}<
\begin{bmatrix} 
1 & 1 \\
0 & 1
\end{bmatrix}<
\begin{bmatrix} 
1 & 1 \\
1 & 0
\end{bmatrix}<
\begin{bmatrix} 
1 & 1 \\
1 & 1
\end{bmatrix}
\end{array}
\]

There are 7 permutation equivalence classes:
\[
\begin{array}{c}
C_1=\{\begin{bmatrix} 
0 & 0 \\
0 & 0
\end{bmatrix},
\},
C_2=\{
\begin{bmatrix} 
0 & 0 \\
0 & 1
\end{bmatrix},
\begin{bmatrix} 
0 & 0 \\
1 & 0
\end{bmatrix},
\begin{bmatrix} 
0 & 1 \\
0 & 0
\end{bmatrix},
\begin{bmatrix} 
1 & 0 \\
0 & 0
\end{bmatrix} \},
C_3=\{\begin{bmatrix} 
0 & 0 \\
1 & 1
\end{bmatrix},
\begin{bmatrix} 
1 & 1 \\
0 & 0
\end{bmatrix}
\},
C_4=\{
\begin{bmatrix} 
0 & 1 \\
0 & 1
\end{bmatrix},
 \begin{bmatrix} 
1 & 0 \\
1 & 0
\end{bmatrix}
\}\\
C_5=\{
\begin{bmatrix} 
0 & 1 \\
1 & 0
\end{bmatrix},
\begin{bmatrix} 
1 & 0 \\
0 & 1
\end{bmatrix}
\},

C_6=\{
\begin{bmatrix} 
0 & 1 \\
1 & 1
\end{bmatrix},
\begin{bmatrix} 
1 & 0 \\
1 & 1
\end{bmatrix},
\begin{bmatrix} 
1 & 1 \\
0 & 1
\end{bmatrix},
 \begin{bmatrix} 
1 & 1 \\
1 & 0
\end{bmatrix}
\},
C_7=\{
\begin{bmatrix}  1 & 1 \\
1 & 1
\end{bmatrix}
\}
\end{array}
\]Here are the matrices that N picks from each equivalence class, i.e. always the  <-maximal element from each class:
\[
\begin{array}{c}
N(A)=\begin{bmatrix} 
0 & 0 \\
0 & 0
\end{bmatrix}
\text{ for } A\in C_1,

N(A)=
\begin{bmatrix}  1 & 0 \\
0 & 0
\end{bmatrix}
\text{ for } A\in C_2,

N(A)=
\begin{bmatrix} 
1 & 1 \\
0 & 0
\end{bmatrix}
\text{ for } A\in C_3,

N(A)=
\begin{bmatrix} 
1 & 0 \\
1 & 0
\end{bmatrix}
\text{ for } A\in C_4\\

N(A)=
\begin{bmatrix} 
1 & 0 \\
0 & 1
\end{bmatrix}
\text{ for } A\in C_5,

N(A)=
 \begin{bmatrix} 
1 & 1 \\
1 & 0
\end{bmatrix}
\text{ for } A\in C_6,

N(A)= 
\begin{bmatrix}  1 & 1 \\
1 & 1
\end{bmatrix}
\text{ for } A\in C_7
\end{array}
\]


Meanwhile i've found out a lot more about this problem after having asked on.stack exchange
Stay tuned for the next few articles.