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

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

\begin{enumerate}
\item Suppose $n = 3$. List all the Horn's sequences $(u_1,u_2), (v_1,v_2), (w_1,w_2)$
of length 2, and list all the Thompson standard sequences $(u_1,u_2), (v_1, v_2)$ and 
$(w_1, w_2) = (u_1+v_1-1, u_2+v_2-2)$.  

Hint:
See p.23-24 in 
http://cklixx.people.wm.edu/teaching/math408/note.pdf

You should see six sets of Horn's sequences 
$(u_1,u_2), (v_1,v_2), (w_1,w_2)$,
and one of them not Thompson standard sequences.

\item Let $A, B, C = A+B \in M_n$ be Hermitian with 
eigenvalues 
$a_1 \ge \cdots \ge a_n$, $b_1 \ge \dots \ge b_n$ and 
$c_1 \ge \cdots \ge c_n$, respectively. Show that if $C = (c_{ij})$ then 
$$\sum_{j=1}^k c_{jj} \le \sum_{j=1}^k (a_j + b_j);$$ 
the equality holds if and only 
if $A = A_{11} \oplus A_{22}, B = B_{11} \oplus B_{22}$ with $A_{11}, B_{11} \in M_k$
such that $A_{11}$ and $B_{11}$ have eigenvalues 
$a_1 \ge \cdots \ge a_k, b_1 \ge \cdots \ge b_k$,
respectively.

\item (Weyl's inequalities.) Suppose 
$A, B, C = A+B\in M_n$ are Hermitian matrices. 
Let $\{x_1, \dots, x_n\}$, $\{y_1, \dots, y_n\}$, $\{z_1, \dots, z_n\}$
be orthonormal sets 
such that $Ax_j = \lambda_j(A) x_j, By_j = \lambda_j(B) y_j, 
Cz_j = \lambda_j(C) z_j$. Suppose $i, j$ are positive integers such that $i+j - 1 \le n$.

(a) Show that there is a unit vector $v \in
V_1 \cap V_2 \cap V_3$,
where 

\qquad $V_1 = \span\{x_i, \cdots, x_n\}$, 
$V_2 =\span\{ y_j, \dots, y_n\}$ and 
$V_3 = \{z_1, \dots, z_{i+j-1}\}$.

Hint: Show that $V_2 \cap V_3$ has dimension at least $(n-j+1)+(i+j-1) - n = i$ 
by considering the null space of the matrix 
$[y_j \cdots y_n \ z_1 \dots z_{i+j-1}]$,
and then show that $V_1 \cap (V_2\cap V_3)$ is not the zero space.

(b) Show that the vector $v$ found in (a) satisfies
$$\lambda_{i+j-1}(C) \le v^*Cv, \ v^*Av \le \lambda_i(A), \ v^*Bv \le \lambda_j(B),$$
and deduce that 
$$\lambda_{i+j-1}(C) \le \lambda_i(A) + \lambda_j(B).$$


\item Show that $\ell_p(v) \ge \ell_q(v)$ for any vector $v \in \IF^n$ if 
$1 \le p \le q \le \infty$. 

Hint: Only need to prove the result for vector with nonnegative entries; show that 
$f(v) = \sum v_j^p \ge 1$ if 
$g(v) = \sum v_j^q - 1 = 0$. Use Lagrange multipliers to the function
$L(\mu,v) = f(v) - \mu g(v)$ and conclude that all nonzero entries of $v$ have to be the
same so that $v = \gamma(1, \dots, 1, 0, \dots, 0)$. 

\item Show that if $x, y \in \IR^n$ are vectors with positive entries such that 
$x \prec y$, then $\ell_p(x) \le \ell_p(y)$ for any $p \ge 1$.

Hint: We need only do the special case when $x$ is obtained from $y$ by
changing two entries $y_i > y_j$ to $y_i-d, y_j+d$ for $d \in (0, y_i-y_j)$. 


\item  
Let $u = (u_1, \dots, u_n)^t$ and $v = (v_1, \dots, v_n)^t$ be such that 
$(|u_1|, \dots, |u_n|) \prec_w (|v_1|, \dots, |v_n|)$. 
Show that there is a nonnegative integer $m$ and 
a nonnegative $d$ such that 
$$(|u_1|, \dots, |u_n|, \underbrace{d, \dots, d}_m) \prec (|v_1|, \dots, |v_n|, 0, \dots, 0).$$
Deduce from the result of the previous problem that 
$\ell_p(u) \le \ell_p(v)$
for any $p \ge 1$.

(Extra credits) Alternatively,  
show that there is $\hat v = (\hat v_1, \dots, \hat v_n)$
such that $\sum_{j=1}^k \hat v_j = \max\{ \sum_{j=1}^k |v_j|, \ell_1(u)\}$.
Then prove that $(|u_1|, \dots, |u_n|) \prec (\hat v_1, \dots, \hat v_n)$ and  
$$\ell_p(u) \le \ell_p(\hat v) \le \ell_p(v).$$

\item (Extra credits)
Suppose $c_1 \ge a_1 \ge c_2 \ge a_2 \ge \cdots \ge a_{n-1} \ge c_n \ge a_n$ are
$2n$ real numbers. 
Show that there is a nonnegative real vector $v  \in \IR^{n}$ 
such that $D + vv^t$ has eigenvalues $c_1 \ge \cdots \ge c_n$ 
for $D = \diag(a_1, \dots, a_{n})$.

Hint: Replace $c_j$ by $c_j + \gamma $  and $a_j+\gamma$ for $j = 1, \dots, n$,
for a sufficiently large $\gamma > 0$, and assume that $c_n \ge a_n > 0$.
By interlacing inequalities, there is $\tilde C = \begin{pmatrix} D & y \cr 
y^t & a \cr\end{pmatrix}$.  Show that $C = D + vv^t$ has eigenvalues $c_1 \ge \cdots \ge c_n$.



\item (Extra credit) Suppose $C = A+iB$ so that 
$A$ and $B$ are Hermitian matrices. Suppose $A$ has eigenvalues $a_1, \dots, a_n$,
and $B$ has eigenvalues $b_1, \dots, b_n$ such that 
$a_1^2 \ge \cdots \ge a_n^2$ and $b_1^2 \ge \cdots \ge b_n^2$.
If $C$ has singular values $s_1 \ge \cdots \ge s_n$, show that
$$(a_1^2+b_n^2, \dots, a_n^2+b_1^2) \prec (s_1^2, \dots, s_n^2)$$
and 
$$(s_1^2+s_n^2, \dots, s_n^2+s_1^2)/2 \prec (a_1^2 + b_1^2, \dots, a_n^2+b_n^2).$$

Hint: $A^2+B^2 = (CC^* +C^*C)/2$.

\item (Extra credit)
Suppose $A = \begin{pmatrix} \tilde A & * \cr 0 & *\cr\end{pmatrix}$. Show that 
$$s_1(A) \ge s_1(\tilde A) \ge s_2(A) \ge s_2(\tilde A) \ge \cdots 
\ge s_{n-1}(\tilde A) \ge s_n(A).$$

Hint: Apply interlacing inequalities to $A^*A$.


\item (Extra credit) Suppose $A, B \in M_{n}$. For any subsequences
$(u_1, \dots, u_k), (v_1, \dots, v_k)$ and $(w_1, \dots, w_k)$ of 
$(1,\dots,n)$ such that $w_j = u_j+v_j-j$ for $j = 1, \dots, k$,
and $u_k+v_k-k\le n$, we have
$$\prod_{j=1}^k s_{u_j}(A) s_{v_j}(B) \ge \prod_{j=1}^k s_{w_j}(AB).$$


Hint: By induction on $n$. Check the case for $n  = 2$. Assume that the result holds for matrices
of size $n-1$. If $k = n$, the equality holds. Suppose $k < n$.  
Let $p$ be the largest integer such that $u_j = j$ for all $j = 1, \dots, p$,
and $q$ be the largest integer such that $v_j = j$ for all $j = 1, \dots, q$.
We may assume that $q \le p$. 
Let $C = AB$, $\{u_1, \dots, u_n\}$ and $\{v_1, \dots, v_n\}$ be 
orthonormal sets such that 
$$B^*B u_j = s_j(B)^2 u_j \quad \hbox{ and } \quad 
C^*Cv_j = s_j(C)^2 v_j.$$
Suppose $U, V$ are unitary such that 
the first $n-1$ columns span a subspace containing $v_1, \dots, v_1, u_{q+2}, \dots, u_n$,
and $V^*BU = \begin{pmatrix}\tilde B & * \cr 0 & * \cr\end{pmatrix}$ with $\tilde B \in M_{n-1}$.
Let $W$ be unitary such that
$W^*BV = \begin{pmatrix}\tilde A & * \cr 0 & * \cr\end{pmatrix}$.
Then $W^*ABV = \begin{pmatrix}\tilde A \tilde B& * \cr 0 & * \cr\end{pmatrix}$.
Apply induction assumption on $\tilde A\tilde B$ to finish the proof.

\end{enumerate}


\end{document}



