Math 6610 • Analysis of Numerical Methods I

{Singular Value Decomposition}
The \textit{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^{\text{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^{\text{th}}\) column of \(V\) and \(\sigma_j\) is the
\(j^{\text{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\)?