My apologies for the poor title and description, it's been a long time since I had linear algebra (or any formal math class).

Given the following example matrix:

\begin{matrix} & W & X & Y & Z\end{matrix}

$$\begin{matrix}A\\B\\C\\D\\E\\F\\G\\H\end{matrix}\begin{bmatrix}1 & 1 & 0 & 1\\0 & 0 & 0 & 1\\0 & 0 & 1 & 0\\1 & 1 & 1 & 0\\0 & 0 & 0 & 0\\0 & 0 & 0 & 0\\0 & 0 & 1 & 0\\0 & 1 & 0 & 1\end{bmatrix}$$

How would I determine the fewest number of rows (A-H) that select all of the columns (W-Z).

For example, in the matrix above, row A fulfills columns W, X, and Z and then row C, D, or G can then fulfill the remaining Y column.

Another example would be row D which fulfills columns W, X, and Y. We could then fulfill column Z with either row A, B, or H.

Again, please forgive me for the poor description and lack of appropriate terminology and language. Please let me know if I'm missing any information or need to clarify anything.


This is not a linear algebra question, despite being phrased with matrices. It is the set cover problem. Each row corresponds to a subset of the columns, namely those columns in which it is nonzero. Choosing a minimal number of rows so that the union of those subsets is everything, i.e. so that all columns are represented, is exactly a set cover. Unfortunately this problem is NP-hard. For large matrices, it can potentially take a very very long time (longer than the universe has existed) to compute the answer you seek. Fortunately there are relatively fast approximate algorithms, i.e. ways to find solutions that might not be optimal, but provably close to optimal.

  • 1
    $\begingroup$ Thanks for the link, my guess was that this could be posed as a graph problem and two of such are listed. $\endgroup$
    – mvw
    Jul 6 '15 at 21:34
  • $\begingroup$ Thanks for your help and great eye in recognizing the actual problem instead of my poorly worded version. For a bit of background, here at work we were trying to solve the issue above. I had proposed a solution, but recognized the problem as one I had studied in college (I thought in linear algebra, but obviously I was wrong) and wanted to verify the approach. Anyway, it turns out we're on the right track since our proposed solution is listed in the Wikipedia article under "greedy algorithm" and should work well enough for us. Thanks again for your help and quick response. $\endgroup$ Jul 8 '15 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.