Math 6610 • Analysis of Numerical Methods I

{Singular Value Decomposition}
The singular value decomposition (SVD) of a real \(m\times n\) matrix \(A\) (you may
assume \(m\ge n\)) is defined by
\[
  A=U\Sigma V^T
\]
where \(U\) is \(m\times m\) and orthogonal. \(\Sigma\) is \(m\times n\) and diagonal. \(V\) is
\(n\times n\) and orthogonal.

\textbf{a)} Prove that every matrix \(A\) has an SVD.

\textbf{b)} Use the SVD of \(A\) to prove the famous result from linear algebra that
the null space of \(A\) is the orthogonal complement of the range of \(A^T\) (the adjoint
of \(A\)).

\textbf{c)} For a nonsingular \(m\times m\) matrix \(A\), the solution to the system
\(Ax=b\) can be expressed in terms of \(A\)'s SVD. Write
\(b=\sum_{j=1}^m c_j u_j\) where \(u_j\) is the \(j\)th column of \(U\). Then the solution
\(x\) is
\[
  x=\sum_{j=1}^m \frac{c_j}{\sigma_j}v_j
\]
where \(v_j\) is the \(j\)th column of \(V\) and \(\sigma_j\) is the \(j\)th singular value.
Verify this formula. Consider the special case \(b=u_1\). What perturbation
\(\delta b\) in \(b\), with \(\lVert\delta b\rVert_2=1\), causes the largest change
\(\delta x\) in the solution \(x\)?