This problem, which I'll call CO for Column Ordering, is NP-hard. Here's a reduction from the NP-hard problem Vertex Cover (VC) to it:
Constructing an instance of CO from an instance of VC
Let the input VC instance be $(V, E)$. Let $n=|V|$ and $m=|E|$. We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns. The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing an edge that needs to be covered. The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).
For each vertex $v_i$, create a column in which:
- among the top $(n+1)m$ rows, the $j$-th block of $n+1$ rows all contain a +1 when edge $e_j$ is incident on $v_i$, and 0 otherwise, and
- the bottom $n$ rows are all 0 except for the $i$-th, which is -1.
Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.
Proof
Intuitively, the -1s in the top of the "fence" column force the selection of a subset of columns to be placed to its left that together contain +1s in all these positions -- corresponding to a subset of vertices that are incident on every edge. Each of these columns that appears to the left of the "fence" has a -1 on a distinct row somewhere in the bottom $n$ rows, incurring a cost of 1; the +1s in the bottom of the "fence" ensure that all columns placed to its right incur no such cost.
Clearly a VC solution using $k$ vertices yields a solution to the constructed CO instance with cost $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.
It remains to show that a solution to CO with cost at most $k$ yields a vertex cover with at most $k$ vertices.
Observe that in any optimal solution to CO, every row in the top $(n+1)m$ rows has a +1 before a -1. (Suppose this were not the case, i.e., some row in the top $(n+1)m$ rows has a -1 before a +1: Then the same must hold for every row in this block of $n+1$ rows, since every column behaves the same way across each of these blocks. This block of rows corresponds to an uncovered edge, which can only occur if both the columns that correspond to the endpoints of this edge appear to the right of the fence. Moving either of these columns from the right side of the fence to the left side would repair every row in this block, saving $n+1$ -1s while costing only a single -1, and thus improving the total score by $n$. Thus the original solution could not have been optimal: contradiction.)
Since each of the $m$ blocks of rows in the top $(n+1)m$ rows have a +1 before a -1, each of the corresponding edges is covered by a vertex corresponding to a column to the left of the fence: that is, this subset of vertices constitutes a vertex cover. Since none of the top $(n+1)m$ rows have a -1 before a +1, the only place where cost can accrue in the solution is in the bottom $n$ rows, from columns placed to the left of the fence. Each such column has cost exactly 1, so given that the cost is at most $k$, there must be at most $k$ such columns, and hence at most $k$ vertices in the cover.
Finally, it's clear that the CO instance can be constructed in polynomial time from the VC instance, meaning that if a polynomial-time algorithm existed for solving CO, any VC instance could also be solved in polynomial time by first constructing a CO instance as described above and then solving it. Since VC is NP-hard, CO is too.