Validity of $\sum\limits_{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!


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.


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.

Tags:

Inequality