How to prove that $rankA + rankA^{T} \geq rank(A + A^{T}) $?

Question

I can see that this inequality means that adding together columns with rows of a matrix can't increase number of linearly independent rows or columns, but I don't really see why. If $A$ has $n$ linearly independent rows (and columns) then $A^{T}$ also has $n$ linearly independent rows (and columns). What exactly happens when we're adding them together?

Answer 1

We have $$\text{range }(A + B) \subseteq \text{range }(A) + \text{range }(B),$$ because every vector in the range of $A + B$ can be written as the sum of a vector in the range of $A$ plus a vector in the range of $B$ like so: $$(A + B)v = Av + Bv.$$ Both $\text{range }(A + B)$ and $\text{range }(A) + \text{range }(B)$ are linear subspaces, so it follows that $$\dim \text{range }(A + B) \leq \dim (\text{range }(A) + \text{range }(B)) \leq \dim \text{range }A + \dim \text{range }B.$$