logo

Proof of the Subadditivity of Matrix Rank: rank(A+B) ≤ rankA + rankB 📂Matrix Algebra

Proof of the Subadditivity of Matrix Rank: rank(A+B) ≤ rankA + rankB

Theorem

The rank of a matrix possesses a quasi-additive property. In other words, for two matrices $A, B$, the following holds. $$ \rank \left( A + B \right) \le \rank A + \rank B $$

Explanation

This theorem is used in the proof of Cochran’s theorem.

Proof 1

Bases for Row Space, Column Space, and Null Space: (a1) Two row equivalent matrices have the same row space, meaning that elementary row operations do not change the row space. (b1) Two row equivalent matrices have the same null space, meaning that elementary row operations do not change the null space.

Let $A '$ and $B '$ be the reduced row echelon forms obtained through Gaussian elimination from $A$ and $B$, respectively. $A '$ has $\rank A$ non-zero row vectors, and $B '$ has $\rank B$ non-zero row vectors. Therefore, $A ' + B '$ has at most $\rank A$ or $\rank B$ non-zero row vectors. Since Gaussian elimination consists solely of elementary row operations, $A + B$ is row equivalent to $A ' + B '$, and its rank satisfies the following inequality. $$ \begin{align*} & \rank \left( A + B \right) \\ =& \rank \left\{ A ' + B ' \right\} \\ =& \max \left( \rank A , \rank B \right) \\ \le & \rank A + \rank B \end{align*} $$


  1. user99680, Show $\operatorname{rank}(A) + \operatorname{rank}(B) \ge \operatorname{rank}(A+B)$, URL (version: 2014-06-29): https://math.stackexchange.com/q/851605 ↩︎