
\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\bd{{\bf d}}
\def\ba{{\bf a}}
\def\bx{{\bf x}}
\def\by{{\bf y}}
\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 408 Advanced Linear Algebra \qquad Final examination {\hfill Due: Dec. 8, noon}}

\medskip\centerline{The scores of the best 7 questions will go to the final examination grade.
}

\centerline{
The rest will be extra homework credits. Good luck!}


\begin{enumerate}
\item (a) Use Gershgorin Theorem to conclude that $\begin{pmatrix} 1 & 1/2 & 1 \cr i & 4 & 0 \cr
0 & i/2 &  7\cr\end{pmatrix}$ has 3 distinct eigenvalues.

(b) For $B = (b_{ij})$, let $G_i(B) = \{\mu\in \IC: |\mu - b_{ii}| \le \sum_{j\ne i} |b_{ij}|\}$.
Construct an example of $B$ so 

\qquad that there is no eigenvalue in $G_1(B)$.

\item Let $A \in M_{n,p}$ and $B \in M_{n,q}$. Show that
$$\rank([A|B]) = \rank(A) + \rank(B) - d,$$
where $d$ is the dimension of $Col(A) \cap Col(B)$, the intersection
of the column space of $A$ and the column space of $B$.

Hint: Let $\{v_1, ..., v_d\}$ be a basis for $Col(A)\cap Col(B)$. Form
bases for $Col(A), Col(B)$ containing $\{v_1, \dots, v_d\}$, and ....

\item Let $A\in M_n$ be a normal matrix.

(a) If $B \in M_m$ is normal, show that $A \otimes B$ is normal.

(b) If $m > 1$ and $C \in M_m$ is not normal, show that $A \otimes C$ is not normal. 

\item Prove or disprove the following.

(a) A principal submatrix of a Hermitian matrix $A \in M_n$ is Hermitian.

(b) A principal submatrix of a normal matrix is normal.

\item Let $A = \begin{pmatrix} A_{11} & A_{12} \cr A_{21} & A_{22} \cr\end{pmatrix} \in M_n$
such that $A_{11} \in M_k$ is invertible.

(a) Compute $RA$ for $R = \begin{pmatrix} I_k & 0 \cr - A_{21}A_{11}^{-1} & I_{n-k}\cr\end{pmatrix}$.

(b) Show that $A$ is invertible if and only if $C = A_{22}-A_{21}A_{11}^{-1}A_{12}$ is invertible,
and $A^{-1}$

\qquad
has the form $A^{-1} = \begin{pmatrix}* & * \cr * & C^{-1} \cr\end{pmatrix}$.

Hint: If $T = RA = \begin{pmatrix}T_{11} & * \cr 0 & T_{22}\cr\end{pmatrix}$ is invertible,
then show that
$T^{-1}$ has the form $\begin{pmatrix}T_{11}^{-1} & * \cr 0 & T_{22}^{-1}\cr\end{pmatrix}$.

\item Let $A \in M_n$ be Hermitian.
Show that if $A \in M_n$ is positive semidefinite if and only if all principal minors of $A$ 
are nonnegative.

\item (a) Show that if $A\in M_n$ is normal, then $r(A) = w(A) = s_1(A)$.

(b) Construct a non-normal $B \in M_n$ such that $r(B) = w(B) = s_1(B)$.


\item Let $(a_1, b_1), \dots, (a_n,b_n) \in \IC^{1\times 2}$ be
such that $a_1, \dots, a_n$ are distinct.

(a) Suppose $f(z) = f_{n-1}z^{n-1} + f_{n-2} z^{n-2} + \cdots + f_0$ satisfies
$f(a_i) = b_i$ for $i = 1, \dots, n$. Show that
$$V(a_1, \dots, a_n) (f_0, \dots, f_{n-1})^t = (b_1, \dots, b_n)^t,$$
where the $i$th row of $V(a_1, \dots, a_n)\in M_n$ is 
$(1 \ a_i \ a_i^2 \ \cdots \ a_i^{n-1})$ for $i = 1, \dots, n$.


(b) Show that $\det(V(a_1, \dots, a_n)) = \prod_{1\le i < j \le n} (a_j-a_i)$;
thus $V(a_1, \dots, a_n)$ is always invertible.

Hint: You may use induction, or show that $(a_j - a_i)$ is always a factor of
$\det(V(a_1, \dots, a_n))$ if we regard $\det(V(a_1, \dots, a_n))$ as a 
multinomial of $(a_1, \dots, a_n)$. Then conclude that the expansion 
of $\det(V(a_1, \dots, a_n))$ is the same as the expansion of 
$\prod_{1\le i < j \le n} (a_j-a_i)$.

{\bf Remark} The matrix $V(a_1, \dots, a_n)$ is known as the Vandetmonde matrix.


\item Let $A \in M_n$. 

(a) Use the fact that $A$ contains all the eigenvalues of $A$  and the convexity of the numerical 
range to show that $(\tr A)/n \in W(A)$.

(b) Show that there is a unitary $U$ such that $U^*AU$ has all diagonal entries equal to 
$(\tr A)/n$.

[Hint: Induction.]
 
 
 \item Let $N_n = E_{12} + \cdots + E_{n-1,n} \in M_n$ and 
$$ T_n = aI_n + bN_n + cN_n^t =
 \begin{pmatrix} 
 a & b &   &  &  \cr
 c & a & b &  &  \cr
   & \ddots & \ddots & \ddots & \cr
   & & c & a & b \cr
                   &&& c & a \cr\end{pmatrix}.$$

(a) Show that $\det(T_1) = a, \det(T_2) = a^2-bc$,
$\det(T_n) = a\det(T_{n-1}) - bc \det(T_{n-2})$.

(b) If $bc = 0$, show that $\det(T_n) = a^n$.

(c) Suppose $bc \ne 0$ and $\alpha, \beta$ are the zeros of $f(z) = z^2 - az + bc$.

(c.1) If $\alpha = \beta$, show that
$\det(T_n) = (n+1)(a/2)^n$.

(c.2) If $\alpha \ne \beta$, show that
$\det(T_n) = c_1 \alpha^n + c_2 \beta^n$ with 
$c_1 = \alpha/(\alpha-\beta)$ and $c_2 = -\beta/(\alpha-\beta)$.

Hint: Suffices to show that the suggested values in (c.1), (c.2) satisfy
the conditions in (a).


                   
\end{enumerate}


\end{document}



