
\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 5 {\hfill Your Name}



\begin{enumerate}
\item (8 points) Let $\bd = (6,3,1)^t$ and 
$\ba = (8,2,0)^t$

(a) Find  doubly stochastic matrices $T_1$ and $T_2$ such that
$T_1\ba = (6,4,0)^t$ and $T_2T_1\ba = \b \bd$.

(b) Construct a real symmetric matrix with eigenvalues $8,2,0$ and diagonal entries
$1,3,6$ 

\qquad (in the specified order).

\item (8 points) Let $\bx = (x_1, \dots, x_n)^t, 
\by = (y_1, \dots, y_n) \in \IR^n$ with positive entries.

(a) Suppose 
$\bx$ is obtained from $\by$ by changing two of its entries $y_p > y_q$ to 
$y_p - d, y_q+d$ with 

\qquad $d \in (0, y_p-y_q)$. Show that $y_py_q \le x_px_q$, and hence
$\prod_{j=1}^n y_j \le \prod_{j=1}^n x_j.$

For example, if $\by = (3,1)$ and $\bx = (2,2)$, then $(3)(1) \le  (2)(2)$.

(b) Suppose 
$\bx \prec \by$. Sow that $\prod_{j=1}^n y_j \le \prod_{j=1}^n x_j.$


\item (8 points) 
(a) Suppose $A = (a_{ij}) \in M_n$ is positive semidefinite.
  Show that  $\det(A) \le \prod_{j=1}^n a_{jj}$.
 
Hint: $\det(A) = \prod_{j=1} \lambda_j(A)$, and use the result of the last problem.
  
(b) Suppose $B \in M_n$ has columns $b_1, \dots, b_n$. Show
$|\det(B)| \le \prod_{j=1}^n \|b_j\|.$

Hint: Show that $\det(B^*B) = |\det(B)|^2$, $B^*B$ has diagonal entries
$\|b_1\|^2, \dots, \|b_n\|^2$, ....


\item (6 points) Let $A = \begin{pmatrix} A_{11} & A_{12} \cr A_{21} & A_{22}
\end{pmatrix} \in M_n$ be positive semidefinite  with $A_{11} \in M_k$. Show that 
$$\det(A) \le \det(A_{11}) \det(A_{22}).$$



\item (8 points) Let $A = A^* \in M_n$. 
Show that there is an invertible
matrix $S$ such that $S^*AS = I_p \oplus -I_q \oplus 0_{n-p-q}$
if and only if $A$ has $p$ positive and $q$ negative eigenvalues.

Hint: To prove the sufficiency, let $U^*AU = \diag(a_1, \dots, a_p, -a_{p+1}, 
\dots, -a_{p+q}, 0, \dots, 0)$ such that $a_1, \dots, a_{p+1} > 0$. Then ...

Hint: To prove the necessity, let $S_1$ be the matrix form by the 
first $p$ columns of $S$. Apply Gram-Schmidt process so that  
$S_1 = VR$ for $V \in M_{n,p}, R \in M_p$ with $V^*V = I_p$ and 
$R$ is invertible upper triangular. Show that 
$\lambda_k(V^*AV) = \lambda_k((R^*)^{-1}R^{-1}) > 0$ so that
$A$ has at least $p$ positive eigenvalues. Similarly, argue that 
$-A$ has at least $q$ positive eigenvalues, and that $A$ has at least $n-p-q$ 
zero eigenvalues.

\item (8 points) Suppose $A, B \in M_n$ are Hermitian matrices with eigenvalues
$a_1 \ge \cdots \ge a_n$ and $b_1 \ge \cdots \ge b_n$, respectively.
Use the result of Lidskii or otherwise to show that 
$$(a_1 + b_n, \dots, a_n+b_1) \prec \lambda(A+B) \prec (a_1 + b_1, \dots, a_n+b_n).$$





\end{enumerate}
\end{document}



