Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 5

For nonzero $x$, let $\varphi$ be its angle to the unit vector $q_1$. The scalar projection on the oriented $q_1$ axis is $\Vert x\Vert \cos \varphi$. Since $\Vert q_1\Vert =1$, the dot product identity gives $q_1^{T}x=\Vert x\Vert \cos \varphi$. Multiplying that signed scalar by $q_1$ places the foot at $p=(q_1^{T}x)q_1$.

The residual is perpendicular to the axis, because $q_1^T(x-p)=q_1^{T}x-(q_1^{T}x)(q_1^T{q}_1)=0$. An obtuse angle gives a negative scalar and a foot on the negative side of the line; $x=0$ has projection zero without needing an angle.

The first panel is a constructed geometric illustration. The second illustrates the directional stretch used later in Question 6.

Associativity of matrix multiplication identifies $(q_i^{T}x)q_i=q_i(q_i^{T}x)=(q_i{q}_i^T)x$. Thus each matrix $P_i=q_i{q}_i^T$ has the required action and $x={\sum }_i{P}_{i}x$.

Consequently $({\sum }_i{P}_i-I_n)x=0$ for every $x$. Taking $x$ successively as the standard basis vectors shows that every column of this difference is zero. Hence ${\sum }_{i=1}^n{P}_i=I_n$. Equality on one selected vector would not suffice; here it holds on all vectors.

Using the unit length of $q_i$,Then ordinary matrix expansion gives $(I_n-P_i{)}^2=I_n-2P_i+P_i^2=I_n-P_i$. Both $P_i$ and its complementary matrix are projectors. The second calculation in fact holds for every idempotent matrix, without requiring the matrix to equal its transpose.

Take $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$. It has exactly two nonzero entries, both one, but $A^2=I_2\ne A$. Thus it is not an idempotent matrix. Its being an orthogonal matrix does not make it an orthogonal projector.

Prove both inclusions. If $v$ belongs to the column space of $I-P$, then $v=(I-P)u$ for some $u$ and $Pv=(P-P^2)u=0$. Thus $v\in \mathcal{N}(P)$.

Conversely, if $Pv=0$, then $v=(I-P)v$, which explicitly writes $v$ as an image of a linear map under $I-P$. Hence $v\in \mathcal{C}(I-P)$. The two inclusions prove $\mathcal{N}(P)=\mathcal{C}(I-P)$. No orthogonality assumption was used.

Set $Q=I-P$. Since $Q^2=I-2P+P^2=I-P=Q$, the previous result applies to this projector and gives $\mathcal{N}(Q)=\mathcal{C}(I-Q)$. Substituting $Q=I-P$ proves $\mathcal{N}(I-P)=\mathcal{C}(P)$. These are the kernel-image identities for complementary projectors.

For a sum of mutually orthogonal projectors, orthonormality gives $q_i^T{q}_j=0$ for $i\ne j$ and one for $i=j$. Therefore $P_i{P}_j=q_i(q_i^T{q}_j)q_j^T$ equals zero for different indices and $P_i$ for equal indices. Expanding the finite sum yieldsThus every stated partial sum is a projector. Its image of a linear map is the span of the first $k$ orthonormal set of vectors; arbitrary sums of idempotent matrices would not have this conclusion.

The image of a linear map of $P_1$ is exactly the one-dimensional span of $q_1$: its formula always returns a multiple of $q_1$, and $P_1{q}_1=q_1\ne 0$. Hence $\mathrm{rank}(P_1)=1$.

The rank-nullity theorem gives $\dim \mathcal{N}(P_1)=n-1$. Since $\mathcal{C}(I_n-P_1)=\mathcal{N}(P_1)$ by (e)(i), $\mathrm{rank}(I_n-P_1)=n-1$. This includes the case $n=1$, where the complementary projector is zero.