Cauchy-Schwarz

As the title suggests this post is all about the humble Cauchy-Schwarz inequality.

We will initially focus on some straightforward applications, which at first glance may not seem very obvious.

A proof of the Cauchy-Schwarz inequality can be found in any introductory text book on linear algebra/real analysis (or on Google).

Let’s start with a plain statement of the inequality:

Cauchy Schwarz Inequality:

Let (a_{i}) and (b_{i}) be finite sequences of real numbers.

Then \sum_{i=1}^{n} a_{i}b_{i} \leq \sqrt{\sum_{i=1}^{n} a_{i}^{2}}\sqrt{\sum_{i=1}^{n} b_{i}^{2}}\hspace{2 in}(1)

 
To better understand the intuition behind this inequality let us consider an alternative more general formulation using inner product spaces:

Let V be an inner product space over a field F.

Then \forall u,v \in V we have |\left\langle u, v \right\rangle| \leq ||u|| ||v||\hspace{1 in}(2).

We see immediately that (1) follows as a special case of (2) under the real Euclidean inner product space (“dot product”) where ||u|| = \sqrt{\left\langle u, u \right\rangle} (we think of this as the length of the vector u).

Dividing (2) by ||u||||v|| and using symmetry + linearity of the inner product we get |\left\langle \frac{u}{||u||}, \frac{v}{||v||} \right\rangle| \leq 1

This is saying that the length of the projection of the unit vector \frac{v}{||v||} along the unit vector \frac{u}{||u||} is at most 1, which is a rather intuitively obvious fact.
Notice also that we have equality if and only if the unit vectors coincide.

Lets prove some basic inequalities that follow immediately from the C-S inequality:

Problem 1 (“The 1 trick”):

Prove that \forall a_{1},...,a_{n} \in \mathbb{R}

(\sum_{i=1}^{n} a_{i})^{2} \leq n\sum_{i=1}^{n} a_{i}^{2}

Solution:
Pick sequences \mathbf{a} = (a_{1},...,a_{n}) and \mathbf{b} = (1,...,1).
Then by Cauchy Schwarz
\sum_{i=1}^{n} a_{i} \leq \sqrt{\sum_{i=1}^{n} 1^{2}}\sqrt{\sum_{i=1}^{n} a_{i}^{2}} .

The inequality follows.

 

Problem 2 (“The splitting trick”):

Prove that \forall a_{1},...,a_{n} \in \mathbb{R}\; and \;p,q \in \mathbb{R}\;s.t\; p+q=1 we have

(\sum_{i=1}^{n} a_{i})^{2} \leq (\sum_{i=1}^{n} a_{i}^{2p})(\sum_{i=1}^{n} a_{i}^{2q})

Solution:

Pick sequences \mathbf{a} = (a_{1}^p,...,a_{n}^p) and \mathbf{b} = (a_{1}^q,...,a_{n}^q).
Then by Cauchy Schwarz
\sum_{i=1}^{n} a_{i} = \sum_{i=1}^{n} a_{i}^{p}a_{i}^{q} \leq \sqrt{\sum_{i=1}^{n} (a_{i}^{p})^{2}}\sqrt{\sum_{i=1}^{n} (a_{i}^{q})^{2}} .

The inequality follows (notice that Problem 1 is a special case of this result).

 

Problem 3 (Why not more than 2?):

Prove that \forall a_{i,j} \in \mathbb{R}\; where \;i,j \in \{1,...,n\},n\geq2\; we have

(\sum_{j=1}^{n} \prod_{i=1}^n a_{i,j})^{2} \leq \prod_{i=1}^n(\sum_{j=1}^{n} a_{i,j}^{2})

Solution:

This may look like a daunting inequality to prove but it is really just an exercise in managing indices.

By multiplying out the brackets and removing a whole lot of positive terms we can deduce the very weak inequality

\prod_{i=1}^{m}(\sum_{j=1}^{n} a_{i,j}^{2}) = \sum_{j_{1}=1}^{n}...\sum_{j_{n}=1}^{n} \prod_{i=1}^{m} a_{i,j_{i}}^{2} \geq \sum_{j=1}^{n}\prod_{i=1}^{m} a_{i,j}^{2} \;\;\;\forall m\leq n \;\;\; (*)

Now by Cauchy Schwarz and (*) we have \sum_{j=1}^{n} \prod_{i=1}^n a_{i,j} = \sum_{j=1}^{n} (\prod_{i=1}^{n-1} a_{i,j})a_{n,j} \leq^{C-S} \sqrt{\sum_{j=1}^n (\prod_{i=1}^{n-1} a_{i,j} )^2} \sqrt{\sum_{j=1}^n a_{n,j}^2} \leq^{(*)} \sqrt{\prod_{i=1}^{n-1} \sum_{j=1}^{n} a_{i,j}^2} \sqrt{\sum_{j=1}^n a_{n,j}^2} = \sqrt{\prod_{i=1}^{n} \sum_{j=1}^{n} a_{i,j}^2}

The inequality follows (note that this upper bound is very weak and next to useless for large n).

 
Cauchy-Schwarz is just the tip of the inequality iceberg.
In general, aesthetical inequalities can arise from very convoluted configurations requiring some serious ingenuity and are therefore quite popular with mathematics competitions.
Techniques range from tricky substitutions to combined usage of several standard inequalities (such as Cauchy-Schwarz).
To give you a taste of what such problems may look like I can offer a problem from IMO 2005, as well as an inequality I just dreamt up myself to illustrate what kind of horrors you can put together on your own.

Problem 4 (IMO 2005 Q3):

Let x,y,x > 0 s.t xyz \geq 1.

Prove that \frac{x^5-x^2}{x^5+y^2+z^2} + \frac{y^5-y^2}{y^5+x^2+z^2} + \frac{z^5-z^2}{z^5+x^2+y^2} \geq 0

Solution:

Looking at this inequality it may seem difficult to find a point of entry.
The fact that the nominator can be negative depending on the choice of x,y,z is clearly a disturbing fact since it is much easier to bound strictly non-negative (or non-positive) expressions.
Moreover homogeneous expressions(i.e where sums of powers of the terms are equal) are often easier to deal with given most classical inequalities are in this form.
The nominators are currently not in homogeneous form so lets try to do something about that.
If we make the inspired move of negating the inequality and adding

\frac{x^5+y^2+z^2}{x^5+y^2+z^2} + \frac{y^5+x^2+z^2}{y^5+x^2+z^2} + \frac{z^5+x^2+y^2}{z^5+x^2+y^2} = 3 to both sides we get the equivalent inequality

\frac{x^2+y^2+z^2}{x^5+y^2+z^2} + \frac{x^2+y^2+z^2}{y^5+x^2+z^2} + \frac{x^2+y^2+z^2}{z^5+x^2+y^2} \leq 3 (*) [remember negation reverses inequalities]

Let’s investigate what Cauchy-Schwarz can do to give us a bound on each of the terms on the left hand side.
We clearly want nominator and denominator to appear on opposite sides of the inequality so we can divide them.
To apply Cauchy-Schwarz it is moreover desirable to have two vectors of size 3 whose dot product is close to being a sum of squares of x,y,z.
We also want one vector whose entries necessarily square to (x^5,y^2,z^2).
The latter requirement gives us one vector as (\sqrt{x^5},y,z).
From the problem statement we have the additional constraint of xyz \geq 1.
Another inspired observation (or rather tedious trial and error perhaps) leads us to believe that using (\sqrt{yz},y,z) might work, partly because one notices that \sqrt{x^5}\sqrt{yz} = \sqrt{x^4}\sqrt{xyz} \geq \sqrt{x^4} = x^2.Indeed by Cauchy-Schwarz we get

(x^5+y^2+z^2)(yz+y^2+z^2) \geq (\sqrt{x^5yz}+y^2+z^2)^2 \geq (x^2+y^2+z^2)^2.

or put another way \frac{yz+y^2+z^2}{x^2+y^2+z^2} \geq \frac{x^2+y^2+z^2}{x^5+y^2+z^2}.

Moreover since (y-z)^2 \geq 0 we have that y^2+z^2 \geq 2yz so that our inequality becomes

\frac{\frac{y^2+z^2}{2}+y^2+z^2}{x^2+y^2+z^2} \geq \frac{x^2+y^2+z^2}{x^5+y^2+z^2} (1).

Similarly we get

\frac{\frac{x^2+y^2}{2}+x^2+y^2}{x^2+y^2+z^2} \geq \frac{x^2+y^2+z^2}{z^5+x^2+y^2} (2) and

\frac{\frac{x^2+z^2}{2}+x^2+z^2}{x^2+y^2+z^2} \geq \frac{x^2+y^2+z^2}{y^5+x^2+z^2} (3)

Adding together (1),(2) and (3) yields (*).

Hence the inequality is proved.

 

Problem 5 (Amini(ngless) inequality):
Let a,b,c,d > 0.

Prove that \frac{d+1}{a+bd} + \frac{d+1}{b+cd} + \frac{d+1}{c+ad} \geq \frac{9}{a+b+c}.

Solution:

Ok, so how do we untangle this mess?

It is probably not immediately obvious that this is a Cauchy-Schwarz inequality.

I have made it quite nasty through a non-linear substitution, so instead of trying to make sense of this let’s start constructing it backwards knowing where we are going.

A common template for quite a few well-known C-S inequalities is (\sum_{i=1}^n a_i)(\sum_{i=1}^n \frac{1}{a_i}) \geq n^2,\; a_{i}>0 .

This inequality follows directly from Cauchy-Schwarz using a suitable sequence.

I will leave it as an easy exercise (Exercise 1).

In our case we will want to use it in the form (x+y+z)(\frac{1}{x} + \frac{1}{y} + \frac{1}{x}) \geq 3^2.

Now make the substitution:

(x,y,z) \longmapsto (a+bd,b+cd,c+ad).

(You can verify this substitution is harmless as long as a,b,c,d > 0).

Inserting we get (a+bd + b+cd + c+ad)(\frac{1}{a+bd}+\frac{1}{b+cd}+\frac{1}{c+ad}) \geq 9.

or (d+1)(a+b+d)(\frac{1}{a+bd}+\frac{1}{b+cd}+\frac{1}{c+ad}) \geq 9.

The inequality follows.

 
Inequalities are often used to manage more complicated quantities through simpler ones, e.g to analyse behaviour “in the limit” or to find good hard estimates of a quantity.
Clearly the sharper an inequality is, the closer it is to being an equality (which is the ultimate inequality).
Inequalities are often best understood by analyzing the equality cases.
Cauchy-Schwarz is an indispensable tool but there are also many other important standard inequalities out there (maybe appearing in future posts?). Among these are HM-AM-GM-QM, Rearrangement, Hölder, Jensen, Chebyshev, Schur and Muirhead inequalities.

Now that you are a Cauchy-Schwarz pro, why not try below exercises?

Exercise 1 (Reciprocal Sum Inequality – Easy):
Prove that \forall a_{1},...a_{n} > 0

(\sum_{i=1}^n a_i)(\sum_{i=1}^n \frac{1}{a_i}) \geq n^2.

 

Exercise 2 (Symmetric inequality – Easy):
Prove that \forall x,y,z > 0

\sqrt{\frac{x+y}{x+y+z}} + \sqrt{\frac{x+z}{x+y+z}} + \sqrt{\frac{y+z}{x+y+z}} \leq \sqrt{6}.

 

Exercise 3 (Iran 1998 IMO team selection – Hard):
Prove that \forall x,y,z > 1\;\;s.t\;\;\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=2

\sqrt{x+y+z} \geq \sqrt{x-1} + \sqrt{y-1} + \sqrt{z-1}.

Advertisements
This entry was posted in Algebra, Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s