# The number of linearly independent solution of the homogeneous system of linear equations $AX=0$

I came across the following multiple choice question:

The number of linearly independent solution of the homogeneous system of linear equations $AX=0$, where $X$ consists of $n$ unknowns and $A$ consists of $m$ linearly independent rows is

$(A)$ $m-n$ $\space$$(B) m \space$$(C)$ $n-m$ $\space$$(D)$ none of these

I think the answer will be $(D)$ because:

When $m=n$, in this case it would mean a square matrix with all linearly independent rows, which implies unique solution. When $m<n$, it would mean that the rank of the matrix is less than number of unknowns in the system, which would mean infinite solutions and these solutions must be linearly dependent (Am I going right?). When $m>n$, there will be no solution (I am not sure about this one)

I think there is something wrong about my answer because I remember something like: number of linearly independent solutions = number of unknowns - rank, from my Linear Algebra class. But I am not sure how to relate to it here..

Thanks..

• The answer is not given. $(D)$ is my guess... – Ritu Apr 15 '15 at 6:33
• When there are infinitely many solutions, there will be among them some finite number of linearly independent solutions. $m>n$ is impossible, if you think about it right. – Gerry Myerson Apr 15 '15 at 7:12
• I suspect that they want you to discard the trivial solution--which wouldn't be linearly independent of any other solution (so it cannot be included when you do have non-trivial solutions). In this case, I'm think the answer is $n - m$--that is definitely true for $n = m$ and $n = m + 1$. If $A$ has $m$ linearly independent rows it can be put into reduced row echelon form: $\begin{bmatrix}1 & 0 &\dots & 0 & A_{1(n - m)} & A_{1(n - m + 1)} & \dots\\ 0 & 1& \dots & 0 & A_{2(n - m)} & A_{2(n - m + 1)} & \dots \\ \dots \\ 0 & 0 & \dots & 1 & A_{m(n - m)} & A_{m(n - m + 1)}&\dots \end{bmatrix}$ – Jared Apr 16 '15 at 6:10
• @GerryMyerson I don't get how $m>n$ is an impossible case. Can you explain a little more? – Ritu Apr 16 '15 at 9:48
• m = Number of linearly independent rows = number of linearly independent columns, which is at most the number of columns, which is $n$. Thus, $m>n$ is impossible. For $m=n$, the unique solution is the zero vector, which is not linearly independent. – Gerry Myerson Apr 16 '15 at 10:45

When $m=n$, we get unique solution that is trivial and hence linearly dependent. So, we get $0$ linearly independent solution (Here, $n-m=0$).
When $m<n$, we also get non-trivial solution along with the trivial solution. We discard the trivial solution because we want only linearly independent solutions. Since we have $m$ linearly independent rows, the rank of $m \times n$ matrix is $m$. Hence $n-m$ linearly independent solutions
The number of linearly independent rows is equal to number of linearly independent columns. Thus, number of linearly independent rows cannot exceed the number of columns. So, $m>n$ is an impossible case.
The correct option is $(C)$ $n-m$.