
\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}
\noindent
{\bf Math 408 Advanced Linear Algebra \qquad Homework 9 {\hfill Your Name}}

\medskip\centerline{
Eight points for each question.}

\begin{enumerate}
\item Let $A = (a_{ij}) \in M_n$ be such that $|a_{ii}| \ge \sum_{j\ne i} |a_{ij}|$ 
for every $i = 1, \dots, n$.

(a) If $|a_{ii}| > \sum_{j\ne i} |a_{ij}|$ 
for every $i = 1, \dots, n$. Show that  $A$ is invertible.

(b) If $a_{ii} \ne 0$ for all $i$, and 
$|a_{ii}| > \sum_{j\ne i} |a_{ij}|$ 
for all but one $i$'s. Show that $A$ is invertible. 

[Hint: Show that there is a diagonal matrix $D$ such that $D^{-1}AD = (b_{ij})$ satisfies
$|b_{ii}| > \sum_{j\ne i}|b_{ij}|$ for every $i = 1, \dots, n$.]

(c) (Extra 4 points) Show that the conclusion (b) fails if we do not assume that 
 $|a_{ii}| \ge \sum_{j\ne i} |a_{ij}|$ 
for every $i = 1, \dots, n$.

\item Let $A = (a_{ij}) \in M_n$ with an eigenvalue $\lambda$.
Suppose $D = \diag(a_{11}, \dots, a_{nn})$ and 
$B = A-D$. If $\lambda \ne a_{ii}$ for
$i = 1, \dots, a_{nn}$, show that 1 is an eigenvalue of 
the matrix $(\lambda I - D)^{-1}B$.


\item Let $A\in M_n$ with columns $v_1, \dots, v_n$. 
Show that 

\medskip\centerline{$|\det(A)| \le \prod_{j=1}^n \ell_{1}(v_j)$ and 
$|\det(A)| \le \prod_{j=1}^n \sum_{k=1}^n |a_{jk}|$.}

\medskip\noindent
Hint: $\ell_2(v) \le \ell_1(v)$.

\item Consider $f(z) = z^n + a_1 z^{n-1} + \cdots + a_n$.
Suppose $\mu$ is a zero of $f(z)$.

(a) Use the Companion matrix $C_f$ of $f$ to deduce that 

\medskip\centerline{
$|\mu| \le \max\{1, \sum_{j=1}^n |a_j|\}$ and
$|\mu| \le \max(\{1+|a_j|: 1 \le j \le n-1\} \cup \{|a_n|\})$.}

\medskip
(b) Show that the Companion matrix of $f$ has singular values
$s_2(C_f) = \cdots = s_{n-1}(C_f) = 1$;

\qquad 
$s_1(C_f)$ and $s_n(C_f)$ are the singular values of the matrix
$\begin{pmatrix}1 & 0 \cr \gamma & |a_n| \cr\end{pmatrix}$, were
 $\gamma = 
\sqrt{\sum_{j=1}^{n-1} |a_j|^2}$.

\medskip 
(c) Use (b) to conclude that 
$|\mu| \le \frac{1}{2} \{\sqrt{(1+|a_n|)^2 + \gamma^2} +
\sqrt{(1-|a_n|)^2 + \gamma^2}\}$.


\item Let $A \in M_n$ with an eigenvalue $\mu$ such that 
$A-\mu I$ has rank $n-1$.  Suppose $x, y$ are right and left eigenvectors of $A$ 
corresponding to the eigenvalue $\mu$ satisfying $y^*x = 1$. 
Show that there is an invertible matrix $S$ such that 
$S^{-1}AS = [\mu] \oplus A_1$ and $A_1 - \mu I_{n-1}$ is invertible.

\item Let $A \in M_n$ be a nonnegative matrix such that $(I+A)^k$ is positive. Show that
$A$ has a simple eigenvalue $r(A)$ with positive right and left eigenvectors $x$ and $y$.

(Extra eight points)
A matrix $A\in M_n$ is irreducible if there is no permutation matrix
$P$ such that $P^tAP = \begin{pmatrix}A_{11} & A_{12} \cr 0 & A_{22}\cr\end{pmatrix}$
with $A \in M_k$ with $1 \le k \le n-1$.
Show that a nonnegative matrix $A \in M_n$ is 
such that $(A + I)^{n-1}$ is a positive matrix.


\item Let $V \in M_{4,2}$ satisfy $V^*V = I_2$, and let $P = VV^*$.

{\rm (a)} Show that $V$ has a submatrix in $M_2$ with singular values 
$s_1, s_2$ if and only if $P$ has a principal submatrix in $M_2$ with eigenvalues 
$s_1^2, s_2^2$.

{\rm (b)} Show that $\det(zI - P) = z^2(z-1)^2$ so that there is a 
$2\times 2$ principal submatrix
of $P$  with determinant larger than $1/6$ and smallest eigenvalue larger than $1/6$.

{\rm (c)} (Extra credit open problem. The solution will earn you an $A$ for the course.)
Show that there is a $2\times 2$ principal submatrix of $P$ with smaller eigenvalue
larger than or equal to  $1/4$.

{\rm (d)} (Extra credit open problem. The solution will earn you an $A$
for the course, and a research paper.) Prove that for any $n\times k$ matrix $V$
such that $V^*V = I_k$. There is an $k\times k$ principal submatrix of 
$P = VV^*$ with smallest eigenvalue larger than or equal to $1/n$.
 


 
\end{enumerate}


\end{document}



