Past exam of the options II course of the University of Oxford / 2005 / P

The elementary elimination step replaces row $i$ by row $i$ minus a multiple $m_{ij}$ of an earlier pivot row $j$. With coordinate vectors $e_i$, its premultiplication matrix isand its inverse is $I+m_{ij}{e}_i{e}_j^T$, since $(e_i{e}_j^T{)}^2=0$. Choose $m_{ij}$ as the current entry below the pivot divided by the current pivot. Required pivots are assumed nonzero, consistently with elimination without row interchanges.

For dimension 4, first eliminate positions $(2,1),(3,1),(4,1)$, then $(3,2),(4,2)$, then $(4,3)$. ThusThe rightmost operation acts first, and every multiplier is computed from the matrix at its own stage. For general $n$, the numbers of eliminations in successive columns are $n-1,n-2,\dots ,1$, totaling $n(n-1)/2$; a zero multiplier simply gives an identity operation.

The product $E$ is unit lower triangular and $U=EA$ is upper triangular. Its inverse $L=E^{-1}$ is unit lower triangular, soThe stored multiplier in position $(i,j)$ is the corresponding subdiagonal entry of $L$, as follows by reversing the pivot-row subtractions column by column.

If $A$ is upper Hessenberg, only the first subdiagonal can be nonzero below the diagonal. At stage $j$ only position $(j+1,j)$ needs elimination. Subtracting row $j$ cannot create lower entries further down because its entries before its pivot are already zero. Hence only $n-1$ operations are needed. The inverse factors occur in increasing column order, and their cross products vanish, givingwhich is lower bidiagonal; $U$ is upper triangular, possibly dense above its diagonal.

If the Hessenberg matrix is also symmetric, it is tridiagonal. At each elimination step the pivot row has no entries past its immediate superdiagonal, so the updated matrix retains that upper bandwidth. Thus $L$ is lower bidiagonal and $U$ is upper bidiagonal, with at most two nonzero entries in each row, as required.

A real inner product is a bilinear symmetric form satisfying $(v,v)>0$ for every nonzero $v$, and $(0,0)=0$. Its norm is $\Vert v\Vert =\sqrt{(v,v)}$. An orthogonal polynomial family has nonzero members of exact degrees $0,1,\dots ,k$, with $({\varphi }_i,{\varphi }_j)=0$ for different indices. Exact degree is part of this definition; merely belonging to the indicated polynomial vector spaces would not suffice.

Distinct degrees make ${\varphi }_0,\dots ,{\varphi }_{\ell -1}$ linearly independent. There are $\ell$ of them in the $\ell$-dimensional space ${\Pi }_{\ell -1}$, so they form a basis. Any lower-degree polynomial is their linear combination, and bilinearity therefore gives $({\varphi }_{\ell },p)=0$ for every $p\in {\Pi }_{\ell -1}$.

Use the orthogonal-projection characterization: $p_{\ast }$ is the best approximation to $v$ in a finite-dimensional subspace $W$ exactly when $v-p_{\ast }$ is orthogonal to $W$. Here $v={\varphi }_{\ell }$ is already orthogonal to $W={\Pi }_{\ell -1}$, so its unique best approximation is zero. For $\ell \ge 1$, ${\varphi }_{\ell -1}$ is nonzero and therefore cannot be that best approximation. Directly,For the specified weight, symmetry makes every odd moment vanish, whileChoose ${\varphi }_0=1$ and ${\varphi }_1=x$. A monic quadratic orthogonal to $x$ has no linear term by symmetry, and orthogonality to 1 requires $\int |x|(x^2-c)dx=1/2-c=0$. Thus a valid answer isThe weight vanishes only at one point, so a nonzero polynomial has positive squared norm; the form is indeed positive definite on the polynomial vector space. Nonzero rescalings of individual family members give equally valid unnormalized answers.