16
$\begingroup$

Let's say you are in $\mathbb{R}^n$ and you define the norm as $||x||=\sqrt{x_1^2+x_2^2...+x_n^2}$. This we recognize as the usual norm from the inner product: $||x|| = \sqrt{\langle x, x \rangle}$, where $\langle x, y \rangle = x_1 y_1 + x_2 y_2+ \cdots + x_n y_n$. It is easy to check that this satisfies all the axioms for an inner product. Then we may define orthogonality as a zero inner product, and we get the Pythagorean theorem, we define projection, and then the proof for Cauchy–Schwarz is pretty straight forward.

But now comes my problem. Lets say you do not want to go through the inner product, but you still want to prove Cauchy–Schwarz. When you do not have an inner product, Cauchy–Schwarz do not make much sense, but I want the part where we have replaced the inner-product part.

I mean, Cauchy–Schwarz says: $|\langle x, y \rangle| \le ||x|| \cdot ||y||$. This equation makes sense even without inner-products for our case:

$\left| x_1 y_1 + x_2 y_2 + \cdots + x_n y_n \right| \le \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2} \cdot \sqrt{y_1^2 + y_2^2 + \cdots + y_n^2}$

However I am not able to prove this inequality. For me, it is easier going through the inner product for proving this, but I want to be able to prove this inequality directly, how am I supposed to do that?

That is, my problem is proving that

$\left| x_1 y_1 + x_2 y_2 + \cdots + x_n y_n \right| \le \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2} \cdot \sqrt{y_1^2 + y_2^2 + \cdots + y_n^2}$

without going through the inner product. Is this hard? Would you say it is easier defining the inner-product and proving it in that way? It seems weird that it should be easier to define a lot of new terms just to prove an inequality.

$\endgroup$
2
  • 4
    $\begingroup$ When you formulate the Cauchy-Schwarz inequality for a general inner product space, it is clear that it must be a consequence of the inner product being bilinear and positive definite, since that is all you have to work with. From there it's just a matter of figuring out how to exploit these properties. When you just write it in terms of variables it is not immediately clear what properties of the formula are relevant, so part of the difficulty is figuring out which properties of the formula you should be trying to exploit. $\endgroup$
    – Nate
    Mar 24, 2014 at 18:32
  • 1
    $\begingroup$ For future reference: use \langle and \rangle for $\langle$angle brackets$\rangle$ and \| for $\|$norms$\|$. It looks better. $\endgroup$
    – user856
    Mar 24, 2014 at 19:17

6 Answers 6

19
$\begingroup$

I thought I never did it directly, but now that I have found the solution below (quite quickly), I begin to suspect that I must have done something similar years ago.

Anyway, as a first step, let's square everything. Then we need to prove this: $$ \left(\sum_i x_i y_i\right)^2 \leq \left(\sum_i x_i^2\right)\left(\sum_j y_j^2\right). $$ Let's subtract the left from the right and open all the parentheses: $$ \begin{align*} \left(\sum_i x_i^2\right)\left(\sum_j y_j^2\right) - \left(\sum_i x_i y_i\right)^2 & = \sum_{i,j}x_i^2 y_j^2 - \sum_{i, j}x_i y_i x_j y_j \\ & = \sum_{i \neq j} x_i^2 y_j^2 - \sum_{i \neq j} x_i y_i x_j y_j \\ & = \sum_{i < j} (x_i^2 y_j^2 + x_j^2y_i^2 - 2 x_i y_i x_j y_j) \\ & = \sum_{i < j} (x_i y_j - x_j y_i)^2 \end{align*} $$ Here indices $i$ and $j$ always iterate from $1$ to $n$. We see that this is a sum of several squares, so it is nonnegative, proving the original inequality.

UPDATE: the very same thing can be done for complex numbers. We want to prove this: $$ \left|\sum_i x_i \overline{y_i}\right| \leq \sqrt{\sum_i x_i \overline{x_i}} \cdot \sqrt{\sum_j y_j \overline{y_j}}. $$ Let us square everything, keeping in mind that $|z|^2 = z\overline{z}$: $$ \left( \sum_i x_i \overline{y_i} \right) \left(\sum_j \overline{x_j} y_j\right) \leq \left( \sum_i x_i \overline{x_i} \right) \left(\sum_j y_j \overline{y_j}\right) $$ As before, we subtract the left from the right: $$ \begin{align*} & \left( \sum_i x_i \overline{x_i} \right) \left(\sum_j y_j \overline{y_j}\right) - \left( \sum_i x_i \overline{y_i} \right) \left(\sum_j \overline{x_j} y_j\right) \\ & = \sum_{i,j}x_i\overline{x_i}y_j\overline{y_j} - \sum_{i, j}x_i \overline{y_i} \overline{x_j} y_j \\ & = \sum_{i \neq j} x_i\overline{x_i}y_j\overline{y_j} - \sum_{i \neq j} x_i \overline{y_i} \overline{x_j} y_j \\ & = \sum_{i < j} (x_i \overline{x_i} y_j \overline{y_j} + x_j \overline{x_j} y_i \overline{y_i} - x_i \overline{y_i} \overline{x_j} y_j - x_j \overline{y_j} \overline{x_i} y_i) \\ & = \sum_{i < j} |x_i y_j - x_j y_i|^2 \end{align*} $$ As before, we have a sum of squares of real numbers, which is real and nonnegative. Done.

$\endgroup$
5
  • $\begingroup$ Thank you very much. Do you see if it is alot of work to extend your example to the complex case? That is to prove that: $|x_1\bar{y_1}+x_2\bar{y_2}...+x_n\bar{y_n}|\le \sqrt{x_1\bar{x_1}+x_2\bar{x_2}...+x_n\bar{x_n}}*\sqrt{y_1\bar{y_1}+y_2\bar{y_2}...+y_n\bar{y_n}}$? $\endgroup$
    – user119615
    Mar 24, 2014 at 18:44
  • $\begingroup$ This can be done. If Dan does not do it first, will do it below. $\endgroup$ Mar 24, 2014 at 18:45
  • $\begingroup$ @user119615 It is precisely the same amount of work. I'll add the complex case to my answer now. $\endgroup$
    – Dan Shved
    Mar 24, 2014 at 18:46
  • $\begingroup$ I'll delete my answer then $\endgroup$ Mar 24, 2014 at 19:01
  • 2
    $\begingroup$ Related: en.wikipedia.org/wiki/Lagrange's_identity $\endgroup$
    – user940
    Mar 24, 2014 at 20:27
9
$\begingroup$

It's not hard. In fact the first proof that I encountered in high school was without using inner products. It goes as follows:

Consider the quadratic $$\sum_{i=1}^{n} (a_ix+b_i)^2 = (\sum_{i=1}^{n}a_i^2)x^2 + 2 (\sum_{i=1}^{n}a_ib_i)x + (\sum_{i=1}^{n}b_i^2)$$

Since the quadratic expression is always non negative, its discriminant must be $\leq 0$ [1]. i.e. $$(\sum_{i=1}^{n}a_ib_i)^2 - \sum_{i=1}^{n}a_i^2\sum_{i=1}^{n}b_i^2 \leq 0$$

from where the inequality follows. Equality occurs iff $$x = \frac{b_i}{a_i} \forall i$$

[1] This follows because its non-negativity implies that it never crosses the x-axis (which means that it has either no real roots, in which case the discriminant is negative, or it has a double root, in which case the discriminant is 0).

$\endgroup$
3
  • $\begingroup$ could you explain Since the quadratic expression is always non negative, its discriminant must be $\leq 0$ a bit more. $\endgroup$ Mar 25, 2014 at 1:05
  • $\begingroup$ Consider $ax^2+bx+c$. By the quadratic equation, this has two (distinct) real roots iff $b^2-4ac>0$, one real (repeated) root iff $b^2-4ac=0$ and two complex roots iff $b^2-4ac<0$. I believe @Sandeep has a typo and the first term, $(\sum a_ib_i)^2$ should be multiplied by $4$, since there is a $2$ in front of the original expanded term. But the inequality still holds because then we have $$(\sum_{i=1}^{n}a_ib_i)^2 - \sum_{i=1}^{n}a_i^2\sum_{i=1}^{n}b_i^2\leq 4(\sum_{i=1}^{n}a_ib_i)^2 - \sum_{i=1}^{n}a_i^2\sum_{i=1}^{n}b_i^2 \leq 0$$ $b^2-4ac$ is called the discriminant $\endgroup$ Mar 25, 2014 at 13:09
  • $\begingroup$ Very nice proof, but I do not udnerstand the part when we have equality iff $x=\frac{b_i}{a_i}, \forall i$, isn't the point of this proof that x is a variable? $\endgroup$
    – user119615
    Mar 25, 2014 at 14:32
4
$\begingroup$

Essentially Dan's prove doesn't avoid inner products, since he proved that $\|x\|^2\|y\|^2-\langle x,y\rangle^2=$ Gram-determinant of $(x,y)$. So what qualifies my statement as an answer? Even if you don't use the notation of an inner product, it's inherently present at all.

$\endgroup$
3
$\begingroup$

It seems weird that it should be easier to define a lot of new terms, just to prove an inequality.

In general you can find many examples of problems (even inequalities) that are solved easier with the use of some mathematical machinery.

Dan Shved gave an excellent answer to your question. Let me just add that you could prove the inequality for n=2 and then use induction on n.

The trick in Sandeep Thilakan's answer can be used to prove the inequality in any inner product space.

A very nice didactic book about inequalities is The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities. Its first chapter is very relevant to your question.

$\endgroup$
2
  • $\begingroup$ Thanks! It says in the link that it may take some time to set up the machinery. What I think is fascinating is that the work in setting up the inner product-function, and its properties, then deriving Cauchy-Scwarz from that almost seems trivial, even though it is quite a lot of work, all the work is easy. And even though I understood Dans proof, it was technical. It almost seems magical that you are able to remove all the technical work, just by introducing the inner-product function. It seems magical, because when using innerprod it is not so clear in which step the technical work disappears $\endgroup$
    – user119615
    Mar 25, 2014 at 3:32
  • $\begingroup$ @user119615 On second thought, the first part of my answer was not much to the point: Going from the sum of products of real numbers to the definition of the inner product does not construct something new from scratch. On the contrary, it is a process of abstraction. It loses information, keeping the properties needed to prove the Cauchy-Schwarz inequality. The magic that you feel is, in the words of J.M. Steele, due to the benefits of good notation. $\endgroup$
    – posilon
    Mar 29, 2014 at 19:25
1
$\begingroup$

Here is another variant, which nicely illustrates how it is sometimes sufficient to prove a seemingly weaker inequality by exploiting its symmetries:

By Young's inequality (which is a simple consequence of $(\lvert x_k\rvert-\lvert y_k\rvert)^2\geq 0$ in this case), we have $\lvert x_k y_k\rvert\leq \frac 1 2x_k^2+\frac 1 2 y_k^2$. This implies $$ \left\lvert\sum_k x_k y_k\right\rvert\leq \frac 1 2 \sum_k x_k^2+\frac 1 2 \sum_k y_k^2. $$ Of course, the left side stays unchanged if we replace $x_k$ by $\lambda^{1/2} x_k$ and $y_k$ by $\lambda^{-1/2} y_k$ for $\lambda>0$. Thus $$ \left\lvert\sum_k x_k y_k\right\rvert\leq \frac {\lambda} 2 \sum_k x_k^2+\frac 1{2\lambda} \sum_k y_k^2. $$ In particular, if $\lambda=\left(\sum_k x_k^2\right)^{-1/2}\left(\sum_k y_k^2\right)^{1/2}$ [see remark below], then $$ \left\lvert\sum_k x_k y_k\right\rvert\leq \left(\sum_k x_k^2\right)^{1/2}\left(\sum_k y_k^2\right)^{1/2}. $$ The same argument works in arbitrary inner product spaces, just that one uses the Young-type inequality $\lvert\langle x,y\rangle\rvert\leq \frac 1 2 \lVert x\rVert^2+\frac 1 2 \lVert y\rVert^2$, which is an easy consequence of the semi-definiteness of the inner product.

Using Young's inequality $\lvert x_k y_k\rvert\leq \frac 1 p \lvert x_k\rvert^p+\frac 1 q \lvert y_k\rvert^q$ with dual exponents $p$ and $q$, one can also obtain Hölder's inequality along the same lines.

Remark: Of course $x$ should not be zero here. The case $x=0$ can either be treated separately or one can take $\lambda=\left(\sum_k x_k^2+\epsilon\right)^{-1/2}\left(\sum_k y_k^2\right)^{1/2}$ and let $\epsilon\searrow 0$ in the end. Also, this choice of $\lambda$ is not arbitrary, it is the value you get if you minimize the right side in $\lambda$. In this sense Cauchy-Schwarz is the optimal form of Young's inequality with respect to the dilation symmetry $x\mapsto \lambda x$, $y\mapsto \lambda^{-1}y$ of the left side.

$\endgroup$
0
$\begingroup$

As with most things the proof isn't tricky when you know how!

Define two norms for $x \in \mathbb{R^n}$ as follows:

$$ \|x\|_1 := \sum_{i=1}^n |x_i|$$

and

$$ \|x\|_2 := (\sum_{i=1}^n |x_i|^2)^{1/2}.$$

For $x,y \in \mathbb{R^n}$ I will define $xy:= x \cdot y$ as a convenient short hand.

To prove your required inequality, it suffices (by the triangle inequality) to show that

$$\forall x,y \in \mathbb{R^n} \ \ \|xy\|_1 \leq \|x\|_2\|y\|_2.$$

To this end, note that

$$\forall a,b \in \mathbb{R}_{+} \quad 0 \leq \|(ax+by)^2\|_1 = a^2\|x^2\|_1 + 2ab\|xy\|_1 + b^2\|y^2\|_1.$$

Dividing through by $b^2$, and setting $\lambda:= a/b$ results in this inequality:

$$\forall \lambda>0 \quad 0 \leq \lambda^2\|x^2\|_1 + 2\lambda\|xy\|_1 + b^2\|y^2\|_1.$$

We can conclude that there are no positive real roots of this quadratic in $\lambda$. Therefore, we know that the determinant must be non-positive, i.e.

$$ (2\cdot \|xy\|_1)^2 \leq 4\|x^2\|_1 \|y^2\|_1.$$

Dividing both sides by $4$ and taking square roots gives:

$$\|xy\|_1 \leq \|x^2\|_1^{1/2} \|y^2\|_1^{1/2} = \|x\|_2\|y\|_2,$$

as required.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .