# Minimal set of rows and columns covering all non-zero entries in matrix

Given a matrix $$A \in \{0,1\}^{n \times n}$$, use network flows to describe an algorithm that finds the minimal set $$I$$ of rows and columns such that any non-zero entry is in one of the rows or columns in $$I$$.

### What I have tried

1. Create an intermediate column (between $$s$$ and $$t$$) for every column and row.

2. For every column, draw an edge from that column to $$t$$ with a capacity equal to the number of $$1$$s it has in it.

3. For every row, draw an edge from that row to $$t$$ with a capacity equal to the number of $$1$$s it has in it.

4. Take the cut between this intermediate column and $$t$$, calculate the entry with the most capacity, add that to set $$I$$.

5. For the selected row or column, remove all $$1$$s from that column and recalculate the network flow.

6. Continue to do this until the flow is $$0$$, i.e., all $$1$$s have been accounted for.

### Examples

1 1 0
1 0 0
1 0 0


We would take column 1, and row 1 here.

1 1 1
0 0 0
0 0 0


We would take row 1 here.

Is there a better approach?