#cauchy-schwarz

[wiskwa]

Over een fundamentele ongelijkheid in de wiskunde

In het kader van een serie artikelen over dingen die met kwadraten te maken hebben verscheen ook een stuk over de ; met toepassingen, onder meer in de krystallografie.

[zornspotato]

A Tale of Lagrange and Cauchy-Schwarz, Part 3

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\) This post is marked as a Triple Star. Prerequisites: You won’t actually need Part 1 and Part 2 to read this, but they’ll help with the motivation and the continuity. You should also know what the Cauchy-Schwarz inequality is or you’ll have no idea what I’m doing.

Okay guys. A Tale of Lagrange and Cauchy-Schwarz Part 3 is here. Finally, after this long wait, we come to the thrilling conclusion of the epic tale: we’re going to prove the Cauchy-Schwarz inequality... again. This is where the mashed potatoes come in, First, you have to just kidding. This is not about potatoes. I’m done with the potato analogy for now.

We’re going to need the AM/GM inequality in order to prove Cauchy-Schwarz this way. Fortunately for us, this is exactly what we proved in Part 2. However, in Part 2 we proved the AM/GM inequality for \(n\) variables. We only actually need it for two variables. I’m actually going to prove it for two variables right now, and it’s really easy. Take everyone’s favorite inequality: \(X^2 \ge 0\), with equality if and only if \(X = 0\). Substituting \(a - b\) in for \(X\) gives us \((a - b)^2 \ge 0\) with equality iff \(a - b = 0\) (which is just when \(a = b\)). Expanding that creates \(a^2 + b^2 -2ab \ge 0\) with equality iff \(a = b\), which is just \(a^2 + b^2 \ge 2ab\) with equality iff \(a = b\).

I just proved the version of AM/GM that we’re going to need for this post. This makes Part 2 entirely pointless for this one. At least it was fun though.

Remember that this is called the AM/GM inequality as a shortcut for the Arithmetic Mean/Geometric Mean inequality, because the following two inequalities are interchangeable \[ a^2 + b^2 \ge 2ab \iff \frac{x + y}{2} \ge \sqrt{xy} \] if we substitute \(a \mapsto \sqrt{x}\) and \(b \mapsto \sqrt{y}\) (equality still is iff  \( x = y \) or \(a = b\)). The right hand inequality above states that the arithmetic mean of two numbers is greater than or equal to their geometric mean, which are the two sides of the inequality respectively. The left hand inequality is typically more useful so we’ll use that one instead. It is, in essence, the AM/GM inequality in its most pure form.

Now, let’s actually get to Cauchy-Schwarz. It is enough to show that \(x\) and \( w\) are unit vectors, and prove that \(|\langle x, w \rangle | \le 1\) with equality if and only if \(x = \pm w\), because the inner product is linear in both coordinates. The absolute value of the inner product \(|\langle x, w\rangle|\) is \begin{align*} |\langle x, w\rangle| &= \left|\sum_{i=1}^n x_iw_i\right| \cr &= |x_1w_1 + x_2w_2 + \dots + x_nw_n| \cr &\le |x_1w_1| + |x_2w_2| + \dots + |x_nw_n| \end{align*} where equality only holds in that last one if each \(x_iw_i\) has the same sign as all the others. Continuing, \begin{align*} &= |x_1w_1| + |x_2w_2| + \dots + |x_nw_n| \cr &= |x_1||w_1| + |x_2||w_2| + \dots + |x_n||w_n| \cr &\le \frac{|x_1|^2 + |w_1|^2}{2} + \frac{|x_2|^2 + |w_2|^2}{2} + \dots + \frac{|x_n|^2 + |w_n|^2}{2} \end{align*} with equality if and only if each \(|x_i|\) equals its \(|w_i|\). We just used the two-variable AM/GM inequality there. Regrouping,

\begin{align*} &=\frac{|x_1|^2 + |w_1|^2}{2} + \frac{|x_2|^2 + |w_2|^2}{2} + \dots + \frac{|x_n|^2 + |w_n|^2}{2} \cr &= \frac{1}{2}\left(|x_1|^2 + |x_2|^2 + \dots + |x_n|^2\right) + \frac{1}{2}\left(|w_1|^2 + |w_2|^2 + \dots + |w_n|^2\right) \cr &= \frac{1}{2}|x| + \frac{1}{2}|w| \cr &= \frac{1}{2} + \frac{1}{2} \cr &= 1 \end{align*}

So we have just proven that \(|\langle x, w\rangle| \le 1\) with equality if and only if each \(|x_i| = |w_i|\) and all the \(x_iw_i\)s have the same sign. This means that equality only holds if \(x = \pm w\). So we’re done. QED Potato. \(\Box\)

Hey, that was actually pretty easy. Oh well, that means we don’t necessarily have as much AM/GM as I would have liked, because AM/GM is the best inequality ever, yo. We can fix this. Tune in next time and we’ll do more AM/GM than you ever cared for. It will be delicious. Yes, delicious. And tell your friends, because it’s going to be \(({*})\) Single Star. Until next time, Zorn’s Potato Out.

[zornspotato]

A Tale of Lagrange and Cauchy-Schwarz, Part 2

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\) This post is marked as a Triple Star. Prerequisites: Part 1. Before we begin, I want to mention that today my Honors Analysis professor drew a differentiable manifold on the board, kinda like a lump. He described it as a “lumpy potato.” Several of my classmates near me gave me this fake-contemptuous look because they read this blog. This made me feel so honored. I just thought I’d share that.

Anyway, recall from Part 1 the Potato Analogy that I had written, copied here for convenience:

“Suppose you have a potato and you want to make mashed potatoes. First, you clean and peel the potatoes. Next, you boil the potatoes to make them nice and soft. Then you mash them. OR, you could clean and peel the potatoes, then cut them into slices, boil them to make them soft, and mash them. The difference between these is that one has an intermediary step that doesn’t change the final result but does change the journey on how to get there. Despite it being more work to learn how to do it the second way, you end up learning more about the process of cooking potatoes.”

Now, we will learn why this is relevant. You see, in Part 1, I proved that Lagrange Multipliers implies Cauchy-Schwarz. Now that it’s Part 2, I will also prove that Lagrange Multipliers implies Cauchy-Schwarz, but I’m going to do it slightly differently. I’m going to prove that Lagrange Multipliers implies the AM/GM Inequality, which is not the most important inequality ever but it is my favorite. Remember that the AM/GM inequality (which stands for Arithmetic Mean/Geometric Mean) states that the arithmetic mean of \(n\) nonnegative real numbers is always greater than or equal to their geometric mean, with equality if and only if all \(n\) of them are equal to each other. The arithmetic mean of \( n \) real numbers is their sum divided by \(n\), and the geometric mean is the \( n \)th root of their product.

Once we establish the AM/GM inequality, we will then use the AM/GM inequality to prove the legendary Cauchy-Schwarz inequality. This means that we’re actually going to break the second proof of this into two separate posts, so get ready for three-halves the proof and three-halves the fun that you thought you were going to get.

Now, it must seem relevant as to why I made that potato analogy: We’re going to take an intermediary step on the way from the initial setup to the final conditions, and even though it will take longer, we’re going to learn more in the process. Just kidding, this proof is longer because I think that’s more fun. But let’s not dwell on why we’re doing this, just that we’re going to do it and nobody is going to stop me!

Okay. So the first thing I’m going to do is simplify the AM/GM inequality slightly. The AM/GM inequality, as stated, reads like this: \[ \left(y_1y_2\dots y_n\right)^\frac{1}{n} \le \frac{y_1 + y_2 + \dots + y_n}{n} \] with equality if and only if all \(y_i\)s are equal. If we let \(x_i = y_i^{1/n}\), then this inequality is equivalent to the inequality \[ x_1x_2\dots x_n \le \frac{x_1^n + x_2^n + \dots + x_n^n}{n} \] with equality iff all \(x_i\)s are equal. We’re going to add the additional stipulation that \(n \ge 2\) because in the case where \(n = 1\) this is trivially true.

It’s convenient to note that \(x_1^n + \dots + x_n^n\) is exactly the value \( \|x\|_n^n \), where \(\|x\|_n\) is the \(L^n\)-norm of \(x\), and \( x\) is the vector whose entries are \(x_i\)s. (The \(L^n\)-norm is defined as \( (|x_1|^n + \dots + |x_n|^n)^{1/n}\), and satisfies all the nice properties of norms.) This is convenient because now, it is enough to show that \[ x_1\dots x_n \le \frac{1}{n} \] as long as \(\|x\|_n = 1\). We can do this because as long as \(x\) is nonzero, we can scale \(x\) by its \(L^n\)-norm without affecting the inequality, because both sides scale by a factor of \(\|x\|_n^n\). In the case where \(x\) is zero, then the inequality is trivially true. We’re then going to replace this constraint equation with \(\|x\|_n^n = 1\) rather than \(\|x\|_n = 1\), because the former is \( C^\infty \) (this is the same thing we did in Part 1), and we’re going to once more change this, to \(\|x_n\|_n^n/n - 1/n = 0\).

Now, we can define the compact differentiable manifold on which we’re maximizing our function, and which function we’re maximizing. We’re going to maximize the function \begin{align*} h : \mathbb{R}^n &\to \mathbb{R}\cr x &\mapsto x_1x_2\dots x_n \end{align*} subject to the constraints \(f(x) = 0\) and \(x_i \ge 0\), where \begin{align*} f : \mathbb{R}^n &\to \mathbb{R}\cr x &\mapsto \frac{\|x\|_n^n}{n} - \frac{1}{n} \end{align*} This gives us a compact, differentiable manifold whose boundary is the set of \( x\) such that \(x_i\) is zero for some \(i\). Now, we’re going to use Lagrange Multipliers to maximize this function on our differential set, by finding critical points and checking critical points and endpoints. (We also have that \(h\) and \( f\) are \(C^\infty\), so that’s covered.)

Taking the gradient, we get that \[ \nabla h = \left(\begin{array}{c} \phantom{x_1}x_2x_3 \dots x_{n-2}x_{n-1}x_n \cr x_1\phantom{x_2}x_3 \dots x_{n-2}x_{n-1}x_n \cr x_1x_2\phantom{x_3}\dots x_{n-2}x_{n-1}x_n \cr \vdots \cr x_1x_2x_3\dots x_{n-2}\phantom{x_{n-1}}x_n \cr x_1x_2x_3\dots x_{n-2}x_{n-1}\phantom{x_n} \end{array}\right) \] and we get that \[ \nabla f = \left(\begin{array}{c} x_1^{n-1} \cr x_2^{n-1} \cr \vdots \cr x_n^{n-1} \end{array}\right) \] Now, when we get our lagrange multipliers, setting \(\nabla h = \lambda \nabla f\), we get the equations \begin{align*} x_2x_3\dots x_n &= \lambda x_1^{n-1} \cr x_1x_3\dots x_n &= \lambda x_2^{n-1} \cr &\vdots \cr x_1\dots x_{n-1} &= \lambda x_n^{n-1} \end{align*} plus our constraints.

If we multiply all \(n\) of these equations together, we get that \[ x_1^{n-1}x_2^{n-1}\dots x_n^{n-1} = \lambda^n x_1^{n-1}x_2^{n-1 }\dots x_n^{n-1} \] so \( \lambda^n = 1\), so \(\lambda\) is a root of unity. But looking at all of our original equations, we have a nonnegative real number is \(\lambda\) times another nonnegative real number, for all of the equations, which means that \( \lambda \) must be equal to \(1\), and not \(-1\) or a complex root. (Remember that we can’t have \(x = 0\) because \(\|x\|_n = 1\)).

Now that we’ve decided that \(\lambda = 1\) is a necessary condition for a solution, we can look back to our equations: \begin{align*} x_2x_3\dots x_n &= x_1^{n-1} \cr x_1x_3\dots x_n &= x_2^{n-1} \cr &\vdots \cr x_1\dots x_{n-1} &= x_n^{n-1} \end{align*} I claim that if all \(x_i\)s equal each other then this is a solution to these equations. If each \(x_i\) equals each other one, then all of the equations become \(x_i^{n-1} = x_i^{n-1}\), which is satisfied, and the constraint is satisfied as long as they’re all equal to \((1/n)^{(1/n)}\). (This is because if we take each of those to the \(n\)th power we get \(1/n\), which becomes \(1\) when we add all \( n\) of them together.) So it’s not hard to see that this is a sufficient condition for a solution.

I also claim that \(x_i\)s equalling each other is a necessary condition. Because the set of \(x_i\)s is a finite set, there must be some \(x_i\) that is a smallest member, but not necessarily unique. That is \(x_i \le x_j\) for any \(1 \le j \le n\). If we look at the particular equation for that one \(x_i\), we get \[ x_1\dots x_{i-1}x_{i+1}\dots x_n = x_i^n \] If any of the \(x_j\)s on the left-hand side are strictly greater than \(x_i\), then the left-hand side would be strictly greater than the right-hand side. This would not satsify the equation, so the only way for this particular equation to hold is for each \(x_j\) to be equal to \(x_i\). So the only way this can be solved is if each \( x_j\) equals each \(x_i\) for any \(i\) or \(j\).

Now, we have shown that there is only one critical point, i.e. each \(x_i\) equals each other and equals \((1/n)^{(1/n)}\), so it suffices to check the critical point and the boundary points. The boundary of the compact set on which we’re maximizing is the set of all points where at least one \(x_i\) equals zero. If at least one \(x_i\) equals zero, then \(h(x) = 0\) because \(h\) is the product of the entries of \(x\). If \(x\) is the critical point, then \(h(x) = 1/n\). The number \(1/n\) is positive so the maximum occurs at the critical point and the minimum occurs along the boundary.

This means that because the maximum is achieved at the critical point, we have that the function \(h\) must be less than or equal to the maximum value, with equality if and only if we’re at the critical point. That is, \[ h(x) \le \frac{1}{n} \] if \(\|x\|_n = 1\), and with equality if and only if \(x_1 = \dots = x_n\). If we then work backward and remove our stipulation that \(\|x\|_n = 1\), we get the inequality: \[ x_1\dots x_n \le \frac{x_1^n + \dots + x_n^n}{n} \] with equality if and only if \(x_1 = x_2 = \dots = x_n\), which is equivalent to the inequality \[ \left(x_1\dots x_n\right)^\frac{1}{n} \le \frac{x_1 + \dots + x_n}{n} \] with equality if and only if \(x_1 = x_2 = \dots = x_n\). And that is exactly the AM/GM inequality. So we’re done proving the AM/GM inequality! QED Potato. \( \Box\)

We’ve done the bulk of the work at this point, but I do want to mention that we’re not quite done. Now, we have to use the AM/GM inequality to prove Cauchy-Schwartz. “How are we going to do that?” I hear you cry. Well fear not, because this is a proof that will be covered in Part 3 of A Tale of Lagrange and Cauchy-Schwartz. Sit back, relax, wait for me to finish this week’s homework because that’s more important, and THEN you shall receive. Until next time, Zorn’s Potato Out.

[zornspotato]

A Tale of Lagrange and Cauchy-Schwarz, Part 1

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\)This post is marked as a Triple Star. Prerequisites: You should know how to do Lagrange Multipliers or you will have no idea what I’m doing. It might also help to be somewhat familiar with the Cauchy-Schwarz inequality because otherwise you might not understand the motivation for this proof. (The CS inequality is sometimes states as the most important inequality in all of math. Proofs of it are numerous and different.)

It appears I haven’t made a post in quite some time. I owe you guys a proof. Now, suppose you have a potato and you want to make mashed potatoes. First, you clean and peel the potatoes. Next, you boil the potatoes to make them nice and soft. Then you mash them. OR, you could clean and peel the potatoes, then cut them into slices, boil them to make them soft, and mash them. The difference between these is that one has an intermediary step that doesn’t change the final result but does change the journey on how to get there. Despite it being more work to learn how to do it the second way, you end up learning more about the process of cooking potatoes. For more information on why this is a relevant anecdote, see part two when it comes out. Unless you are reading this in the future, in which case just go read part two.

So now, we’re going to discuss Lagrange Multipliers. Actually, we’re going to discuss the Cauchy-Schwarz inequality in \(\mathbb{R}^n\). BUT WHICH ONE? What if I told you... that we were going to discuss both AT THE SAME TIME?!?! You’d probably not panic and you’d probably say, “I figured that’s what you were going to do.” This will make me sad that I was so predictable, but that’s okay. We’re going to prove the Cauchy-Schwarz inequality in \(\mathbb{R}^n\) using Lagrange Multipliers.

So I want to do a disclaimer. Most of the proofs on this blog I came up with myself. This one I did as well, and when I found out that this is a well-known fact I got quite sad that I wasn’t original, but at least happy that it meant I was probably right.

Recall that the Cauchy-Schwarz inequality states that if \(w, x \in \mathbb{R}^n\), then \(|\langle w, x\rangle | \le \|w\|\|x\| \) with equality if and only if \(w\) and \(x\) are linearly dependent. What I’m going to do is fix \(w \in \mathbb{R}^n\), and I’m going to prove that for \(x \in \mathbb{R}^n\) where \(\|x\| = 1\), then we have that \( |\langle w, x\rangle | \le \|w\| \) with equality if and only if \(w = \mu x\) for some \(\mu \in \mathbb{R}\). If we can do this, then it works for any non-unit vector too, because we can divide by the norm of it (unless it’s zero, in which case we’ve already won).

The first thing I’m going to do is note that \(\|x\| = 1\) is the same statement as \(\|x\|^2 = 1\) (the norm is always nonegative), so I will use that one instead. We’re going to try to maximize \(h : \mathbb{R}^n \to \mathbb{R}\) where \(h(x) = \langle w, x\rangle\), subject to the constraint equation \(f : \mathbb{R}^n \to \mathbb{R}\) where \(f(x) = \|x\|^2 - 1 = 0\). Now, we need to check to make sure we can actually use lagrange multipliers. First, is our constraint set compact? Well our constraint set is \(\|x\|^2 - 1 = 0\), which is the boundary of the unit ball, which is compact. Second, are \(h\) and \(f\) sufficiently continuous/differentiable? Well, they’re both \(C^\infty\), which is good enough. (This is one of the advantages of using \(\|x\|^2\) over \(\|x\|\): the first one is \(C^\infty\).)

So let’s calculate our derivatives. \(h(x) = \langle w, x\rangle\), which can be rewritten as \(w_1 x_1 + w_2 x_2 + \dots + w_n x_n\). Thus, when we take the gradiant, we get \(\nabla h = (w_1, w_2, \dots, w_n) = w\). \(f(x) = \|x\|^2 - 1\), which can be rewritten as \(x_1^2 + x_2^2 + \dots + x_n^2 - 1\). When we take the gradiant, we get \(\nabla f = (2 x_1, 2 x_2, \dots, 2 x_n) = 2x\). So now, we collect our equations, which are: \begin{align*} \nabla h &= \lambda \nabla f \cr 1 &= \|x\|^2 \end{align*} Substituting, we get that the critical points occur at solutions to \begin{align*} w &= 2\lambda x \cr 1 &= \|x\|^2 \end{align*} But wait! Look at that first equation! That one says critical points only occur when \(w\) is a constant multiple of \(x\)! This means that the function \(h\) is maximized and minimized when \(w = \pm \mu x\) for some real number \(\mu \ge 0\). We know this because there’s only two unit vectors that are a constant multiple of any arbitrary vector, and those are negatives of each other. (Here, if \(w\) is zero, then we only get one solution and that’s \(\mu =0\)).

Now, we have to check our critical points. Checking \(w = \mu x\), we get that \begin{align*} h(x) &= \langle w, x\rangle \cr &= \langle \mu x, x \rangle \cr &= \mu \|x\|^2 \cr &= \mu \|x\| \cr &= \|\mu x\| \cr &= \|w\| \cr \end{align*} Checking \(w = -\mu x\), we get \begin{align*} h(x) &= \langle w, x\rangle \cr &= \langle -\mu x, x \rangle \cr &= -\mu \|x\|^2 \cr &= -\mu \|x\| \cr &= -\|\mu x\| \cr &= -\|w\| \cr \end{align*} Clearly, \(\|w\|\) is the maximum and \(-\|w\|\) is the minimum because \(\|w\| \ge 0\) and \(-\|w\| \le 0\). But wait! If \(h\) is maximized at \(\|w\|\) on our compact set, then we have that \(h(x) \le \|w\|\) for \(\|x\|^2 = 1\), with equality iff we’re at the maximum. Similarly, \(h(x) \ge -\|w\|\), with equality iff we’re at the minimum. But we can combine these two inequalities together to give us \(|h(x)| \le \|w\|\), with equality iff we had equality before, so iff we were at either the max or the min. But \(|h(x)| \le \|w\|\) is exactly the Cauchy-Schwartz inequality when we expand it out: \(h(x) = \langle w, x\rangle\), so this means that we have \(|\langle w, x\rangle| \le \|w\|\) for \(\|x\| = 1\), with equality if and only if \(w = \alpha x\), for some \(\alpha \in \mathbb{R}\). So we’re done! QED Potato \(\Box\).

I just gave a direct proof of the Cauchy-Schwartz inequality in \(\mathbb{R}^n\) with Lagrange Multipliers. Direct proofs aren’t quite as fun as indirect proofs, so tune in next time for Part 2 when we prove the same thing (that is, Lagrange Multipliers \(\implies\) Cauchy-Schwarz), but this time we prove an intermediary theorem. But which one? That’s going to be a surprise (unless you can guess, in which case it won’t be a surprise). Anyway, until next time, Zorn’s Potato out.

[soundtracks-for-the-blind]

[mintwater]

Proof of the Cauchy-Schwarz Inequality

Cauchy-Schwarz Inequality

$$ {\lvert \langle f, g \rangle \rvert}^2 \leq \langle f, f \rangle \langle g, g \rangle $$

For two vectors \( f \) and \( g \) in an inner product space, pick an arbitrary real scalar \( \lambda \) and write:

$$ \lvert \langle \lambda f + g, \lambda f + g \rangle \rvert \geq 0 $$

which is true because it's a length squared, so

$$ \lvert \langle \lambda f + g, \lambda f + g \rangle \rvert = {\lambda}^2 \langle f, f \rangle + 2\lambda\lvert\langle f, g \rangle\rvert + \langle g, g \rangle \geq 0 $$

The expression on the left is quadratic in \( \lambda \), and since it's always greater than or equal to zero, it has zero real roots (i.e. entirely above the x axis) or one real root (i.e. just touching the x axis).

It can't have two real roots, because that would require that the expression be negative for some \( \lambda \) (i.e. go underneath the x axis), and that can't be the case since it's a length squared.

Altogether, this means that the quadratic's discriminant is less than or equal to zero:

$$ b^2 - 4ac \leq 0 $$

$$ 4 {\lambda}^2 {\lvert\langle f, g \rangle\rvert}^2 - 4 {\lambda}^2 \langle f, f \rangle \langle g, g \rangle \leq 0 $$

$$ 4 {\lambda}^2 {\lvert\langle f, g \rangle\rvert}^2 \leq 4 {\lambda}^2 \langle f, f \rangle \langle g, g \rangle $$

$$  {\lvert\langle f, g \rangle\rvert}^2 \leq \langle f, f \rangle \langle g, g \rangle $$

Equality occurs when \( f \) and \( g \) are linearly dependent. This means \( f = \lambda g \) for some scalar \( \lambda \), and we can show this directly by writing:

$$ {\lvert \langle f, g \rangle \rvert}^2 ={\lvert\langle \lambda g, g \rangle \rvert}^2 = {\lvert \lambda \rvert}^2 {\langle g, g \rangle}^2 = {\lvert \lambda \rvert}^2 \langle g, g \rangle \langle g, g \rangle = \langle f, f \rangle \langle g, g \rangle  $$

$$ {\lvert \langle f, g \rangle \rvert}^2 = \langle f, f \rangle \langle g, g \rangle $$

See some similar/alternate proofs and applications of the Cauchy-Schwarz Inequality here: http://cnx.org/content/m10757/latest/