Selecting Columns with Minimum Overlaps
I don't know if there is a polynomial-time algorithm, but if your matrix is not too large, you could try approaching this with integer linear programming.  Define zero-or-one variables $x_{ij}$, with the intended meaning that $x_{ij}=1$ means $j \in S_i$.  Then you have the constraints

$$\sum_{j} a_{ij} x_{ij} \ge 1.$$

Also, introduce zero-or-one variables $o_{pq}$, with the intended meaning that $o_{pq}=\Delta(S_p,S_q)$, and enforce that

$$o_{pq} = (x_{p1} \land x_{q1}) \lor \dots \lor (x_{pn} \land x_{qn})$$

using the techniques in Express boolean logic operations in zero-one integer linear programming (ILP).  (In other words, you introduce fresh temporary zero-or-one variables $o'_{pqj}$ and add the constraints $o'_{pqj} \ge x_{pj} + x_{qj}-1$, $o'_{pqj} \le x_{pj}$, $o'_{pqj} \le x_{qj}$, $o_{pq} \le o'_{pq1} + \dots + o'_{pqn}$, $o_{pq} \ge o'_{pqj}$.)

Finally, minimize $\sum_{p&lt;q} o_{pq}$, subject to the constraints above.  This is a set of linear inequalities over integer variables, so you can feed it to an off-the-shelf ILP solver and hope it finds you a good solution.  This algorithm will have exponential running time in the worst case, but ILP solvers incorporate many heuristics, so if the matrix is not too large, it's possible this might give you good results in a reasonable amount of time.