# Minimum columns of a matrix such that there is at least one nozero value in each row

I have a question that might belong better on the CS SE; let me know and I will move it. This comes from a research project and is a reframing of our question. Essentially, we have some matrix that is $$m \times n$$, where $$m > n$$. These matrices are generally diagonal and are only $$1$$s and $$0$$s. An example is: $$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}$$

We want to find the minimum amount of columns such that each row has at least one $$1$$ in it. For example, there are three possible "correct" answers to this:
cols 1, 2, 4, 5
cols 1, 2, 3, 5
cols 1, 3, 4, 5

While it would be great to have the specific combination of columns, it would also suffice to have simply the minimum number of columns. I think there should be an easier way to do this than brute-forcing. That's what I've been doing so far via Jupyter and as you can imagine, the complexity gets bad fast. So, is there a way to define this problem in terms of linear independence? Is there a linear algebra trick that might make this problem much simpler? Is this an integer linear programming thing? Is this a well-known problem in anyone's field? I appreciate any insight.

This looks like the set cover problem. We look for a covering of $$S:=\{1,\ldots,m\}$$ by sets $$S_j:=\{i: a_{ij}=1\}$$, where $$A=(a_{ij})$$ is the given binary matrix. Since the problem is NP-hard, there is no linear algebra trick to provide the minimal solution apart from the brute force approach.
There are methods, however, which provide an approximate solution for the problem. For example, a greedy algorithm suggests itself: starting with an empty cover, build iteratively the cover by selecting iteratively at step $$k$$ a subset $$S_{i_k}$$ which covers the maximum of uncovered elements. This can lead to suboptimal solutions but is quite easy to implement.