# If $A$ is an $m \times n$ matrix, prove that $Ax=0$ has infinite solutions $iff$ $\text{rank}(A)<n$

Prove that $Ax=0$ has infinite solutions if and only if $\text{rank}(A)<n$

Here is one way of my if proof, but I don't know how to proof the other part.

Let $r$ be the rank of $A$. Then $r\leq n$. If $r<n$, then there are $n-r$ linearly independent solutions. Furthermore any linear combination of these solutions will also be a solution of $Ax=0$. Hence, in this case, the equation $Ax=0$ has infinite number of solutions

For the converse. Suppose that $\text{rank}(A)=n$. Then, the $n$ columns of the matrix are linearly independent. And as the rank of the transpose of $A$ if equal to the rank of $A$, you have $n$ lines which are linearly independent. WLOG you can suppose that those are the $n$ first.

Then if $Ax = 0$ you also have $Bx=0$ where $B$ is the sub matrix of $A$ taking the first $n$ lines. $B$ is invertible, hence $x=0$ and the last $m-n$ equations are obviously satisfied. Hence the equation $Ax=0$ has only one solution.

The key (since $A \lambda x = \lambda Ax$) is to observe that $Ax = 0$ has infinitely many solutions if and only if $Ax = 0$ has a nonzero solution.

Observe that $Ax$ is a linear combination of the columns of $A$, so $Ax = 0$ has a nonzero solution if and only if the columns of $A$ are linearly dependent.

Can you relate this to the rank of the matrix?

For the other part, you can use the rank-nullity theorem: $$\ker{A}+\text{rank}\,A=n$$
• @EmmaWool You can't use the determinant since $A$ isn't necessarly square. – Scientifica Mar 18 '17 at 19:08
If $Ax=0$ has two distinct solutions $x_0$ and $x_1$, then $A$ cannot have full column rank because $A(x_0-x_1)=0$ with $x_0-x_1\neq 0$. Conversely, if $A$ does not have full column rank, then there is $x_0\neq 0$ such that $Ax_0=0$ and so the solution set to $Ax=0$ must be infinite for it contains the infinite set $\{\alpha x_0:\alpha\in\mathbb{R}\}$. This proves $$Ax=0\text{ having 2 distinct solutions}\iff A\text{ does not have full column rank}\\\iff Ax=0\text{ having infinitely many distinct solutions.}$$