Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the system of linear equations $A\bf{x}=\bf{b}$ where $A$ is an $m\times n$ matrix with $m<n$ and suppose that the system has infinitely many solutions. I want to know under what circumstances the rows of $A$ would be linearly dependent? I know that, if the rank($A$) is less than $m$, it is possible. Is there anything else?

share|cite|improve this question
You misread Arturo's answer: the system having more than one solution implies that the rank of $A$ is $\lt n$. – Did Feb 17 '12 at 14:00
Yes, sorry, this not exactly what I intended to ask. I ll modify the question accordingly. – Ashok Feb 17 '12 at 14:16
up vote 2 down vote accepted

There is a theorem of linear algebra: For any $m \times n$ matrix $A$,

$$ \operatorname{rank}(A) + \operatorname{nullity}(A) = n,$$

or in terms of the system of equations $A\mathbf{x} = \mathbf{0}$,

$$ \textrm{(number of independent equations)} + \textrm{(number of independent parameters in the solution)} = \textrm{(number of columns of $A$)} $$

At any rate, if $A\mathbf{x} = \mathbf{b}$ has more than one solution, then so will the system $A\mathbf{x} = \mathbf{0}$, meaning that $\operatorname{nullity}(A) > 0$. But this only shows that $\operatorname{rank}(A) < n$. As @Jyrki Lahtonen stated in his answer, there are no restrictions on $\operatorname{rank}(A)$ with respect to $m$, the number of rows.

[added after question was edited]

For the case $m < n$, we certainly know $\operatorname{rank}(A) \leq m$. You are asking under what conditions the rows must be dependent. That condition is exactly equivalent to $\operatorname{rank}(A) < m$. And we can say more, in terms of the original system. Using the rank formula above, $\operatorname{rank}(A) = n - \operatorname{nullity}(A)$. So $\operatorname{rank}(A) < m$ forces $\operatorname{nullity}(A) > n - m$. In practical terms, the condition that $A$ has dependent rows is equivalent to the condition that there are more independent paramaters in the solution than the difference of rows and columns.

Hope this helps!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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