GATE CS 2024 Set 1 Q39 — Linear Algebra: Matrices, Determinants, System of Linear Equations

By the Rank-Nullity Theorem, for any $n \times m$ matrix $A$ where $m > n$:

$$\text{rank}(A) + \text{nullity}(A) = m$$

Since $A$ has $n$ rows, the rank of $A$ is at most $n$ (i.e., $\text{rank}(A) \le n$). This gives:

$$\text{nullity}(A) = m - \text{rank}(A) \ge m - n$$

The nullity of $A$ is the dimension of the null space of $A$, which represents the maximum number of linearly independent solutions to the system $Ax = 0$. Since $\text{nullity}(A) \ge m - n$, there exist at least $m - n$ linearly independent solutions. Thus, Option A is always true.

We can disprove the other options with counterexamples:

• Option B: If $A$ is the $1 \times 3$ zero matrix ($n=1, m=3$), the nullity is $3$. We need $3$ linearly independent vectors to span the solution space, which is more than $m-n = 2$.
• Option C: Let $A = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix}$ ($n=1, m=3$). Here $m-n = 2$. Any solution with at least $2$ zero variables must be the zero vector.
• Option D: Let $A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$ ($n=2, m=3$). The solutions are of the form $[0, 0, c]^T$. The maximum number of non-zero variables in any solution is $1$, which is less than $n = 2$.