Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2010 / A / 1

An orthogonal projector sends $x$ to the foot $Px$ of its perpendicular onto the image of a linear map $\mathrm{range}P$. The residual $r=x-Px$ is orthogonal to the entire range, not just to the single vector $Px$. Indeed, for any range vector $Pv$,In particular $\boxed{(Px{)}^T(x-Px)=0}$. The orthogonal projection diagram illustrates the resulting right triangle.

The vector Euclidean norm is $\boxed{\Vert x{\Vert }_2=(x^{T}x{)}^{1/2}=(\sum _i{x}_i^2{)}^{1/2}}$, the ordinary length from the origin. The induced matrix norm isGeometrically this is the largest stretch of a unit vector. A linear map sends the unit sphere to an ellipsoid, possibly degenerate; its largest semiaxis has length $\Vert A{\Vert }_2$. Equivalently the matrix 2-norm is the largest singular value.

The perpendicular decomposition in part (a) gives, by the Pythagorean theorem,Thus an orthogonal projection cannot lengthen a vector and $\boxed{\Vert P{\Vert }_2\le 1}$. Algebraically the cross term vanishes because $P^T(I-P)=P-P^2=0$, giving the same identity directly from the hypotheses. If $P\ne 0$, take a nonzero $x$ in its range; then $Px=x$ and $\Vert P{\Vert }_2=1$. For $P=0$ the norm is zero.

The nullspace is the vector subspace $\boxed{\ker A=\{x\in {\mathbb{R}}^n:Ax=0\}}$. A full real singular value decomposition iswhere $U,V$ are orthogonal matrices and ${\Sigma }_{ij}=0$ for $i\ne j$, with ${\Sigma }_{jj}={\sigma }_j\ge 0$ for $1\le j\le n$. We may order ${\sigma }_1\ge \cdots \ge {\sigma }_n\ge 0$. The columns of $V$ form an orthonormal basis of the input space ${\mathbb{R}}^n$, and the columns of $U$ form one of the output space ${\mathbb{R}}^m$. The positive singular values number exactly the matrix rank.

Let $r$ be the matrix rank, and partition the right singular vectors as $V=(V_r{V}_0)$, with $V_0\in {\mathbb{R}}^{n\times (n-r)}$ consisting of the columns associated with zero singular values. From $Ax=0⟺\Sigma V^{T}x=0$, these columns form an orthonormal basis of the nullspace. Therefore its orthogonal projector isIt acts on the input space ${\mathbb{R}}^n$. Symmetry and idempotence follow from $V_0^T{V}_0=I_{n-r}$. At full column rank it is zero, and at rank zero it is the identity.