It seems this question has confused some of you. Here's an example that was sent in by a student and that I've tried explaining. Consider the matrix A=[ [0,1,0], [2,0,3], [4,0,5] ]. (It doesn't matter if in this notation, the rows are listed first or the columns...)
In this matrix, you can choose entries 1 in row 1, column 2, then 2 in row 2, column 1, and finally 5 in row 3, column 3. You thus have three nonzero entries, no two of which are in the same line.
So if the statement is going to be correct, you also need to show that whatever two lines (rows or columns) you choose, you'll miss at least one nonzero entry. This is clear for such a small matrix.
Now take a different example: B=[ [0,1,0], [1,0,1], [0,1,0] ]. Picking the nonzeros in row 1, column 2 and in row 2, column 1 gives two nonzeros that are not in the same line. However, we cannot add to this either of the other two nonzeros without having two nonzeros either in one row or in one column.
On the other hand, we cannot cover all the nonzeros with just one line, but need at least two (the middle row and the middle column). Thus both the maximum and the minimum are equal to 2.
I hope this helps, but do respond if there is still something that is not clear.
Subscribe to:
Post Comments (Atom)
Of course, both of these examples are small and so for them, the answers may be obvious. Your proof should work regardless of theh size of the matrix, even for nonsquare matrices.
ReplyDelete