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..


  • $\begingroup$ The answer is not given. $(D)$ is my guess... $\endgroup$ – Ritu Apr 15 '15 at 6:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 15 '15 at 7:12
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Jared Apr 16 '15 at 6:10
  • $\begingroup$ @GerryMyerson I don't get how $m>n$ is an impossible case. Can you explain a little more? $\endgroup$ – Ritu Apr 16 '15 at 9:48
  • 2
    $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.