7
$\begingroup$

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 :-)

$\endgroup$
6
$\begingroup$

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$.

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

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.

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

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!)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Algebraic Pavel May 7 '15 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.