# Linear Algebra Proof

If A is a $m\times n$ matrix and $M = (A \mid b)$ the augmented matrix for the linear system $Ax = b$.

Show that either

$(i) \operatorname{rank}A = \operatorname{rank}M$, or
$(ii)$ $\operatorname{rank}A = \operatorname{rank}M - 1$.

My attempt:

The rank of a matrix is the dimension of its range space. Let the column vectors of $A$ be $a_1,\ldots,a_n$. If $\text{rank}\;A = r$, then $r$ pivot columns of $A$ form a basis of the range space of $A$. The pivots columns are linearly independent. For the matrix $M = (A \mid b)$, there are only two cases. Case $(i)$: $b$ is in the range of $A$. Then the range space of $M$ is the same as the range space of $A$. Therefore $\operatorname{rank}M = \operatorname{rank}A$.

I am stuck on how to do case $(ii)$?

-
If b is not in the range of A, the pivot columns together with b are a base for the range of M. – Brian M. Scott Dec 11 '12 at 0:39
@BrianM.Scott so then I can conclude that $rank A= rank M−1$? – diimension Dec 11 '12 at 0:44
That’s right: you know that $b$ is not in the span of the pivot columns of $A$, so you know that those together with $b$ are a linearly independent set spanning the range of $M$, and therefore $\operatorname{rank}M=\operatorname{rank}A+1$. – Brian M. Scott Dec 11 '12 at 0:48
@BrianM.Scott thank you very much Brian! – diimension Dec 11 '12 at 0:49
You’re very welcome. – Brian M. Scott Dec 11 '12 at 0:50

## 1 Answer

Suppose the columns of $A$ have exactly $r$ linearly independent vectors. If $b$ lies in their span, then $\operatorname{rank} A=r=\operatorname{rank} M$. If not, then the columns of $A$ together with $b$ have exactly $(r+1)$ linearly independent vectors, so that $\operatorname{rank} A+1=r+1=\operatorname {rank} M$.

-
Ah I see now, thank you very much! – diimension Dec 11 '12 at 0:46
getting close to 10K, Jasper! ;-) – amWhy Dec 12 '12 at 0:58