Past exam of the options II course of the University of Oxford / 2013 / P4

A real square matrix is orthogonal when $Q^{T}Q=I$, equivalently when its columns form an orthonormal basis. Taking determinants gives $(\det Q{)}^2=1$, soIn particular it is invertible with inverse $Q^T$ and preserves the Euclidean norm.

A QR decomposition is $\boxed{A=QR}$ with $Q$ orthogonal and $R$ upper triangular. One algorithm for computing it is Householder reflection reduction; a sequence of such reflections produces a QR factorization. The diagonal of $R$ may include zero when $A$ is singular, and no nonsingularity assumption is needed here.

Comparing the $j$th columns of $A=QR$ gives $a_j=Q{r}_j$. ThusTaking nonnegative square roots proves $\boxed{\Vert a_j\Vert =\Vert r_j\Vert }$. This is simply norm preservation by an orthogonal matrix.

Use a QR factorization, whose existence is supplied. Since $|\det Q|=1$ and $R$ is triangular,Each diagonal entry is one component of its column, so $|r_{jj}|\le \Vert r_j\Vert =\Vert a_j\Vert$. Multiplication yields Hadamard determinant inequality:The argument includes singular matrices, since a zero diagonal factor makes the determinant zero.

Every column has $n$ entries of magnitude at most one, so $\Vert a_j{\Vert }^2\le n$. Substituting in part (d) givesThe bound comes from the maximum allowed column lengths, together with Hadamard's inequality.