GATE CS 2004 Q76 — Linear Algebra: Matrices, Determinants, System of Linear Equations

Let $k$ be the maximum number of non-zero entries such that no two are in the same row or column (i.e., they are independent entries).

• Since all non-zero entries of the matrix are covered by $a$ rows, any set of independent non-zero entries can contain at most one entry from each of these $a$ rows. Thus, $k \leq a$.
• Similarly, since all non-zero entries are covered by $b$ columns, any set of independent non-zero entries can contain at most one entry from each of these $b$ columns. Thus, $k \leq b$.

Combining these two inequalities, we get: