GATE CS 2024 Set 1 — Question 49

The system $Ax = \mathbf{0}$ is a homogeneous system with $n$ equations and $m$ variables. The set of all solutions to $Ax = \mathbf{0}$ forms the null space (or kernel) of the matrix $A$. The dimension of this space is called the nullity of $A$.
According to the Rank-Nullity Theorem:
$$\text{rank}(A) + \text{nullity}(A) = m$$ $$\text{nullity}(A) = m - \text{rank}(A)$$ Since $A$ has $n$ rows, the maximum possible rank is $n$. Thus, $\text{rank}(A) \le n$.
Substituting this inequality:
$$\text{nullity}(A) \ge m - n$$ This means the dimension of the solution space is at least $m - n$. Therefore, there exist at least $m - n$ linearly independent solutions. Statement (A) is TRUE. This statement implies that the dimension of the solution space is exactly $m - n$ (i.e., the solution space is spanned by $m-n$ vectors). This is true only if $\text{rank}(A) = n$. However, the problem states $A$ is any matrix. If $\text{rank}(A) < n$, the nullity would be greater than $m - n$. Thus, this is not always true. Statement (B) is FALSE. This statement claims there is a non-zero solution with at least $m - n$ zeros. This is equivalent to saying there is a non-zero solution with at most $m - (m - n) = n$ non-zero entries (support size $\le n$).
Consider the case where $n=1, m=2$ and $A = \begin{bmatrix} 1 & 1 \end{bmatrix}$. The equation is $x_1 + x_2 = 0$. Non-zero solutions are of the form $k(1, -1)$. Every non-zero solution has 2 non-zero entries. We need a solution with at most $n=1$ non-zero entry, which is impossible here. Statement (C) is FALSE. This statement claims there is a solution with at least $n$ non-zero entries.
Consider $n=2, m=3$ and $A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$. The equations are $x_1 = 0, x_2 = 0$. Solutions are of the form $(0, 0, x_3)$. Any solution has at most 1 non-zero entry. We need at least $n=2$ non-zero entries, which is impossible. Statement (D) is FALSE.