# Equivalence of $\|x\|_1\|x\|_{\infty}$ and $\|x\|_2^2$

Let $x$ be any complex $n$-vector and let $\|\cdot\|_p$ denote the usual $p$-norm. It is easy to show that $\|x\|_2^2\leq\|x\|_1\|x\|_{\infty}$ (Hölder's inequality). What I am rather interested in is the reversed inequality: finding a $c$ ($c>1$) such that $$\tag{1} \|x\|_1\|x\|_\infty\leq c\|x\|_2^2\quad\text{for all x.}$$ Obviously, $\|x\|_1\leq\sqrt{n}\|x\|_2$ and $\|x\|_\infty\leq\|x\|_2$, so an easy candidate is $c_\mathrm{naive}:=\sqrt{n}$. However, it seems that a better constant is about a half of the naive one: $c_\mathrm{better}:=(1+\sqrt{n})/2$. I was wondering about a proof for this better $c$, that is, how to prove that

$$\tag{2}\|x\|_1\|x\|_\infty\leq\frac{1+\sqrt{n}}{2}\|x\|_2^2\quad\text{for all x\in\mathbb{C}^n.}$$

WLOG we can assume that $x:=[1,y^T]^T$, where $\|y\|_\infty\leq 1$, so the quest for the optimal $c$ in (1) is equivalent to finding (or bounding from above) $$\tag{3} c_\mathrm{optimal}:=\max_{\|y\|_\infty\leq 1}\frac{1+\|y\|_1}{1+\|y\|_2^2}\;.$$ By some experimentation, it seems that actually (2) is sharp, that is, $c_\mathrm{optimal}=c_\mathrm{better}$, and the bound in (2) is attained by $x=[1,\alpha,\ldots,\alpha]^T$, where $\alpha=1/(\sqrt{n}+1)$.

Since this is a problem in an early chapter of Matrix Computations by Golub and Van Loan, I suppose its prove might be not overly complicated and, since a hint is missing, it should actually be quite easy. Any input will be highly appretiated; a hint if possible :-)

Let $x$ be a vector in $\mathbb R^n$ with non-negative entries. Assume $x_1$ is the largest of them. Then we have to prove $$x_1 \cdot \sum_{i=1}^n x_i \le c \sum_{i=1}^n x_i^2.$$ My idea is to estimate for $i\ne 1$ with $a>0$ $$x_1 x_i \le \frac1{2a}x_1^2 + \frac a2 x_i^2.$$ In order to obtain a balanced estimate, $$1+(n-1)\frac1{2a} = \frac a2$$ is required. Setting $a= 1+\sqrt n$ gives $c=\frac{1+\sqrt n}2$.

• Nice. I was already thinking about Peter-Paul, but it seems that not hard enough. – Algebraic Pavel May 6 '15 at 12:20

As you know, $$1 + \|y\|_1 \le 1 + \sqrt{n-1}\|y\|_2$$ so it would suffice to show $$1 + \sqrt{n-1}\,\|y\|_2 \le \frac{1+\sqrt n}{2}(1+\|y\|_2^2)$$ In this inequality (if it's true), the fact that $\|y\|_2$ is the norm of a vector doesn't seem to have any significance... it's just a number, here.

Since you requested only a hint, I'll stop here.

• Thanks. Now I feel a bit embarassed :-) – Algebraic Pavel May 6 '15 at 12:24
• It's bad I cannot accept more than one answer but the other was a few seconds faster and both are equally nice. – Algebraic Pavel May 6 '15 at 12:34

When all the coordinates are equal you have $\|x\|_2^2\leq\|x\|_1\|x\|_{\infty}$ (with equality indeed but I don't know to write this with TeX Commands). Consequently you cannot have c > 1 as the constant you expected. (I think I was a little confused!)

• I don't understand what do you mean (probably). I already knew that $\|x\|_2^2\leq\|x\|_1\|x\|_\infty$, attainable, e.g,. with $x=[1,0,\ldots,0]^T$. The question was about the reversed inequality. – Algebraic Pavel May 7 '15 at 15:38