Question

Question: Exercises 12-17 develop properties of rank that are sometimes needed in applications. Assume the matrix $A$ is $m\times n$.

16. If $A$ is an $m\times n$ matrix of rank$r$, then a rank factorization of $A$ is an equation of the form $A=CR$, where $C$ is an $m\times r$ matrix of rank$r$ and $R$ is an $r\times n$ matrix of rank $r$. Such a factorization always exists (Exercise 38 in Section 4.6). Given any two $m\times n$ matrices $A$ and $B$, use rank factorizations of $A$ and $B$ to prove that rank$\left(A+B\right)\le \mathrm{rank}A+\mathrm{rank}B$.

(Hint: Write $A+B$ as the product of two partitioned matrices.)

Short answer

It is proved that $\mathrm{rank}\left(A+B\right)\le \mathrm{rank}A+\mathrm{rank}B$.

Step-by-step solution

Show that $\mathrm{rank}\left(A+B\right)\le \mathrm{rank}A+\mathrm{rank}B$

Consider rank$A=r_1$ and rank$B=r_2$. Rank factorization of $A$ and $B$ are $A=C_1{R}_1$ and $B=C_2{R}_2$, where $C_1$ is $m\times r_1$ with rank$r_1$, $C_2$ is $m\times r_2$ with rank$r_2$, $R_1$ is $r_1\times n$ with rank$r_1$, $R_2$ is $r_2\times n$ with rank$r_2$.

By stacking $R_1$ over $R_2$, create a $m\times \left(r_1+r_2\right)$ matrix $C=\left(\begin{array}{cc}{C}_1& C_2\end{array}\right)$ and a $\left(r_1+r_2\right)\times n$ matrix $R$.

$\begin{array}{c}A+B=C_1{R}_1+C_2{R}_2\\ =\left(\begin{array}{cc}{C}_1& C_2\end{array}\right)\left(\begin{array}{c}{R}_1\\ R_2\end{array}\right)\\ =CR\end{array}$

The matrix $CR$ is a product, so according to exercise 12, its rank cannot exceed the rank of either of its factors. The rank of $C$ cannot exceed $r_1+r_2$ because $C$ has $r_1+r_2$. Similarly, as matrix $R$ has $r_1+r_2$ rows, then its rank cannot exceed $r_1+r_2$.

Therefore, the rank of $A+B$ cannot exceed $r_1+r_2=\mathrm{rank}A+\mathrm{rank}B$, or $\mathrm{rank}\left(A+B\right)\le \mathrm{rank}A+\mathrm{rank}B$.

Thus, it is proved that $\mathrm{rank}\left(A+B\right)\le \mathrm{rank}A+\mathrm{rank}B$.