\documentclass{amsart}

\usepackage{amsmath}
\usepackage{amssymb}

\input{macros}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\bB}{\mathbb{B}}
\newcommand{\bH}{\mathbb{H}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\ip}[2]{\left\langle #1,\, #2\right\rangle}
\newcommand{\norm}[1]{\left\Vert #1\right\Vert}

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

\noindent
Homework Set 5\hfill Due Friday October 31
\bigskip
\begin{flushleft}
\begin{tabular}{lp{5.5in}}
\kern-.1in{\bf Reading} & Horn \& Johnson, Chapter 1 - 3
\end{tabular}
\end{flushleft}


\begin{enumerate}
\item 
\begin{enumerate}
\item Let $A\in\C^{n\times n}$ be invertible and set
$|\l|_{\max}=\max\{|\l|:\l\in\Sigma(A)\}$,
$|\l|_{\min}=\min\{|\l|:\l\in\Sigma(A)\}$. Show that the condition number of $A$
relative to any submultiplicative norm satisfies $k(A)\ge
|\l|_{\max}/|\l|_{\min}$. (So if this ratio is large, $A$ is
ill-conditioned.)
\item Let $A,B\in\C^{n\times n}$ with $A$ invertible and $B$ singular. Show
that the condition number of $A$ relative to any submultiplicative norm
$\|\cdot\|$ satisfies $k(A)\ge \frac{\|A\|}{\|A-B\|}$. 
\item Use part (b) to show that if $A\in\C^{n\times n}$ is upper triangular
and invertible, then the condition number of $A$ relative to $\|
|\cdot|\|_\infty$ satisfies $k(A)\ge \frac{\| |A|\|_\infty}{\min_{1\le i\le
n}|a_{ii}|}$.
\end{enumerate}
\item Let $A\in\C^{n\times n}$ and suppose that $\l$ is an eigenvalue of $A$
of algebraic multiplicity $1$. Show that $\rank(A-\l I)=n-1$, but not
conversely.
\item 
\begin{enumerate}
\item Let $A\in\C^{n\times n}$ be normal and suppose all eigenvalues of $A$
are real. Show that $A$ is Hermitian.
\item Let $A\in\C^{n\times n}$ be normal and suppose all eigenvalues of $A$
satisfy $|\l|=1$. Show that $A$ is unitary.
\item Show by examples that (a) and (b) both fail if the normality
assumption is reduced to assuming just that $A$ is diagonalizable.
\end{enumerate}
\item 
\begin{enumerate}
\item Let $A, B\in\C^{n\times n}$ and suppose $A$ is invertible. Show that
$AB$ and $BA$ are similar. Show by example that this need not be true if
$A$ and $B$ are both allowed to be singular.
\item Let $A,B\in\C^{n\times n}$ show that $A+\e I$ is invertible for all
sufficiently small $\e>0$. Use part (a) and take limits to show that for
any $A,B\in\C^{n\times n}$, $AB$ and $BA$ have the same characteristic
polynomials. Deduce that $AB$ and $BA$ have the same eigenvalues, including
algebraic multiplicities.
\end{enumerate}
\item If $A,B\in\C^{n\times n}$ are Hermitian, we say that $A\ge B$ if $A-B\in \cH^n_+$,
where $\cH^n_+$ is the set of Hermitian positive semi-definite matrices.
\begin{enumerate}
\item Let $A\in\C^{n\times n}$ be Hermitian and $\a\ge 0$. Show that
$\|A\|\le\a$ iff $-\a I\le A\le\a I$ (where $\|\cdot\|$ is the operator
2-norm).
\item If $A$ is Hermitian and $\a I\le A\le\b I$, and if $p$ is a polynomial
for which $p\ge 0$ on $[\a,\b]$, show that $p(A)\ge 0$.
\item If $A$ is Hermitian and $\a I\le A\le\b I$, and if $p$ is a polynomial
such that $p\ne 0$ on $[\a,\b]$, show that $p(A)$ is invertible.
\end{enumerate}
\item The following describes an iterative procedure, called the
\index{power method}\emph{power method}, for (usually) finding the largest
eigenvalue (in magnitude) and an associated eigenvector for $A\in\C^{n\times
n}$. Although the method applies in a more general setting, assume for
simplicity that the eigenvalues $\l_1,\ldots,\l_n$ of $A\in\C^{n\times n}$
satisfy $|\l_1|>|\l_2|\ge|\l_3|\ge\cdots\ge|\l_n|$ and that $A$ is
diagonalizable. Given $x_0\in\C^n$, define a sequence $\{x_k\}$ in $\C^n$
inductively by $x_{k+1}=\frac{1}{\|x_k\|_2}Ax_k$. Show that for $x_0$ in
a dense open subset in $\C^n$ (actually, the complement of a
hyperplane---identify this set explicitly), the generated sequence $\{x_k\}$
converges to an eigenvector of $A$ corresponding to $\l_1$. Show also that
for $1\le i\le n$, if the $i^{\mathrm{th}}$ component of this eigenvector is
nonzero, then $\lim_{k\to\infty}(Ax_k)_i/(x_k)_i=\l_1$.
\end{enumerate}
\end{document}
