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?

  • 2
    $\begingroup$ Do you mean $P^2 = P$ in the first line? $\endgroup$ – Arthur Dec 17 '16 at 9:47

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$.

  • $\begingroup$ @ValerySaharov In the second proof, if $f_i'=f_i$, then $Ff_i'=f_i=f_i'$ since the columns of $F$ span its image. Otherwise, $Ff_i'=0$ by construction. So, relative to this basis each column of $F$ is either $e_i$ or $0$, which you can then permute into the desired form. $\endgroup$ – amd Dec 18 '16 at 13:17
  • $\begingroup$ @ValerySaharov Yes. $Fe_i=f_i$ since that’s the $i$th column of $F$, so $Ff_i=F^2e_i$. $\endgroup$ – amd Dec 19 '16 at 6:10

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}$$


$$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.