Skip to main content

Lexacographically Lexicographically largest incidence matrix

Source Link
Ihromant
  • 501
  • 1
  • 7

Lexacographically largest incidence matrix

I have simple algorithmic question, but I can't find any source where this algorithm is explained in details. Let's assume that we have incidence (with 0 and 1 values) matrix of size $m\times n$. Let we apply simultaneously all pairs of row $P_1 \in S_m$ and column $P_2 \in S_n$ permutations to this incidence matrix. Obviously because we have finite ordered set, there exist lexicographically largest value of this matrix.

Question is: what is the best algorithm that allows to find this biggest value?

Example input (Fano plane incidence matrix): Fano plane

Example output:

$$ 1110000 \\ 1001100 \\ 1000011 \\ 0101010 \\ 0100101 \\ 0011001 \\ 0010110 $$