EIGENVALUES, SINGULAR VALUES, AND LITTLEWOOD-RICHARDSON COEFFICIENTS (Role of Operator Inequalities in Operator Theory)

EIGENVALUES,

SINGULAR VALUES, AND

LITTLEWOOD-RICHARDSON

COEFFICIENTS

Chi-Kwong Li

Department of Mathematics, CollegeofWilliamand Mary, Williamsburg, Virginia23187-8795,

USA

E-mail: [email protected]

We briefly describe

some

recent results

on

inequalities relating the eigenvalues of the

sum

of

Hermitian

or

real matrices, and how to

use

these them inequalities relating the eigenvalues and

singular values of

a

matrix and its submatrices. These results

are

joint work with Poon, Fomin, and Fulton [4, 14, 15]. Some open problems and remarks

are

also mentioned.

1

Sum of

Hermitian

(Real Symmetric)

Matrices

Let $\mathrm{H}_{n}$ bethe set of$n\mathrm{x}$ $n$ Hermitian

matrices.

Denotethe vector of eigenvalues of$X\in \mathrm{H}_{n}$ by

A(X) $=(\lambda_{1}(X), \ldots, \lambda_{n}(X))$

with $\lambda_{1}(X)$ $\geq\cdots\geq\lambda_{n}(X)$

.

There has been a great dealof interest instudying the following.

Problem Let$A$,$E\in \mathrm{H}_{n}$ and $\tilde{A}=A+E$

.

Determine inequalities relating the eigenvaluesof

$\tilde{A}$

and

those of$A$ and $E$.

One

can

regard$E$

as

a

smallperturbation ofthe matrix$A$. So,

we are

interested intherelations

betweenthe eigenvalues ofthe original matrix $A$ and the perturbed matrix $\tilde{A}$.

One may

see

[6] for an excellent survey on this problem and its solution. To motivate our

discussion,

we

collect several wellknownresults by Weyl, Liskii, Mirsky, Wielandt, Thompsonand

Freede;

see

$[1, 17]$.

.

For $\mathrm{i}=1$, $\ldots$,$n$,

$\lambda_{n}(E)\leq\lambda_{i}(\tilde{A})-\lambda_{i}(A)\leq\lambda_{1}(E)$

.

.

Suppose $1\leq \mathrm{i}_{1}<\cdots<\mathrm{i}_{m}\leq n$ and $1\leq j_{1}<\cdots<j_{m}\leq n$

.

Then

$\sum_{s=1}^{m}\lambda_{n-s+1}(E)\leq\sum_{s=1}^{m}(\lambda_{j_{s}}(\tilde{A})-\lambda_{j_{s}}(A))\leq\sum_{s=1}^{m}\lambda_{s}(E)$

.

Consequently, forany unitarily invariant norm $||\cdot$ $||$ we have

$-||E||\leq||\overline{A}||-||A||\leq||E||$

.

.

Suppose $1\leq \mathrm{i}_{1}<\cdots<\mathrm{i}_{m}\leq n$and $1\leq j_{1}<\cdots<j_{m}\leq n$

.

If$i_{m}+j_{m}-m\leq n$, then

$\sum_{s=1}^{m}\lambda_{i_{S}+j_{S}-s}(\tilde{A})\leq\sum_{s=1}^{m}\lambda_{i_{s}}(A)+\sum_{s=1}^{m}\lambda_{j_{s}}(E)$ .

All the above andmany

more

other earlyresults suggest that there areinequalitiesof the form

$\sum_{j\in J_{0}}\lambda_{j}(\tilde{A})\leq\sum_{j\in J_{1}}\lambda_{\mathrm{J}}(A)+\sum_{j\in J_{2}}\lambda_{j}(E)$

for

some

suitable subsets Jo,$J_{1}$,$J_{2}$ of $\{$1,

$\ldots$ ,$n\}$. It turns out that a complete set of inequalities

can

be described inthis way;

see

[9] and also [6].

Theorem

1.1

There exist $A,B$,$C\in \mathrm{H}_{n}$ satisfying $C=A+B$ with $\lambda(A)=(a_{1}, \ldots : a_{n})$, $\lambda(B)=$

$(b_{1}, \ldots, \mathrm{b}\mathrm{n})$, $\mathrm{X}(\mathrm{C})=(\mathrm{c}\mathrm{i}, \ldots, c_{n})$

if

and only

if

we

have the trace equality

$\sum_{s=1}^{n}c_{s}=\sum_{s=1}^{n}(a_{s}+b_{s})$,

and

_for

any (Jo,$J_{1}$,J2) $\in LR_{m}^{n}$ with$m<n$

$\sum_{j\in J_{0}}c_{j}\leq\sum_{j\in J_{1}}a_{j}+\sum_{j\in J_{2}}b_{j}$

.

In the theorem,we

use

theconceptsof Littlewood-Richardson sequences$LR_{m}^{n}$

.

A goodreference

for this concept is [5]. Here

we

describe the formal definitionand give a simple example.

Let $[n]=$ $($1,

$\ldots$,$n)$ and $J=(j_{1}, \ldots,j_{m})$ be

an

increasing subsequences of $[n]$, i.e., $1\leq j_{1}<$ $\ldots<j_{m}\leq n$. Define

$\mu(J)=(j_{m}-m, \ldots ,j_{1}-1)$

.

Suppose $J0$,$J_{1}$,$J_{2}$ are increasing subsequences of $[n]$

.

Then (Jo,$J_{1},$$J_{2}$) $\in LR_{m}^{n}$ if $\mu(J_{0})$

can

be

generated from $\mu(J_{1})$ and$/\mathrm{i}(\mathrm{J}_{2})$ according to theLittlewood-Richardson rules:

Display $\mathrm{f}\mathrm{x}\{\mathrm{J}\mathrm{o}$) $=(\mathrm{c}\mathrm{i}, \ldots, \mathrm{r}\mathrm{m})$, $\mu(J_{1})=(\mathrm{c}\mathrm{i}, \ldots, s_{m})$, and $\mathrm{p}(\mathrm{J}2)=(t_{1}, \ldots, t_{m})$

as

Young diagrams. Add $t_{1}+\cdots+t_{m}$ entries from $\{$1,...,$m\}$ to the

rows

oftheYoung diagram of$\mu(J_{1})$ to generate

theYoung diagramof$\mu(J_{0})$

so

that:

.

The entries $\mathrm{i}$

occurs

exactly $t_{i}$

so

many times.

.

The entries in eachrow is weakly increasing from left to right.

.

The entries ineach column isstrictly increasing from top tobottom.

.

For any$p$with $1 \leq p\leq\sum_{j=1}^{m}t_{f7}$ define$p(i)$to be the number of$\mathrm{i}$ inthe first

$p$assigned values

counting from right to left andtop to bottom,

we

have$p(\mathrm{i})\geq p(\mathrm{i}+1)$

.

Insuch

a

case, theLittlewood-Richardson coefficient $c_{\mu(J_{1})\mu(J_{2})}^{\mu J_{0})}$of the three partitions $\mu(J_{0}),\mu(J_{1})$,

Example 1.2 Suppose $\mu(J_{0})=(5,$4,3,1), $\mu(J_{1})=(3,2,1,0)$, $\mu(J_{2})=(3,2,$2,0). Here

are

three

examples of good constructions:

$*$ $*$ $*$ 1 1 $*$ $*$ $*$ 1 1 $*$ $*$ $*$ 1 1

$*$ $*$

1

2 $*$ $*$ 2

2

$*$ $*$ 2 2

$*$ 2

3

$*$ 1 3 $*$ 3 3

3

3 1

Here

are

three examples ofbad constructions:

$*$ $*$ $*$ 1 1 $*$ $*$ $*$ 1 1 $*$ $*$ $*$ I1

$*$ $*$ 2 1 $*$ $*$ 2

3

$*$ $*$ 1 2

$*$ 2

3

$*$ 2 1 $*$

3 3

3

3

2

One

can

use

the LR rules to explain the Weyl inequalities, and the standard inequalities of

Thompson.

[Weyl’s inequalities] $((j_{0}), (j_{1})$, (j2)$)$ \in LR% ifand only if$j\mathrm{O}$ $=j_{1}+j_{2}-1$

.

[Thompson’s standard inequalities] If$J_{1}=$ (ii

.

.

.

,$i_{m}$) and$J_{2}=(j_{1}, \ldots, j_{m})$satisfy$\mathrm{i}_{m}+j_{m}-m\leq n$,

then $J_{0}=$ $(\mathrm{i}_{1}+j_{1}-1, \ldots, \mathrm{i}_{m}+j_{m}-m)$ is admissible.

Note that

one can

do

a

good constructionby adding$j_{r}-r$to the $(m-r+1)\mathrm{s}\mathrm{t}$

row

of$\mu(J_{1})$ to

get $\mu(J_{2})$

.

In general, it is not easyto solve the following.

Problem How to generate all the $(J_{0}, J_{1}, J_{2})$ sequences, and do it efficiently?

By the result in [12],

one can

focus

on

$(J_{0}, J_{1}, J_{2})$ sequences with LR coefficient equal to one,

i.e., there is

a

unique

construction

of$\mu(J_{0})$ from$\mu(J_{1})$ and $\mu(J_{2})$

.

However it is hardtodeterminewhenthe LR coefficient is positive

or

equals

one.

In particular,

it is difficult to write

a

computer program to generate all LR sequences. in

some

situations,

one

may prefer to generate

a

class of

sequences

systematically

even

though the classmay contain many

redundant sequences. Taking this approach,

one

can

use

the Horn’s consistent sequences $(R, S, T)$,

which is defined recursively

as

follows,

Let $R=$ $(r_{1}, \ldots, r_{m})$,$S=(s_{1}, \ldots, s_{m}),T=(t_{1}, \ldots, t_{m})\in[n]$

.

.

For $m\geq 1$, $\sum_{l=1}^{m}(r\ell-\ell)=\sum_{\ell=1}^{m}(s\ell+t\ell-2l)$

.

.

If$m>1$, thenfor any consistent triple $(U, V, W)$:

with$m’\in\{1, \ldots , m-1\}$, we have

$\sum_{\ell=1}^{m^{J}}(r_{u_{l}}-\ell)\geq\sum_{\ell=1}^{m’}(s_{vp}+t_{w_{t}}-2\ell)$.

One

can

extend Theorem 1.1 to the

sum

of$r$ Hermitian matrices

over

real, complex,

or

real

quaternions; see [6].

Theorem 1.3 There are $A_{1}$,

$\ldots$,$A_{r}\in \mathrm{H}_{n}$ with

$\lambda(A_{s})=(a_{1}^{(s\rangle}, \ldots, a_{n}^{(s)})$

for

$s=1$ ,

$\ldots$,$r$, and

$\lambda(\sum A_{j})=(a_{1}^{(0)}, \ldots, a_{n}^{(0)})$

if

and _$on/y$

if

$\sum_{j}a_{j}^{(0)}=\sum_{j}a_{j}^{\langle 1)}+\cdots+\sum_{j}a_{j}^{(f)}$

and

_for

any $(J_{0}, J_{1}, ., ., J_{r})\in LR_{m}^{n}(r)$ with$m<n$

$\sum_{j\in J_{0}}a_{J}^{(0)}\leq\sum_{j\in J_{1}}a_{j}^{(1)}+\cdots+\sum_{j\in J},$

$a_{j}^{(r\}}$

.

It isinteresting that the sameset ofinequalities governthe eigenvalues of the

sum

ofHermitian

matrices

over

real, complex, or real quaternions. To elaborate this comment, note that for every

$A=[a_{ij}]\in \mathrm{H}_{n}$ there are $A_{1}$,$\ldots$,$A_{n}\in \mathrm{H}_{n}$ with the same eigenvalues

as

$A$ suchthat

diag$(a_{11}, \ldots , a_{nn})=\frac{1}{n}(A_{1}+\cdots+A_{n})$

.

In fact, if$w=e^{2\pi i/n}$ _{and $D=$ diag}$(1, w, \ldots, w^{n-1})$, then

diag$(a_{11}, \ldots, ann)$ $= \frac{1}{n}(\sum_{j=1}^{n}D^{j}A(D^{j})^{*})$ .

Now, by Theorem 1.3, the

same

result holds for real symmetricmatrices. However,

even

for$n=3$,

it is hard to construct $B_{1}$,$B_{2},B_{3}!$ Let

us

consider the following.

Example 1.4 Let

$A=(\begin{array}{lll}4 2 12 3 11 1 1\end{array})$ , $D=(\begin{array}{lll}1 0 00 e^{i2\pi}/3 00 0 e^{i4\pi}/3\end{array})$

.

Then $B_{1}=D^{*}AD$,$B_{2}=(D^{2})^{*}AD^{2},B_{3}=A\in \mathrm{H}_{3}$satisfy

(a) $\lambda(A)=\lambda(B_{1})=\lambda(B2)=\lambda(B_{3})$, and

(b) $(\begin{array}{lll}4 0 00 3 00 0 1\end{array})=\frac{1}{3}(B_{1}+B_{2}+ \mathrm{S}_{3})$

.

Even for this specific example, it is not

easy

to construct $B_{1}$,$B_{2}$,$B_{3}\in \mathrm{S}_{3}$ such that (a) and (b)

2

Principal

Submatrices

of

a

Hermitian

Matrix

Using the result

on

the

sum

ofHermitian matrices, we

can

obtain inequalities relating the

eigen-values of a Hermitian matrix and those of the principal submatrices. Here is the specific problem.

Problem Study the relations between the eigenvalues of$A\in \mathrm{H}_{n}$ and those of its principal

sub-matrices,

Again, let

us

beginby describing

some

well known results;

see

$[1, 3]$

.

.

There is$A\in \mathrm{H}_{n}$ with thevector of diagonal

entries

($d_{1}$,

$\ldots$,$d_{n}\rangle$ ifandonly ifit is majorized by $\lambda(A)$, i.e., $\sum_{j=1}d_{j}=\sum_{j=1j}^{n}\lambda(A)$ and for $k=1$,$\ldots$,$n-1$

.

.

There is $A\in \mathrm{H}_{n}$ with

an

$m\cross$ $m$ principal submatrix $B\in \mathrm{H}_{m}$ such that $\lambda(A)=(a_{1}$,

. .

.,$a_{n})$

and $\lambda(B)=(b_{1}, \ldots, b_{m})$ ifand only if

$a_{j}\geq b_{j}\geq a_{n-m+j}$ for$j=1$, $\ldots$,$m$.

We

have thefollowing result;

see

[14].

Theorem 2.1 There is$A=(_{*}^{A_{1}}$ $A_{2}*)\in \mathrm{H}_{n}$ with $\lambda(A)=(a_{1}, \ldots, a_{n})$, $A_{1}\in \mathrm{H}_{k}$ and$A_{2}\in \mathrm{H}_{n-k}$

such that

$\mathrm{A}(\mathrm{A})=(a_{1}^{(1)}, \ldots, a_{k}^{(1)})$ and $\lambda(A_{2})=(a_{1}^{(2)}, \ldots, a_{n-k}^{(2)})$

if

and only

_if

$\sum_{j}a_{j}=\sum_{j}a_{j}^{(1)}+\sum_{j}a_{j}^{(2)}$

and

_for

any ($J0$,$J_{1}$,J2) $\in LR_{m}^{n}$ with $m<n$

$\sum_{\mathrm{i}\in J_{0}}(a_{j}-a_{n})\leq\sum_{j\in J_{1}}(a_{j}^{(1)}-a_{n})+\sum_{j\in J_{2}}(a_{j}^{(2)}-a_{n})$,

here $a_{j}^{\langle s)}=a_{n}$ whenever$j>n_{s}$.

More generally,

we

have the following.

Theorem 2.2 Suppose $n_{1}+\cdots+n_{r}=n$

.

There exists $A=(A_{ij})_{1\leq i,j\leq r}\in \mathrm{H}_{n}$ such that $\lambda(A)$ $=$

$(a_{1}, \ldots, a_{n})$, and

$A_{jj}\in \mathrm{H}_{n_{j}}$ with

$\lambda(A_{jj})=(a_{1}^{(j)}, \ldots, a_{n_{\mathrm{j}}}^{(j)})$

for

$j=1$,

$\ldots$,$r$

if

and only

if

and

_for

any (Jo,$J_{1}$,

$\ldots$,$J_{r}$) $\in LR_{m}^{n}(r)$ with $m<n$

$\sum_{J\in J_{0}}(a_{j}-a_{n})\leq\sum_{s=1j}^{r}\sum_{\in J_{s}}(a_{j}^{(s)}-a_{n})$ ,

here $a_{j}^{(s)}=a_{n}$ whenever_{$j>n_{s}$}.

Similar to the results

on

the

sum

ofmatrices,

one

would like to reduce the list of inequalities.

For each $s=1$,$\ldots$$\dot,$

$r$, only consider $J_{s}=$ $(j_{1}^{(s)}, \ldots, j_{m}^{(s)})$ such that either $j_{m}^{(s)}\leq n_{s}$

or

the last $p$

terms have the form: $n_{s}+1$,$n_{s}+2$,$\ldots$,$n_{s}+p$. Also, we did the

case

when $nj\leq 2$. To describe

the result, we need

some

more

notation.

Suppose $A_{ii}\in \mathrm{H}_{2}$ has eigenvalues $a_{1}^{(i)}\geq a_{2}^{(i)}$ for $1\leq \mathrm{i}\leq m$, and $A_{ii}=[a_{1}^{(i)}]\in \mathrm{H}_{1}$ for $m+1\leq \mathrm{i}\leq n-m$ Let $(1, \cdots, im)$ be

a

permutation of $($1, $\cdots$, $m)$ such that $a_{2}^{(i_{1})}\geq\cdots\geq a_{2}^{(x_{m})}$

.

For any subset $R\subseteq\{1, \cdots , m\}$ with _$|R|=r$, let $b_{1}^{R}\geq\cdots\geq b_{n-m-2r}^{R}$ be theeigenvalues of$\oplus_{i\not\in R}A_{\dot{\mathrm{t}}}$

.

Theorem 2.3 There exists $A=(A_{ij})\in \mathrm{H}_{n}$ with eigenvalues $c_{1}\geq\cdots\geq c_{n}$, such that$A_{ii}\in \mathrm{H}_{2}$ has eigenvalues $a_{1}^{(i)}\geq a_{2}^{(i)}$

for

$1\leq \mathrm{i}\leq m$, and $A_{ii}=[a_{1}^{(i\rangle}]\in \mathrm{H}_{1}$

for

$m+1\leq \mathrm{i}\leq n$

-$m$

if

and only

if

$\sum_{i=1}^{n}c_{i}=\sum_{i=1}^{n-m}a_{1}^{(i)}+\sum_{i=1}^{m}a_{2}^{(i)}$

and

_for

any $(s, t)\in\{0, \cdots, m\}$ $\mathrm{x}\{0, \ldots, n-2s\}$ with

$0<s+t<n$

and any $s$ element subset

$S\subseteq\{\mathrm{i}_{1}, \cdots, \mathrm{i}\ell\}$ with $\ell=\min\{m, s+t\}$, we have

$\sum_{l=1}^{t}c_{\iota}+\sum_{i=t+2}^{s+t+1}c_{i}\geq\sum_{j\in S}a_{2}^{(j)}+\sum_{i=1}^{t}b_{i}^{S}$

.

3

OfF-diagonal blocks

In this section, we study the following.

Problem Determine whena matrix $X\in M_{k,n-k}$

can

be theoff-diagonal block of

a

matrix $C\in \mathrm{H}_{n}$

with prescribed eigenvalues.

Observation There is $C=(_{X^{*}}^{*}$ $X*)\in \mathrm{H}_{n}$ with $\mathrm{X}(\mathrm{C})=(1, \ldots,Ca)$ if andonly if there

are

(for

any) unitary matrices $U\in M_{k}$ and $V\in M_{n-k}$ thematrix

$\tilde{C}=$

(

_{$UXV*)\in \mathrm{H}_{n}$} w.th _{$\lambda(\tilde{C})=(c_{1}$},

.

.

.,$c_{n})$.

Denote by $s(X)=(s_{1}(X), \ldots, s_{k}(X))$ the vector ofsingular values of $X\in M_{k,n-k}$ with entries

We have the followingresult; [15].

Theorem 3.1 Let $c_{1}\geq\cdots\geq c_{n}$ and $s_{1}\geq\cdots\geq s_{k}\geq 0$ be given, where $k\leq n/2$

.

The following

are

equivalent.

(a) There is $C=(_{X^{*}}^{*}$ $X*)\in \mathrm{H}_{n}$ such that _{$X\in M_{k,n-k}$}, $\lambda(C)=(c_{1}, \ldots,c_{n})$ and $s(X)=$

$(s_{1}, \ldots, s_{k})$

.

(b) There exist $C_{1}$,$C_{2}$,$S\in \mathrm{H}_{k}$ such that $C_{1}$ – $C_{2}\geq 2S$, where $\lambda(C_{1})=(c_{1}, \ldots,c_{k})$, $\lambda(C_{2})=$

$(c_{n-k+1}, \ldots, c_{n})$, and A(S) $=(s_{1}$,

.

. .,$s_{k})$. (c) For each ($J_{0}$,$J_{1}$,J2) $\in LR_{m}^{k}$ with$m\leq k$

2$\sum_{j\in J_{0}}s_{j}\leq\sum_{\mathrm{j}\in J_{1}}c_{j}-\sum_{j\in J_{2}}c_{n-\mathrm{J}}+1$

.

There

are

some

interesting

consequences

of this theorem. Let $S_{k}(c)$ be the set of $k\mathrm{x}$ $(n-k)$

matrices

for the

existence

of$C=(_{X^{*}}^{*}$ $X*)\in \mathrm{H}_{n}$ with $\lambda(C)=c=(c_{1}, \ldots, c_{n})$

.

.

Suppose$X\in S_{k}(c)$

.

Thenforany

contractions

$R\in M_{k}$ and$T\in M_{n-k}$,

we

have$RXT\in S_{k}(c)$

.

In particular, if$X\in S_{k}(c)$ then $tX\in S_{k}(c)$ for any $t\in[0,1]$. So, $S_{k}(c)$ is star-shaped with

the

zero

matrix

as

the star-center.

.

Theset $S_{k}(c)$ is

convex

ifand only if$(c_{1}$,. .

.

’$c_{k})$ and $(c_{n-k+1}, \ldots, c_{n})$

are

arithmetic

progres-sions with the

same

common

difference.

4

Complex

Symmetric

Matrices

In this section,

we

consider the following.

Problem Study the singular values ofthe off-diagonal blocks of complex symmetric and general

matrices.

It turnsout that there

are

not much differencebetween complexsymmetric

or

general matrices

withreal symmetric matrices! We have the following result;

see

[4].

Theorem 4.1 Let$\gamma_{1}\geq\cdots\geq\gamma_{n}$ and $s_{1}\geq\cdots\geq s_{k}\geq 0$ be given, where $k\leq n/2$. The following

are equivalent.

(a) There is a symmetric

matrix

$C=(_{X}^{*}t$ $X*)\in M_{n}$ wilh $X\in M_{k,n-k}$, $s(C)=(\gamma_{1}, \ldots, \gamma_{n})$

(b) There is $C=$ $(\begin{array}{ll}* YZ *\end{array})$ $\in M_{n}$ with $s(C)=(\gamma_{1}, \ldots, \gamma_{n})$ such that $Y$,_{$Z\in M_{k,n-k}$} have $a$

combined list

_of

singular values: si, $s_{1}$,$s2$, $s_{2}$,$\ldots$,$s_{k}$,$s_{k}$.

(c) There exists

a

real symmetric matr$rixC=(_{X^{t}}^{*}$ $X*)$ such that $X\in M_{k,n-k}$, $s(X)=$

$(s_{1}, \ldots, s_{k})$,

an

$d$

$\lambda(C)=(\gamma_{1}, -\gamma_{2}, \gamma_{3}\ldots, (-1)^{n}\gamma_{n})$

.

(d) There exist$C_{1}$,$C_{2}$,$S\in \mathrm{H}_{k}$ such that$C_{1}+C_{2}\geq 2S$ with A(S) $=(s_{1}, \ldots , sk)$,

$\lambda(C_{1})=(\gamma_{1}, \gamma_{3}\ldots, c_{2k-1})$, and $\lambda(C_{2})=(\gamma_{2}, \gamma_{4}, \ldots, \gamma_{2k})$.

(e) For each (Jo,$J_{1},$$J_{2}$) $\in LR_{m}^{k}$ with $m\leq k$

2$j \sum_{\in J_{0}}s_{j}\leq\sum_{j\in J_{1}}\gamma_{2j-1}+\sum_{j\in J_{2}}\gamma_{2j}$.

Again, there are some interesting consequences ofthis result.

.

If$X\in M_{k,n-k}$ is the $(1, 2)$ block of $C\in \mathrm{H}_{n}$ with eigenvalues values $c_{1;}\ldots$,$\mathrm{c}_{n}$, such that

$|c_{1}|\geq\cdots\geq|c_{n}|$, then$X$ is the $(1, 2)$ block of$\tilde{C}\in \mathrm{H}_{n}$ with eigenvalues

$|c_{1}|,$$-|c_{2}|$,$|c_{3}|,$$-|c_{4}|$, $\ldots$

.

.

If $A$,$B$,$C\in \mathrm{H}_{n}$ satisfies $C=A+B$ and the combined list of eigenvalues of $A$ and $B$ is

$\gamma_{1}\geq\cdots\geq\gamma_{2n}$, then $C=\tilde{A}+\tilde{B}$ suchthat

$\lambda(\overline{A})=(\gamma_{1}, \gamma_{3}, \ldots, \gamma_{2n-1})$ and $\lambda(\tilde{B})=(\gamma_{2},$

$\gamma_{4}$,$\ldots$,$\gamma_{2n^{\}}},$

.

.

Same result work for $A_{0}=A_{1}+\cdots+A_{r}$, we

can rearrange

the eigenvalues:

$\tilde{A}_{1}$ has eigenvalues

$\gamma_{1},\gamma_{r+1},\gamma_{2r+1}$, $\ldots$

$\tilde{A}_{2}$ has eigenvalues

$\gamma_{2},\gamma_{r+2},\gamma_{2r+2}$,$\ldots$

$\tilde{A}_{3}$

5

Future

research

There

are

many interesting problems deserve further study. We mention

a

few ofthem in the following.

.

Determine numerical algorithms to construct the

matrices

withdesired properties.

.

Studythe relationsbetween the singular values ofcomplementary blocks;

see

$[4, 16]$

.

$\bullet$ Study therelationsbetween the singularvaluesof$C$ and thoseof

$S$,

or

those of$R$and $T$, for

$C=(\begin{array}{ll}R 0S T\end{array})$;

see

[13].

$\bullet$ Study the implications ofthe results in the real world!

Acknowledgement

Li is an honorary professor of the Heilongjiang University, and also

an

honorary professor of theUniversityof Hong Kong. His research

was

partiallysupportedby

a

USA NSF grant andaHK

RCG

grant. Hewould liketo thankProfessorK. Okubo forhosting hisvisit to Sapporo and Kyoto

in 2004, thesupport oftheHokkaido University of Education in Sapporo, theHokkaido University,

and the Kyoto University, and also the Grant-Aid for Science Research (number 15540148) from

References

[I] R. Bhatia, Matrix Analysis, Springer, New York,

1996.

[2] J. Day, W. So and R.C. Thompson, The spectrum of

a

Hermitian

matrix

sum, Linear

Algebra AppL

280

(1998),

289-332.

[3] K. Fan and G. Pall, Imbedding conditions for Hermitianand normal matrices, Canad. J.

Math. 9 (1957),

298-304.

[4]

S.

Fomin, W. Fulton,

C.K.

Li, and Y.T. Poon, Eigenvalues, singular values, and

Littlewood-Richardsoncoefficients, Amer. J. Math., to appear.

[5] W. Fulton, Young Tableaux, Cambridge University Press,

1997.

[6] W. Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus, Bull

Amer. Math. Soc.

37

(2000),

209-249.

[7] W. Fulton, Eigenvalues ofmajorized Hermitian matrices, and Littlewood-Richardson

co-eflicients, Linear Algebra AppL

319

(2000),

23-36.

[8] A.Horn, Eigenvalues of

sums

ofHermitian matrices,

_Pacific

J. Math. 12 (1962), 225-241.

[9] A.A. Klyachko, Stable bundles, representation theory and Hermitian operators, Selecta

Math. (N. S.) 4 (1998),

419-445.

[10] A. Knutson and T. Tao, The honeycomb model of$\mathrm{G}\mathrm{L}_{n}(C)$ tensor products. I. Proof of

the saturation conjecture, J. A rner. Math. Soc. 12 (1999),

no.

4,

1055-1090.

[11] A. Knutson and T. Tao Honeycombs and

sums

ofHermitian matrices, Notices Amer.

Math. Soc.

48

(2001),

no.

2,

175-186

[12] A. Knutson, T. Tao, and C. Woodward, Honeycombs II: Facets of the

Littlewood-Richardson cone,to appear.

[13] C.K. LiandR.Mathias,Inequalities onsingular values ofblocktriangularmatrices, SIAM

Matrix Analysis AppL 24 (2002),

126-131.

[14] C.K. Li andY.T. Poon, Principal submatrices of

a

Hermitian matrix, Linear and

Multi-linear Algebra

51

(2003),

199-208.

[i5] C.K. Li and Y.T. Poon, Off-diagonal submatrices of

a

Hermitian matrix, Proc. Amer.

Math. Soc.

132

(2004),

2849-2856.

[16] $\mathrm{R}.\mathrm{C}$

.

Thompson, Singular values,

diagonal elements, and convexity,

SIAM

J. AppL

[17] $\mathrm{R}.\mathrm{C}$

.

Thompson and $\mathrm{L}.\mathrm{J}$. Freede, Eigenvalues of paxtitioned Hermitian matrices, Bulletin