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 {\mathop{\rm rank}\nolimits} A + {\mathop{\rm rank}\nolimits} B\).

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

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}{*{20}{c}}{{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}{*{20}{c}}{{C_1}}&{{C_2}}\end{array}} \right)\left( {\begin{array}{*{20}{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} = {\mathop{\rm rank}\nolimits} A + {\mathop{\rm rank}\nolimits} B\), or \({\mathop{\rm rank}\nolimits} \left( {A + B} \right) \le {\mathop{\rm rank}\nolimits} A + {\mathop{\rm rank}\nolimits} B\).

Thus, it is proved that \({\mathop{\rm rank}\nolimits} \left( {A + B} \right) \le {\mathop{\rm rank}\nolimits} A + {\mathop{\rm rank}\nolimits} B\).