[Math] Getting a matrix lexicographically sorted along both directions

discrete mathematicslinear algebramatricessorting

Let $A$ be some $2n\times 2n$ matrix such that each row and each column contains exactly $n$ times $0$ and $n$ times $1$.

If I sort the rows of $A$ lexicographically (in the sense of the matrix treated as a list of words, its rows, not in the sense of rearranging each single row) and then its colums, will the rows stay sorted?

If not, will the process of alternatingly sorting rows and colums eventually stabilize, giving some reordering of $A$ which is sorted along both directions?

[EDIT] Jorge Fernández Hidalgo's very nice answer works for arbitrary binary matrices and as well for matrices with values in $\{0,\dots,k-1\}$ by replacing $2$ with $k$ in the proof. Since every $n\times n$ matrix can be replaced by an order equivalent matrix with values in $\{0,\dots,n^2-1\}$, the proof also works for arbitrary real valued matrices.

However, I asked myself if it makes a difference whether one starts the process by sorting the rows or sorting the columns. In more general terms, if $P_R,P_C,P_R',P_C'$ are permutation matrices such that $P_R AP_C$ and $P_R' AP_C'$ are both sorted by rows and columns, do we necessarily have $P_R AP_C=P_R' AP_C'$?

The answer is (if my code is not wrong) that it makes a difference how we start, even when looking only at matrices of the type I described in the beginning (same number of $0$s and $1$s in each row and column). The smallest counterexample I could find (of this type) has dimensions $6\times 6$.

Here is some Matlab code, if anyone wants to fool around:

function A=sortRowFirst(A)
  B=sortrows(sortrows(A)')';
  while(!isequal(A,B))
    A=B;
    B=sortrows(sortrows(A)')';
  endwhile
endfunction

function A=sortColFirst(A)
  B=sortrows(sortrows(A')');
  while(!isequal(A,B))
    A=B;
    B=sortrows(sortrows(A')');
  endwhile
endfunction

function A=randNice(n)
  A=[];
  for i=0:n-1
    a=[ones(1,i),-ones(1,i)];
    a=a(randperm(i*2));
    A=[A;a;-a];
    A=A';
    a=[a(randperm(i*2)),[-1,1](randperm(2))];
    A=[A;a;-a];
  endfor
endfunction

Best Answer

Assign to each matrix the integer $f(M)=\sum\limits_{1\leq i,j\leq n}2^{i+j}M_{i,j}$.

Notice that if you swap two columns or rows that where lexicographically unordered this sum decreases.

Therefore sorting all of the columns or rows decreases $f(M)$.

Therefore this process must halt after at most $f(M)$ steps, and $f(M)$ is clearly bounded by $2^{2n}n^2$.

Related Question