I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! As input we have a matrix $\{-1, 0, 1\}^{n\ \times\ k} $ , for example:

$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & -1 \\ -1 & -1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & -1 \end{bmatrix}$

Without trying every single permutation, find an ordering of columns $c_i$ that maximises the number of rows for which the first non-zero element is $1$ .

For the example above, one such ordering (it's not unique!) is $(c_3, c_4, c_1, c_2, c_5)$, i.e. :

$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ 0 & 0 & -1 & 0 & 1 \\ 1 & 0 & 0 & 1 & -1 \\ 0 & 1 & 1 & -1 & 1 \\ 0 & 0 & 1 & 0 & -1 \end{bmatrix}$

Here, for 4 out of 5 rows the first non-zero element is 1.

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated!

Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example,

$$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & -1 \\ -1 & -1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & -1 \end{bmatrix}$$

Without trying every single permutation, find an ordering of columns $c_i$ that maximises the number of rows for which the first non-zero element is $1$.

For the example above, one such ordering (it's not unique!) is $(c_3, c_4, c_1, c_2, c_5)$, i.e.,

$$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ 0 & 0 & -1 & 0 & 1 \\ 1 & 0 & 0 & 1 & -1 \\ 0 & 1 & 1 & -1 & 1 \\ 0 & 0 & 1 & 0 & -1 \end{bmatrix}$$

Here, for $4$ out of $5$ rows the first non-zero element is $1$.