# Correct proof? Linear Algebra

Prove that if $A$ and $B$ are matrices of rank $n$, then $AB$ is of rank $n$.

Solution This should be equivalent to proving that the columns $AB$ are linearly independent.

$AB = \begin{pmatrix} \vdots & \vdots & \vdots & \vdots \\ A\vec{b_1} & A \vec{b_2} & \cdots & A\vec{b_n} \\ \vdots & \vdots & \vdots & \vdots \\ & & & \end{pmatrix}$

where $\vec{b_i}$ is the column vector of $B$. Note that since $B$ has rank $n$, $$\sum_{i \in J_n} \sigma_i \vec{b_i} = 0 \mid \sigma_i \in \mathbb{R}$$ iff $\forall i, \, \, \sigma_i = 0$.

Thus, to test if the column vectors of $AB$ are linearly independent, we see that $$\sum_{i \in J_n} A \sigma_i \vec{b_i} = A \big( \sum_{i \in J_n} \sigma_i \vec{b_i} \big) = 0 \mid \sigma_i \in \mathbb{R}$$ iff $\forall i, \, \, \sigma_i = 0$.
Thus, the rank of $AB$ is $n$.

Is this proof sufficient?

You're about 90% there. (For one thing, you need to say "$n \times n$ matrices" in the hypotheses, or something like that!)

At "Thus," you probably want to apply the usual approach to independence: say "Suppose that some linear combination of the columns is zero..." and then prove that the coeffs have to be zero. That looks like this:

Suppose that $\sum_i \sigma_i (Ab_i) = 0$. By linearity of matrix multiplication, this tells us that $\sum_i A (\sigma_i b_i) = 0$, so $A (\sum_i \sigma_i b_i) = 0$.

Now $(\sum_i \sigma_i b_i)$ is a vector whose entries we can call $c_i$. The last equality says that $c_1 A_1 + \ldots + c_n A_n = 0$, where the $A_i$ are the columns of $A$. But since those columns are indepedent, the $c_i$ are all zero.

That means that $(\sum_i \sigma_i b_i)$ is the zero vector. And since the $b_i$ are independent, that means that the $\sigma_i$ are all zero.

So if we have a zero-combination of the columns of $AB$, we've shown the coefficients must be zero. That makes the columns independent.

• Yes he would have to say that the matrices are $n \times n$, see my answer. Although he used $k$ for the number of columns. – Zoltan Zimboras Feb 8 '14 at 4:13
• Yeah...I was trying to get at the essentials of how independence proofs get written rather than the details of how well he copied the exercise from the text. :) But it'd be good if the OP cleaned up the question to be correct, so later readers would get it right. – John Hughes Feb 8 '14 at 4:16
• He cleaned it up, but now my answer does not make sense... with the $k$ and the rest... – Zoltan Zimboras Feb 8 '14 at 4:18
• @John Why is this necessary ? We already know that $\sigma_i = 0$, since we're given $B$ is of rank $n$? – Anthony Peter Feb 8 '14 at 4:19
• @AnthonyPeter: a third alternative proof: It follows directly from the definitions that an $n \times n$ matrix $M$ is of rank $n$ (i.e. full rank) if and only if for any non-zero vector $\vec{v}$ we have that $M\vec{w} \ne \vec{0}$ (where $\vec{0}$ is the zero vector). Now for any non-zero vector $\vec{v}$, consider the vector $\vec{u}=AB \vec{v}$. As $B$ is full rank, we have that $\vec{w}=B\vec{v}$ is a non-zero vector. But we also know that $\vec{u}=A\vec{w}$ (by definition) and since $A$ is full rank, we have that $AB\vec{v}=\vec{u}\ne\vec{0}$; this means that $AB$ have to be of rank $n$ – Zoltan Zimboras Feb 8 '14 at 4:43

Edit This answer refers to the situation when it was still not clear from the question that $A$ and $B$ were $n \times n$ matrices (although this case is also discussed at the end of the answer).

It is not true that if $A$ and $B$ are matrices of rank $n$, then $AB$ is of rank $n$. Consider the following example

$A = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$,

$B = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$,

$AB = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$.

The rank of $A$ is $1$, the rank of $B$ is $1$, but the rank of $AB$ is $0$. What is true is that if $A$ and $B$ are matrices of rank $n$, then $AB$ is of rank less or equal to $n$. Another true statement is this: if $n=k$ and $A$ and $B$ are $k \times k$ matrices (I think you used $k$ for the number of columns), then $AB$ is also of rank $n(=k)$. This follows from the fact that a $k \times k$ matrix has rank $k$ if and only if it is invertible. This would mean that $A$ and $B$ have inverses, which we denote by $A^{-1}$ and $B^{-1}$, respectively. But then (by simple algebra) the matrix $B^{-1}A^{-1}$ would be an inverse of $AB$, hence $AB$ is invertible and thus have rank $k$.

• Maybe the OP is thinking matrices of full rank? – Pedro Tamaroff Feb 8 '14 at 4:08
• @PedroTamaroff Yes, I am.@PedroTamaroff although not explicit in the question in the book. – Anthony Peter Feb 8 '14 at 4:09
• Anthony Peter and @Pedro Tamaroff: Yes, while I was writing the answer. I was also thinking that the question (implicitly) might mean that, so I answered to that version as well. But the notation $k$ for the number of columns was a bit misleading also. (+ Then one could just say "non-singular" matrix or "invertible" matrix or "full rank" matrix instead of rank n matrix.) Anyway, I hope I could help with my answer. – Zoltan Zimboras Feb 8 '14 at 4:17