Prove that projection matrix has the same rank as design matrix.

Question

The equation for projection matrix is as follows:

$$\begin{align} \mathrm{P = A\left(A^TA\right)^{-1}A^T} \end{align}$$

Here we want to project onto column space of $\mathrm A$.

How to prove that $\mathrm {rank(P) = rank(A)}$?

Answer 1

Let's prove that left nullspace of $\mathrm{P}$ is equal to left nullspace of $\mathrm{A}$, i.e $\mathrm{N\left(P^T\right) = N\left(A^T\right)}$. Having done that we'll prove that their orthogonal complements, namely $\mathbf{C(P)}$ and $\mathbf{C(A)}$, are equal.

Note that $\mathrm{N\left(P^T\right) = N\left(P\right)}$, since $\mathrm{P}$ is symmetric. Also keep in mind that $\mathrm {P = A\left(A^TA\right)^{-1}A^T}$.

1. $\mathrm{A^Tx = 0 \implies \text{multiply by } A\left(A^TA\right)^{-1} \implies A\left(A^TA\right)^{-1}A^Tx = 0 \implies N\left(A^T\right) \subseteq N\left(P^T\right)}$.

2. $\mathrm {A\left(A^TA\right)^{-1}A^Tx = 0 \implies \text{multiply by } A^T \implies A^Tx = 0 \implies N\left(P^T\right) \subseteq N\left(A^T\right)}$.

3. $\mathrm {N\left(P^T\right) = N\left(A^T\right)}$.

4. $\mathrm {C\left(P\right) = C\left(A\right)}$.

5. $\mathrm{rank\left(P\right) = rank\left(A\right)}\ \square$.

---

In step 2 when we multiplied $\mathrm {A\left(A^TA\right)^{-1}A^Tx = 0}$ by $\mathrm {A^T}$ on the left we got $\mathrm {\underbrace{{\color{red}{A^TA}}{\color{blue}{\left(A^TA\right)^{-1}}}}_{\text{Identity matrix}}A^Tx = 0}$.

Answer 2

Here's a more direct approach.

Obviously we have $\text{Col}(P) \subseteq \text{Col}(A)$. To prove reverse inclusion, let $y\in \text{Col}(A)$. Find $x$ so that $y=Ax$. Then $$\begin{eqnarray*}Py&=&A(A^TA)^{-1}A^Ty \\&=&A(A^TA)^{-1}(A^TA)x \\ &= &Ax \\&=&y \\ &\in &\text{Col}(P)\end{eqnarray*}$$ This shows $A$ and $P$ have the same column space and we're done.