# Validity of $\sum_{i=1}^n(a_i^2+b_i^2+c_i^2+d_i^2)\lambda_i\geq\lambda_1+\lambda_2+\lambda_3+\lambda_4$?

Suppose that $\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n$ is a sequence of real numbers. Clearly, if $a=(a_1,\dots, a_n)$ is a unit vector, then $\sum_{i=1}^na_i^2\lambda_i\geq \lambda_1$. I want to see if the following generalization is true or not: If $a=(a_1,\dots, a_n)$, $b=(b_1,\dots, b_n)$, $c=(c_1,\dots, c_n)$, and $d=(d_1,\dots, d_n)$ ($n\geq 4$) form an orthonormal set, I wonder if we have $\sum_{i=1}^n(a_i^2+b_i^2+c_i^2+d_i^2)\lambda_i\geq\lambda_1+\lambda_2+\lambda_3+\lambda_4$.

-

The inequality is true.

Lemma Let $\lambda_1 \leq \ldots \leq \lambda_N$ be an increasing sequence of real numbers. Consider the set $\mathcal{A}_k := \{ (x_1,\ldots,x_N) \in [0,1]^N, \sum x_i = k \leq N\}$ of $N$-tuples inside the unit $N$ box, with total sum given by some real number $k$. Then $$\inf_{x\in \mathcal{A}_k} \sum_{i = 1}^N \lambda_i x_i = \sum_{i = i}^{\lfloor k \rfloor} \lambda_i + (k-\lfloor k\rfloor) \lambda_{\lceil k\rceil}$$

In other words: the lemma says that if you have $N$ different materials costing $\lambda_1\ldots \lambda_N$ per kilogram. You need to buy $k$ kilograms, but you are not allow to buy more than 1 kilogram of each type, then the cheapest way you can satisfy the requirement is to first buy 1 kilo of the cheapest stuff, then another kilo of the second cheapest, and so on until you used up all the money. The proof of the Lemma I'll leave as an easy exercise.

Now we can apply Lubos' observation. Namely that if $X_1, X_2, \ldots X_M$ are $M$ orthonormal vectors in $\mathbb{R}^N$ (with $M < N$), then $$P = X_1X_1^T + X_2X_2^T + \cdots X_MX_M^T$$ is a projection operator onto some $M$ dimensional subspace. In particular, as a projection, it cannot increase in length! This implies that for each unit vector $v$ $$v^TPv \leq 1$$ and in particular if we take $v$ to be the standard unit vector $e_i$, this says that the coordinate values $$\sum_{j = 1}^M (e_i^T X_j)^2 \leq 1$$

On the other hand, we also have the fact that for each fixed vector $X_j$, the normality condition $$\sum_{i = 1}^N (e_i^T X_j)^2 = 1$$

So in particular if we define the $N$-tuple $$Y_i = \sum_{j=1}^M (e_i^TX_j)^2$$ we have that $\sum_{i=1}^N Y_i = M$, and each individual component $Y_i\leq 1$. So in particular $Y_i \in \mathcal{A}_M$.

Your inequality then follows from the above observation combined with the Lemma.

Note that this also shows why in the case of $N = M$ the inequality must be saturated. The above process converts the problem to the case of the Lemma where you have $N$ types of material, you need to buy $N$ kilograms with no more than 1 kilo of each. So there's only one way of filling the purchase order!

-

If $a,b,c,d$ form an orthonormal basis, then the matrix with columns $a,b,c,d$ is an orthogonal matrix $A$ satisfying $AA^T=A^TA=1$. It follows that $$(a_i)^2+(b_i)^2 + (c_i)^2 + (d_i)^2 = 1$$ for each $i$ - because these four numbers are just the (squared) norms of the rows of $A$ which are also equal to one for an orthogonal matrix. So your final inequality is $$\lambda_1+\lambda_2+\lambda_3+\lambda_4 \geq \lambda_1+\lambda_2+\lambda_3+\lambda_4$$ which is true - in fact, it is always saturated. So the answer is "Yes, the inequality holds", but I wouldn't view it as a generalization of the original inequality because unlike the original one, it doesn't treat the smallest $\lambda_1$ differently from others and it is never satisfied "sharply".

If you're interested, I got the hint that the inequality is always an equality by substituting a rather nontrivial set of vectors - $\lambda = (0,0,0,1)$ and $a=(1/2,1/2,1/2,1/2)$, $b=(1/2,-1/2,-1/2,1/2)$, $a=(-1/2,1/2,-1/2,1/2)$, $a=(-1/2,-1/2,1/2,1/2)$. The vectors $a,b,c,d$ are weights of $SO(8)$ known to those who know the triality of $SO(8)$. The inequality was saturated so I decided it's always the case. And it is.

Higher-dimensional vectors

I was answering the original question in which the vectors $a,b,c,d$ were four-dimensional - at least I and Ross were reading it this way. If they're higher-dimensional, it's possible to lower $a_i^2+\dots + d_i^2$ by moving a part of this sum to $a_5^2, \dots d_5^2$, and so on, without destroying the orthonormality. This reduces $a_i^2+\dots + d_i^2$ for $i=1,2,3,4$ and changes nothing else, and because the inequality was saturated to start with, a further reduction of $a_i^2+\dots + d_i^2$ will make it invalid. A counterexample is in another answer.

However, the technology above allows us to prove exactly the opposite inequality than you wrote down: $$\sum_{i=1}^n(a_i^2+b_i^2+c_i^2+d_i^2)\lambda_i\leq\lambda_1+\lambda_2+\lambda_3+\lambda_4$$ is actually valid for any sequence of $\lambda's$ and any orthogonormal set of 4- or higher-dimensional vectors $a,b,c,d$. The inequality above is true because we may complete the set $a,b,c,d$ to an $n$-dimensional orthonormal basis. Then $$a_i^2 + b_i^2 + \dots m_i^2 = 1$$ by the same arguments as above ($m$ is the appropriate letter for the last $n$-th basis vector). It follows that $$a_i^2+ b_i^2+c_i^2+d_i^2 \leq 1$$ and the inequality above trivially follows.

-
Once I got my set ortogonalized, it didn't work. And your answer shows why. – Ross Millikan Jun 26 '11 at 15:28
Interesting, I jumped on the same intuition as you did - it couldn't be right, I thought, because the RHS didn't have the minimal $\lambda$ anymore. Of course, the catch is that the "generalization" has almost nothing to do with the original inequality. – Luboš Motl Jun 26 '11 at 15:30
I disagree with this: $\sum_{i=1}^n(a_i^2+b_i^2+c_i^2+d_i^2)\lambda_i\leq\lambda_1+\lambda_2+\lambda_3‌​+\lambda_4$ To provide a counter example, I could find a, b, c, d such as $a_i=b_i=c_i=d_i=0$ for $i=1..4$; for example $a=(0,0,0,0,1,0,...)$, $b=(0,0,0,0,0,1,0,...)$, $c=(0,0,0,0,0,0,1,0,...)$, $d=(0,0,0,0,0,0,0,1,0,...)$, and then set $\lambda_1,...,\lambda_4<0$, and the other $\lambda>0$. I think the fact that the there are $n$ $\lambda$'s and only 4 orthogonal vectors gives us the freedom to come up with a counter example for lots of inequalities here. – S4M Jun 26 '11 at 16:39
There's a hole in the final argument: to saturate the inequality as in the 4 dimensional case you need $\sum_{i = 1}^n (a_i^2 + \cdot + d_i^2)\lambda_i \leq \lambda_1 + \cdots + \lambda_n$ !! On the right hand side you only have up to $\lambda_4$. In fact, by moving "parts of $d_3$ to $d_5$, let's say, you gain a bit of $\lambda_5$, so it is not just a pure loss. – Willie Wong Jun 26 '11 at 17:20
Oh, I see, you're right. – Luboš Motl Jun 27 '11 at 20:09

The proof of equality can also be handled economically via properties of the trace operator. Let $Q = (q_{ij})$ be an $n \times n$ orthogonal matrix and $\Lambda$ a diagonal matrix with entries $\lambda_1\leq \lambda_2 \leq \cdots \leq \lambda_n$. Then note that

$$\newcommand{\tr}{\mathrm{tr}} \sum_{i=1}^n \big(\sum_{j=1}^n q_{ij}^2\big) \lambda_i = \tr( Q^T \Lambda Q ) = \tr( Q Q^T \Lambda ) = \sum_{i=1}^n \lambda_i \>,$$

and so we are done.

This can be generalized in the following way. Consider, instead, $Q$ as an $n \times m$ matrix with orthogonal columns (hence $m \leq n$). Then $$\sum_{i=1}^m \lambda_i \leq \sum_{i=1}^n \big(\sum_{j=1}^m q_{ij}^2\big) \lambda_i \leq \sum_{i=1}^m \lambda_{n-i} \>.$$

This result can be deduced from the following theorem.

Theorem (Richter): Let $A$ and $B$ be $n \times n$ hermitian matrices with eigenvalues $\alpha_1 \leq \alpha_2 \leq \cdots \leq \alpha_n$ and $\beta_1 \leq \beta_2 \leq \cdots \leq \beta_n$, respectively. Then $$\sum_{i=1}^n \alpha_i \beta_{n-i} \leq \tr(AB) \leq \sum_{i=1}^n \alpha_i \beta_i \> .$$

A simple proof of this result is found in

L. Mirsky, On the trace of matrix products, Math. Nachr., vol. 20, no. 3-6, pp. 171–174, 1959.

As pointed out in the aforementioned paper, there is a certain relationship with another more well-known result.

Theorem (von Neumann): Let $S$ and $T$ be arbitrary complex-valued $n \times n$ matrices. Let $(\sigma_i)$ and $(\tau_i)$ be the singular values of $S$ and $T$, respectively, in nonincreasing order. Then, $|\tr(ST)| \leq \sum_{i=1}^n \sigma_i \tau_i$.

A nice, elementary proof of this latter theorem can be found in

L. Mirsky, A trace inequality of John von Neumann, Monatsh. Math. 79 (4): 303–306, 1975, MR0371930.

-
Yes, Richter proves a set of upper and lower bounds that can be viewed as generalizations of the rearrangement inequalities. Mirsky gives an elementary proof of that result in another paper. I'll try to update my answer to provide that result shortly. – cardinal Jun 26 '11 at 21:40
@Willie: Edited (finally) as promised. – cardinal Jun 28 '11 at 23:59

It doesnt hold: if $\lambda_1=x<0$ and $\lambda_i=0, i=2..n$, your inequality becomes $(a_1^2+b_1^2+c_1^2+d_1^2)x\geq x$ which becomes false if we find and orthogonal system $(a,b,c,d)$ such as $a_1^2+b_1^2+c_1^2+d_1^2>1$. For example

$a=(\frac{\sqrt{2}}{2}, -\frac{\sqrt{2}}{2},0,...,0)$,

$b=(\frac{\sqrt{3}}{3},\frac{\sqrt{3}}{3},\frac{\sqrt{6}}{6},\frac{\sqrt{6}}{6},0,...,0)$,

$c=(\frac{\sqrt{6}}{6},\frac{\sqrt{6}}{6},-\frac{\sqrt{3}}{3},-\frac{\sqrt{3}}{3},0...,0)$,

$d=(0,0,0,0,1,...,0)$.

-
Uh, in your example, isn't the sum $a_1^2 + b_1^2 + c_1^2 = 1/2 + 1/4 + 1/4 = 1$? – Willie Wong Jun 26 '11 at 18:06
@Willie that's right! I edited my post to change $b$ and $c$ accordingly. – S4M Jun 26 '11 at 19:06
$1/2 + 1/3 + 1/6 = 1$ still... see my answer below. – Willie Wong Jun 26 '11 at 19:22