
\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}
\openup 1 \jot
\noindent
{\bf Math 309 Intermediate Linear Algebra \quad Final Exam} 
{\hfill Name: \underbar{\ \hskip 1.8in \ }

\medskip
Send your (typed or handwritten) solution to ckli@math.wm.edu
 by 11:59 p.m.\ May 13.  
 



\medskip\noindent
{\bf 1.} (a)  Determine $A^{-1}$ if
$A = \begin{bmatrix} 1 & 0 & t  \cr 0 & 2 & t^2 \cr 
0 & 0 & 4 \cr\end{bmatrix}$ for $t \in \IR$,
  and determine $\frac{dA^{-1}}{dt}$
by differentiating the 

entries of $A^{-1}$ AND also by
the formula $-A^{-1} \frac{dA}{dt} A^{-1}$

\medskip\noindent
(b) Let  $\lambda_1(t), \lambda_2(t)$ be the eigenvalues of 
$B = \begin{bmatrix} 2 & 2   \cr 2 & 1 \cr 
\end{bmatrix} + t \begin{bmatrix} 1 & 1   \cr 1 & 1 \cr 
\end{bmatrix}$ 
for $t \in \IR$.
Determine $\frac{d\lambda_j}{dt}$ at $t = 0$.


\medskip\noindent
{\bf 2.} Find a degree 2 polynomial $f(x)$ such that
$f(0) = 1, \ f(1) = 2, \ f(2) = 7.$


\medskip\noindent
{\bf 3.} Let $A\in M_{m,n}$ with nonzero singular values
$s_1 \ge \cdots \ge s_r > 0$. Show that 
$$\begin{bmatrix} 0_m & A \cr A^* & 0_n\cr\end{bmatrix}$$

have nonzero eigenvalues $\pm s_1, \dots, \pm s_r$.

\medskip
\noindent
{\bf 4.} Suppose $H = H^* \in M_n$ have eigenvalues $\lambda_1 \ge \dots,
\ge \lambda_n$. Let $H_k\in M_k$ be a principal submatrix 

of $H$
with eigenvalues $\mu_1 \ge \cdots \ge \mu_k$.

\medskip
(a) Show that $\lambda_j \ge \mu_j$ for $j = 1, \dots, k$.

\medskip
(b) Show that  $\tr(H_k) \le \sum_{j=1}^k \lambda_j$.

\medskip
(c) If $H$ has diagonal entries $d_1 \ge \cdots \ge d_n$,
Show that for $k = 1, \dots, n-1$, 
$$d_1 + \cdots + d_k \le \lambda_1 + \cdots + \lambda_k.$$

\medskip\noindent
{\bf 5.} Let  $X, Y \in M_{m,n}$. Show that for $j = 1, \dots, n,$
$$\lambda_j(X^*X + Y^*Y) \ge \lambda_j(X^*Y+Y^*X).$$

[Hint: Consider $(X-Y)^*(X-Y).$]

\medskip\noindent
{\bf 6.} Recall that $A \in M_n$ is normal if and only if $AA^* = A^*A$.
Suppose $T \in M_n$ is upper triangular. 


Show that 
$T$ is normal if and only if $T$ is a diagonal matrix.


\medskip
\noindent
\medskip{\bf 7.}
Let $P = E_{12} + E_{23} + \cdots + E_{n-1,n} + E_{n1}$,
$w = e^{i2\pi/n}$, and $V = \frac{1}{\sqrt{n}} [w^{(i-1)(j-1)}]$.

(a) Show that $V^*PV = D = \diag(1, w, w^2, \dots, w^{n-1})$.

(b) Let  $A= a_0I + a_1P + \cdots + a_{n-1}P^{n-1}$. Show that
 $V^*AV = \sum_{j=0}^n a_j D^j$
and determine the 

\quad eigenvalues of $A$.


\medskip\noindent
{\bf 8.} Suppose $A \in M_{m,n}$ has rank $r$.
Show that there are  $C \in M_{m,r}, R \in M_{n,r}$
such that $A = CR$ 

and 
$\|A\|_N = \|C\|_F^2 = \|R\|_F^2$. [Hint: Let $A = U\Sigma V^*$. Then ...]







\newpage


\centerline{\bf 
 Extra credit problem for Exam 1 or 2.}
 
 \bigskip\noindent
{\bf 9.} 
Let  $A \in M_n$.

\begin{itemize}
\item[(a)] If $A$ is singular, show that  there is $j \in \{1,\dots, n\}$
such that $|a_{jj}| \le \sum_{\ell\ne j} |a_{j\ell}|.$

[Hint: Suppose $x =[x_1, \dots, x_n]^T \in \IF^n$ 
is nonzero such that $Ax = 0$. If $|x_\ell| \le |x_j|$ for all $\ell$,
use the fact that $[a_{j1}, \dots, a_{jn}] x = 0$
to deduce the conclusion.]

\item[
(b)] Use (a) to deduce that if $\lambda$ is an eigenvalue of 
$A$, then there is $i \in \{1, \dots, n\}$ such that 
$|a_{ii}-\lambda| \le \sum_{\ell \ne i} |a_{i\ell}|.$

\end{itemize} 

\bigskip\noindent
{\bf 10.}
Let $A$ be a partial matrix in $M_{m,n}$. 
Then a completion $A_0$ with minimum nuclear norm
satisfies
$$\|A_0\|_N = \min\left\{ [\tr(P_1)+\tr(P_2)]/2:
\begin{bmatrix}
P_1 & A_0 \cr A_0^* & P_2 \cr
\end{bmatrix} \hbox{ is psd} \right\}.$$
\end{document}