Proof that a projection matrix is similar to a fragment of the identity matrix

Question

If $P$ is projection matrix, i. e., $P^2 = P$, then it is similar to a matrix of the type:

$$ \left( \begin{array}{cc} I_m & 0 \\ 0 & 0 \end{array} \right)$$

where $I_m$ is the identity matrix with $m$ elements.

I have problems understanding the second proof of this fact here on page 6. In particular, they construct by induction a sequence of column vectors $v_1, \dots, v_n$ such that $v_i = p_i \lor e_i - p_i$ where $p_i$ is the $i$th column of $P$ and $e_i$ is the $i$th canonical basis vector.

Then, they show $P v_i = v_i \lor P v_i = 0$.

How is that?

Answer 1

Recall that the columns of a transformation matrix are the images of the basis. Following the paper, where the projection matrix is denoted by $F$, if we choose the first $m$ columns of the matrix $P$ to be a basis for $\operatorname{im}F$ and the rest a basis for $\ker F$, then $P^{-1}FP$, which is a change of basis operation on $F$, will have the required form.

The columns of $F$ span $\operatorname{im}F$, so in particular, $f_i\in\operatorname{im}F$, so $F(e_i-f_i)=Fe_i-Ff_i=Fe_i-f_i$. $Fe_i$ is just the $i$th column of $F$, though, so $F(e_i-f_i)=0$ and thus $e_i-f_i\in\ker F$. (Equivalently, $I-F$ is a projection onto $\ker F$, with kernel $\operatorname{im}F$.) The construction in the second proof thus ends up replacing “redundant” columns of $F$ with linearly independent elements of $\ker F$. At the end, the $f_i$ that weren’t replaced form a basis for $\operatorname{im}F$, and the replacement columns form a basis for $\ker F$.

Answer 2

Given a matrix $\mathrm A \in \mathrm R^{m \times n}$, let its SVD be

$$\mathrm A = \mathrm U \Sigma \mathrm V^{\top} = \begin{bmatrix} \mathrm U_1 & \mathrm U_2\end{bmatrix} \begin{bmatrix} \hat\Sigma & \mathrm O\\ \mathrm O & \mathrm O\end{bmatrix} \begin{bmatrix} \mathrm V_1^{\top}\\ \mathrm V_2^{\top}\end{bmatrix}$$

where the zero matrices may be empty. The projection matrix that projects onto the column space of $\mathrm A$ is

$$\mathrm P_{\mathrm A} := \mathrm A (\mathrm A^{\top} \mathrm A)^+ \mathrm A^{\top}$$

where $(\mathrm A^{\top} \mathrm A)^+$ is the pseudoinverse of $\mathrm A^{\top} \mathrm A$. Hence,

$$\begin{array}{rl} \mathrm P_{\mathrm A} &= \mathrm A (\mathrm A^{\top} \mathrm A)^+ \mathrm A^{\top}\\ &= \mathrm U \Sigma \mathrm V^{\top} (\mathrm V \Sigma^{\top} \mathrm U^{\top} \mathrm U \Sigma \mathrm V^{\top})^+ \mathrm V \Sigma^{\top} \mathrm U^{\top}\\ &= \mathrm U \Sigma \mathrm V^{\top} \mathrm V (\Sigma^{\top} \Sigma)^+ \mathrm V^{\top} \mathrm V \Sigma^{\top} \mathrm U^{\top}\\ &= \mathrm U \Sigma (\Sigma^{\top} \Sigma)^+ \Sigma^{\top} \mathrm U^{\top}\\\end{array}$$

where

$$\Sigma (\Sigma^{\top} \Sigma)^+ \Sigma^{\top} = \begin{bmatrix} \hat\Sigma & \mathrm O\\ \mathrm O & \mathrm O\end{bmatrix} \begin{bmatrix} \hat\Sigma^{-2} & \mathrm O\\ \mathrm O & \mathrm O\end{bmatrix} \begin{bmatrix} \hat\Sigma & \mathrm O\\ \mathrm O & \mathrm O\end{bmatrix} = \begin{bmatrix} \mathrm I & \mathrm O\\ \mathrm O & \mathrm O\end{bmatrix}$$

Thus, we conclude that $\mathrm P_{\mathrm A}$ is similar to $\begin{bmatrix} \mathrm I & \mathrm O\\ \mathrm O & \mathrm O\end{bmatrix}$

$$\mathrm P_{\mathrm A} = \begin{bmatrix} \mathrm U_1 & \mathrm U_2\end{bmatrix} \begin{bmatrix} \mathrm I & \mathrm O\\ \mathrm O & \mathrm O\end{bmatrix} \begin{bmatrix} \mathrm U_1^{\top}\\ \mathrm U_2^{\top}\end{bmatrix} = \mathrm U_1 \mathrm U_1^{\top}$$

because $\mathrm U = \begin{bmatrix} \mathrm U_1 & \mathrm U_2\end{bmatrix}$ is orthogonal.