[Math] 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$

inequality

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\limits_{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\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$.

Best Answer

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!

Related Question