\documentclass{amsart}

\usepackage{amsmath}
\usepackage{amssymb}

\input{macros}

\begin{document}
\noindent
\Large Math 554\hfill Autumn 2014

\noindent
Homework Set 7\hfill Due Monday November 17
\bigskip

%\begin{flushleft}
%\begin{tabular}{lp{5.5in}}
%\kern-.1in{\bf Reading} & Horn \& Johnson, Sections 7.0--7.4, 7.7\\
%&Skim through Horn \& Johnson, Sections 6.0--6.3
%\end{tabular}
%\end{flushleft}


\begin{enumerate}
\item Let $A\in\C^{n\times n}$ have polar form $A=PU$. Show that $A$ is
normal iff $PU=UP$.
\item Find the SVD for the matrix $A=\left[\begin{array}{ccc}
10&0&0\\ 0&3&4\end{array}\right]$.
\item Given $A\in\C^{m\times n}$ and $\e>0$, show that there exists
$B\in\C^{m\times n}$ of full rank (i.e., $\rank(B)=\min(m,n)$) so that
$\|A-B\|<\e$, where $\|\cdot\|$ is the Euclidean operator norm.
\item
\begin{enumerate}
\item Prove the following minimax characterization of the singular values
$\s_1\ge \cdots\ge\s_n$ of $A\in\C^{m\times n}$: for $1\le k\le n$,
$$\s_k=\min_{S_{n-k+1}}\left(\max_{x\ne 0, x\in
S_{n-k+1}}\frac{\|Ax\|}{\|x\|}\right),$$ where the min is taken over all
subspaces $S_{n-k+1}$ of dim.\ $n-k+1$, and $\|\cdot\|$ denotes the
Euclidean norm. (Note: Here $\s_1\ge\cdots\ge\s_n$, whereas in
Courant-Fischer, we had $\l_1\le\cdots\le\l_n$.)
\item Use (a) to prove that if $A, B\in\C^{m\times n}$ have singular values
$\s_1\ge\cdots\ge\s_n$ and $\t_1\ge\cdots\ge\t_n$ then for $1\le k\le n$
$$|\s_k-\t_k|\le\|A-B\|,$$ where $\|\cdot\|$ is the Euclidean operator norm.
\item Let $A\in\C^{m\times n}$ have rank $r>1$, and suppose $1\le s<r$.
Consider the problem of minimizing $\|A-B\|$ (Euclidean operator norm) over
all matrices $B\in\C^{m\times n}$ of rank $s$. Show that the minimum value
is $\s_{s+1}$, and identify a matrix $B$ which achieves the min.
\end{enumerate}
\item Problem 4(b) shows that if a matrix is perturbed slightly, then its
singular values can change at most by the (Euclidean operator) norm of the
perturbation.
\begin{enumerate}
\item Show that this result fails dramatically for eigenvalues in general by
considering the perturbation $$A_\e=\left[\begin{array}{cccc}0&1&&0\\
\vdots&\ddots&\ddots \\
0&&& 1\\
\e & 0 & \cdots & 0 \end{array}\right]$$ of $A_0\in\C^n$. Find the
eigenvalues of $A_\e$ and compare with the eigenvalues of $A_0$ when $\e$ is
small. For example, let $n=10$ and take $\e=10^{-10}$. 
\item Compute the singular values of $A_\e$ and check that 4(b) really does
hold in this case.
\end{enumerate}
%\item
%(a) Use the LU-factorization to compute bases for the four fundamental
%subspaces associated with the matrix
%$$
%A=\begin{bmatrix}
%1&2&3&1&8&4\\
%-1&0&1&-2&-8&-3\\
%2&2&5&1&15&7\\
%1&2&6&-1&7&4
%\end{bmatrix}
%$$
%
%\noindent
%(b) Use the solution to part (a) to completely describe the set
%of solutions to the system 
%$$
%Ax=\begin{pmatrix} 2\\ 0\\ 5\\ 5\end{pmatrix}\ .
%$$
\item (Cholesky Factorization)
Suppose $A\in \C^{n\times n}$ is Hermitain positive definite.
\begin{enumerate}
\item
Show that $A$ can be written in factored form as
$A=LDL^H$ where $L$ is unit lower triangular and $D$ is
diagonal with positive entries. This factorization is called
the {\it Cholesky factorization} of $A$. 
Here are some hints to get you going.
\begin{enumerate}
\item Show that $A_{11} > 0$.
\item Let $L_1$ be the first Gaussian elimination matrix in our
algorithm for computing the LU-factorization of $A$.
Decribe the block structure of the matrix $L_1^{-1}AL_1^{-H}$.
\end{enumerate}
\item
Show that a Hermitian matrix $A\in\C^{n\times n}$ is positive
semi-definite if and only if there is a matrix $B\in \C^{n\times n}$
such that $A=BB^H$.
\item
Suppose the Hermitian matrix $A$ is positive semi-definite.
Use the ideas behind Gaussian elimination with pivoting to
construct a permutation matrix $P$, diagonal matrix $D$, 
and a lower triangular matrix $L$ such that $A=PLDL^HP^H$.
\end{enumerate}
\item
Let $A\in\C^{n\times n}$ and let $\l\in\s(A)$ with associated
eigenvector $v$. Let $b\in\C^n$ be any vector for which
$\langle v,\, b\rangle\ne 0$. Consider solving the equation
$(A-\l I)x=b$ numerically (i.e, subject to numerical error),
and let $\bar x$ be the numerically computed solution.
Give an arguement that explains why the vector 
$v=\bar x/\Vert \bar x\Vert$ is an excellent approximation
to an eigenvector associated with the eigenvalue $\l$. 

\noindent
To illustrate this problem try the following Matlab commands:
\begin{eqnarray*}
A&=&10*(0.5*ones(50,50)-rand(50,50));\\
ev&=&eig(A);\\
b&=&10*(0.5*ones(50,1)-rand(50,1));\\
x&=&(A-ev(1)*eye(50,50))\backslash b;\\
xn&=&x/norm(x,2);\\
r&=&(A-ev(1)*eye(50,50))*xv;\\
&&norm(r)
\end{eqnarray*}
The first command generates a random $50\times 50$ matrix
with entries between $-10$ and $10$. The semicolon at the end
of each line prevents Matlab from printing the results of the command 
line. The final line will print the $2$-norm of the residual
vector $r$. The norm of $r$ should be on the order of $10^{-13}$
indicating that $v$ is an eigenvector for the eigenvalue
$ev(1)$ within the numerical precision of the floating point
computations used in Matlab (14 decimal places). 
When you execute the command
$$x=(A-ev(1)*eye(50,50))\backslash b;$$
Matlab will send a warning message telling you about the near
singularity of the matrix $(A-ev(1)*eye(50,50))$. The
warning is to be expected in this case (why?) so just ignore it.
What happens when you repeat the last four of the Matlab 
commands given above but with the vector $b$ replaced by the 
eigenvector approximation $v$?  In particular, what should
happen to the new residual norm $\Vert r\Vert$?
\end{enumerate}
\end{document}

\item (QR factorization by Householder Transformations) For simplicity, we
consider only the real case. A matrix $A\in\R^{n\times n}$ of the form
$Q=I-2\frac{yy^T}{y^Ty}$ where $y\in\R^n$, $y\ne 0$ is called an
\index{elementary reflector}\index{reflector!elementary}\emph{elementary
reflector} or a \index{Householder
Transformation}\index{Transformation!Householder}\emph{Householder
Transformation} (H.T.) If $u=y/\|y\|_2$, then $\|u\|_2=1$ and $Q=I-2uu^T$.
Clearly $Q$ is symmetric and orthogonal, so $Q=Q^T=Q^{-1}$. 
\begin{enumerate}
\item If $Q=I-2uu^T$ (where $\|u\|_2=1$) is a H.T., show that $Qu=-u$ and
$Qz=z$ for $z\in\{u\}^\perp$. (If $x\in\R^n$, $x=\a u+z$ for some $\a\in\R$
and $z\in\{u\}^\perp$, so $Qx=-\a u+z$ for the reflection of $x$ through
$\{u\}^\perp$.)
\item Given $v\ne w\in\R^n$ with $\|v\|_2=\|w\|_2$, show $\exists$ a H.T.
$Q$ for which $Qv=w$. (Hint: Try $y=v-w$.)
\item Given $v\in\R^n$< $v\ne 0$, choose $\s=1$ if $v_1\ge 0$ and $\s=-1$ if
$v_1<0$. Show that the H.T. $Q$ with $y=v+\s\|v\|_2e_1$ maps $v$ into a
multiple of $e_1$. (The choice of $\s$ is for numerical reasons: if $v$ is
nearly a multiple of $e_1$, choosing the other sign gives cancellation error
in computing $y$.)
\item Given $v\in\R^n$, $v\ne 0$, with $v_1=\cdots=v_{k-1}=0$, find a H.T.
$Q$ for which $Qv$ is a multiple of $e_k$, and $Qe_j=e_j$ for $1\le j\le
k-1$. (There are two choices; choose the one which avoids cancellation
error.)
\item Suppose $A\in\R^{m\times n}$ (with $m\ge n$) has full rank (i.e.,
$\rank A=n$). Use (c) to find a H.T. $Q_1\in\R^{m\times m}$ for which the
first column of $Q_1A$ is a multiple of $e_1$. Then use (d) inductively to
find H.T. $Q_2, \cdots, Q_{n-1}$ (and $Q_n$ if $m>n$) for which, for each
$k$, $Q_k\cdots Q_1A$ has zeroes below the diagonal in the first $k$
columns. Let $Q^T=Q_{n-1}\cdots Q_1$ if $m=n$, $Q^T=Q_n\cdots Q_1$ if $m>n$.
Conclude that $Q^TA\equiv R=\left[\begin{array}{c}\widetilde R\\
0\end{array}\right]\in\R^{m\times n}$, where $\widetilde R\in\R^{n\times n}$
is upper triangular, and thus $A=QR$. Show also that $\widetilde R$ is
invertible.
\item Show that the condition numbers (with respect to the Euclidean
operator norm) of $A^T\in\R^{n\times n}$ and $\widetilde R\in\R^{n\times n}$
(where $A\in\R^{m\times m}$ has rank $n$) satisfy $k(A^TA)=k(\widetilde
R)^2$. (Thus solving the least squares problem $\min\{b-Ax\|^2_2$ using the
QR factorization of $A$ yields a linear system (with matrix $\widetilde R$)
which is better conditioned than the normal equations.)
\end{enumerate}
\end{enumerate}
\end{document}
