
\documentclass[11pt]{article}
%\baselineskip 16pt
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}

\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.5in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\def\qed{\hfill $\Box$\medskip}



\def\IC{{\mathbb C}}
\def\ID{{\mathbb D}}
\def\IR{{\mathbb R}}
\def\IZ{{\mathbb Z}}
\def\ZZ{{\IZ}}
\def\IF{{\mathbb F}}
\def\IQ{{\mathbb Q}}
\def\IN{{\mathbb N}}
\def\tr{{\mathrm tr}\,}
\def\Sp{{\mathrm Sp}\,}
\def\Ev{{\mathrm Ev}\,}
\def\rank{{\rm rank}\,}
\def\conv{{\rm conv}\,}
\def\diag{{\rm diag}\,}
\def\bD{{\bf D}}
\def\bW{{\bf W}}
\def\ba{{\bf a}}
\def\cS{{\mathcal S}}
\def\cT{{\mathcal T}}
\def\cN{{\mathcal N}}
\def\cU{{\mathcal U}}
\def\cM{{\mathcal M}}
\def\cH{{\mathcal H}}
\def\cR{{\mathcal R}}
\def\cH{{\mathcal H}}
\def\cF{{\mathcal F}}
\def\cL{{\mathcal L}}
\def\cP{{\mathcal P}}
\def\cV{{\mathcal V}}
\def\cK{{\mathcal K}}
\def\BH{{\cB(\cH)}}
\def\SH{{\cS(\cH)}}
\def\FH{{\cF(\cH)}}
\def\KH{{\cK(\cH)}}
\def\re{{\rm Re}\,}
\def\im{{\rm Im}\,}
\def\cl{{\bf cl}\,}
\def\span{{\rm span}\,}
\def\la{{\langle}}
\def\ra{{\rangle}}
\def\vec{{\rm vec}}

\def\bV{{\mathbf V}}
\def\bP{{\mathbf P}}
\def\bA{{\mathbf A}}
\def\bB{{\mathbf B}}
\def\bF{{\mathbf F}}
\def\bmu{{mathbf \mu}}
\def\red{\color{red}}
\def\blue{\color{blue}}
\def\green{\color{green}}
\def\pink{\color{pink}}
\def\grey{\color{dark}}


\begin{document}
\noindent
{\bf Math 309 Intermediate Linear Algebra \quad Exam 2} 
{\hfill Name: \underbar{\ \hskip 1.8in \ }

\medskip
Send your solution to ckli@math.wm.edu
 by 11:59 p.m.\ April 7.  
 
Both handwritten and typed solution
will be accepted.


\medskip\noindent
{\bf 1.} Let 
$$S = \begin{bmatrix} 3 & -2 \cr -2 & 3 \cr\end{bmatrix}
\quad \hbox{ and } \quad
M = \begin{bmatrix}1 & 0 \cr 0 & 4 \end{bmatrix}.$$

(a) Compute the generalized eigenvalues 
$\lambda_1, \lambda_2$ and generalized eigenvectors 
$x_1, x_2$ such that 

\medskip
\centerline{$(S - \lambda_j M)x_j$ for $j = 1, 2$.}
\medskip
(b) Show that $x_1^T M x_2 = 0$.

\medskip
(c) Change $M$ to $M = \begin{bmatrix}1 & 0 \cr 0 & 0 \end{bmatrix}.$
Show that $(S-\lambda M)$ has an eigenvalue $\infty$, 

\quad and 
the two generalized eigenvectors are still $M$-orthogonal to 
each other. 




\newpage
\medskip
\noindent
{\bf 2.}  Let $A = \begin{bmatrix} 3 & 0 \cr 4 & 5i \cr\end{bmatrix}$.

\medskip
(a) Determine $\|A\|_2$ and $x \in \IC^2$ such that
$\ell^2(x) =1$ and $\|A\|_2 = \ell^2(Ax)$.

\medskip
(b) Determine $x \in \IC^2$ such that $\ell^1(x) = 1$
and $\|A\|_1 = \ell^1(Ax)$.

\medskip
(c) Determine $x \in \IC^2$ such that 
 $\ell^\infty(x) = 1$
and $\|A\|_\infty = \ell^\infty(Ax)$.

\medskip
(d) Give an example $B$ such that $\|AB\|_2 \ne \|BA\|_2$.

\newpage
\noindent
{\bf 3.}  Let $A = s_1 u_1 v_1^T + s_2 u_2v_2^T$,
where $(s_1, s_2) = (2,1)$,
$$u_1 =\frac{1}{\sqrt{3}} \begin{bmatrix}
1 \cr 1 \cr 1 \cr\end{bmatrix}, \quad
u_2 = \frac{1}{\sqrt{2}}
\begin{bmatrix}1 \cr -1 \cr 0\cr\end{bmatrix}, \quad
v_1 = \frac{1}{\sqrt{3}}
\begin{bmatrix}1 \cr 1 \cr 1 \cr 0 \cr \end{bmatrix},
\quad
v_2 = \frac{1}{\sqrt{2}}\begin{bmatrix}
1 \cr -1 \cr 0 \cr 0\cr\end{bmatrix}.
$$

(a) Find the
 best rank one approximation $A_1$ of $A$ with respect to 
the Frobenius norm.

(b) Find  matrices $U_1, V_1$
with orthonormal columns such that 
$A = U_1\Sigma_1 V_1^T$ with $\Sigma_1 =\begin{bmatrix}
2 & 0 \cr 0 & 1 \cr
\end{bmatrix}$.

(c) Find  matrices $U_2, V_2$
with orthonormal columns such that 
$A = U_2\Sigma_2 V_2^T$ with 
$\Sigma_2 =\begin{bmatrix}
2 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 \cr 
0 & 0 & 0 & 0 \cr 
\end{bmatrix}$.


\newpage
\noindent
{\bf 4.} Let $A \in M_n$ be a complex matrix.

\begin{itemize}
\item[(a)] 
Suppose $\lambda_1$ is an egenvalue of $A$ with a unit eigenvector
$u_1$,  $U_1\in M_n$ is unitary with $u_1$ as the first
column. Show that $U_1^*AU_1$ has the form $\begin{bmatrix}
\lambda_1 & x^*\cr 0 & A_1 \cr\end{bmatrix},$
where $x \in \IC^{n-1}$ and $A_1 \in M_{n-1}$.

[Hint: Argue that the first column of $U_1^*AU_1$ has the form
$(\lambda_1, 0, \dots, 0)^T$.]

\item[(b)] Prove by induction that there is a unitary $U \in M_n$
such that $U^*AU$ is in upper triangular form, i.e., 
all the $(i,j)$ entries are zero if $i > j$. 

[Hint: If $n > 1$,
apply induction 
assumption to the matrix $A_2$ in part (a) to get a 
unitary $U_2 \in M_2$ such that $U_2^*A_2U_2$ is in 
upper triangular form. Let 
$U = {\tiny U_1 \begin{bmatrix} 1 & \cr & U_2  \cr\end{bmatrix}}$. 
Then ...]

\end{itemize}

\newpage
\noindent
{\bf 5.} Suppose $A = SDS^{-1}$ such that $D$ is a diagonal 
matrix with diagonal entries $\lambda_1,\dots, \lambda_n$.

\medskip
(a) Show that $\det(\lambda I - A) = \det(\lambda I-S^{-1}DS)$. 

\medskip
(b) For any polynomial
 $f(x) = x^m + f_{m-1}x^{m-1} + \cdots + f_0$, and $C \in M_n$, let
 $$f(C) = C^m + f_{m-1}C^{m-1} + \cdots + f_0 I_n.$$

\quad Prove that  \ 
 $f(A) = A^m + f_{m-1}A^{m-1} + \cdots + f_0 I_n = 
 S(D^m + f_{m-1}D^{m-1} + \cdots + f_0I_n)S^{-1}.$

\medskip
\quad [Hint:  First show that $A^k = SD^kS^{-1}$ for any positive
integer $k$.]
 
 \medskip
 (c) Show that if $f(x) = \det(xI-A) = (x-\lambda_1)\cdots (x-\lambda_n)$,
 then 
 $$f(A) = (A-\lambda_1 I) \dots (A-\lambda_n I) = 0.$$

\quad [Hint: Show that $f(D) = (D-\lambda_1 I) \cdots (D-\lambda_n I) 
= 0$ and use (b).]
 


\newpage
\noindent
{\bf Extra credit for making up Exam 1 score} 

\medskip\noindent
Suppose $A = UTU^* \in M_n$ is a complex matrix
such that $U$ is unitary and $T = [t_{ij}]$ 
is an upper triangular matrix. Let $m$ be a positive integer.
Show that there are 
$d_1,\dots, d_n \in \IC$ such that

\begin{itemize}
\item[(a)] $(t_{11} + d_1, \dots, t_{nn}+d_n)$
has $n$ distinct entries and $|d_1|^2 + \cdots + |d_n|^2 < 1/m^2$, and 

[Hint: Let $d_1 = 0$; for $j > 1$ let
$d_j$ with $|d_j| < 1/(m^2n)$, and
$t_{jj}+d_j\notin\{t_{ii}+d_i: 1 \le i < j\}.$]


\item[(b)] if $D = \diag(d_1, \dots, d_n)$ and
$\tilde A = A + UDU^*$, then 
$\|\tilde A - A\|_F < 1/m$.

\end{itemize}

\end{document}



