Difference between revisions of "Cauchy-Schwarz Inequality"

m
(14 intermediate revisions by 2 users not shown)
Line 1: Line 1:
The '''Cauchy-Schwarz Inequality''' (which is known by other names, including '''Cauchy's Inequality''', '''Schwarz's Inequality''', and the '''Cauchy-Bunyakovsky-Schwarz Inequality''') is a well-known [[inequality]] with many elegant applications. It has an elementary form, a complex form, and a general form.  
+
In [[algebra]], the '''Cauchy-Schwarz Inequality''', also known as the '''Cauchy–Bunyakovsky–Schwarz Inequality''' or informally as '''Cauchy-Schwarz''', is an [[inequality]] with many ubiquitous formulations in abstract algebra, calculus, and contest mathematics. In high-school competitions, its applications are limited to elementary and linear algebra.
  
[https://en.wikipedia.org/wiki/Augustin-Louis_Cauchy|Augustin Louis Cauchy] wrote the first paper about the elementary form in 1821. The general form was discovered by [https://en.wikipedia.org/wiki/Viktor_Bunyakovsky|Viktor Bunyakovsky] in 1849 and independently by [https://en.wikipedia.org/wiki/Hermann_Amandus_Schwarz|Hermann Schwarz] in 1888.
+
Its elementary algebraic formulation is often referred to as '''Cauchy's Inequality''' and states that for any list of reals <math>a_1, a_2, \ldots, a_n</math> and <math>b_1, b_2, \ldots, b_n</math>, <cmath>(a_1^2 + a_2^2 + \cdots + a_n^2)(b_1^2 + b_2^2 + \cdots + b_n^2) \geq (a_1b_1 + a_2b_2 + \cdots + a_nb_n)^2,</cmath> with equality if and only if there exists a constant <math>t</math> such that <math>a_i = t b_i</math> for all <math>1 \leq i \leq n</math>, or if one list consists of only zeroes. Along with the [[AM-GM Inequality]], Cauchy-Schwarz forms the foundation for inequality problems in intermediate and olympiad competitions. It is particularly crucial in proof-based contests.
  
== Elementary Form ==
+
Its vector formulation states that for any vectors <math>\overrightarrow{v}</math> and <math>\overrightarrow{w}</math> in <math>\mathbb{R}^n</math>, where <math>\overrightarrow{v} \cdot \overrightarrow{w}</math> is the [[dot product]] of <math>\overrightarrow{v}</math> and <math>\overrightarrow{w}</math> and <math>\| \overrightarrow{v} \|</math> is the [[norm]] of <math>\overrightarrow{v}</math>, <cmath>\|\overrightarrow{v}\| \|\overrightarrow{w}\| \geq |\overrightarrow{v} \cdot \overrightarrow{w}|</cmath> with equality if and only if there exists a scalar <math>t</math> such that <math>\overrightarrow{v} = t \overrightarrow{w}</math>, or if one of the vectors is zero. This formulation comes in handy in linear algebra problems at intermediate and olympiad problems.
  
For any real numbers <math> a_1, \ldots, a_n </math> and <math> b_1, \ldots, b_n </math>,
+
The full Cauchy-Schwarz Inequality is written in terms of abstract vector spaces. Under this formulation, the elementary algebraic, linear algebraic, and calculus formulations are different cases of the general inequality.  
<cmath>
 
\left( \sum_{i=1}^{n}a_ib_i \right)^2 \le \left(\sum_{i=1}^{n}a_i^2 \right) \left(\sum_{i=1}^{n}b_i^2 \right)
 
</cmath>
 
with equality when there exists a nonzero constant <math>\mu</math> such that for all <math> 1 \le i \le n </math>, <math>\mu a_i = b_i </math>.
 
  
To easily memorize this formula, we use the simpler, more compact notation:
+
== Proofs ==
<cmath>\left(\sum (ab)^2\right)\leq \left(\sum a^2\right)\left(\sum b^2\right)</cmath>
+
Here is a list of proofs of Cauchy-Schwarz.
  
=== Discussion ===
+
Consider the vectors <math> \mathbf{a} = \langle a_1, \ldots a_n \rangle </math> and <math> {} \mathbf{b} = \langle b_1, \ldots b_n \rangle </math>.  If <math>\theta </math> is the [[angle]] formed by <math> \mathbf{a} </math> and <math> \mathbf{b} </math>, then the left-hand side of the inequality is equal to the square of the [[dot product]] of <math>\mathbf{a} </math> and <math> \mathbf{b} </math>, or <math>(\mathbf{a} \cdot \mathbf{b})^2 = a^2 b^2 (\cos\theta) ^2</math>  .The right hand side of the inequality is equal to <math> \left( ||\mathbf{a}|| * ||\mathbf{b}|| \right)^2  = a^2b^2</math>.  The inequality then follows from <math> |\cos\theta | \le 1 </math>, with equality when one of <math> \mathbf{a,b} </math> is a multiple of the other, as desired.
  
Consider the vectors <math> \mathbf{a} = \langle a_1, \ldots a_n \rangle </math> and <math> {} \mathbf{b} = \langle b_1, \ldots b_n \rangle </math>.  If <math>\theta </math> is the [[angle]] formed by <math> \mathbf{a} </math> and <math> \mathbf{b} </math>, then the left-hand side of the inequality is equal to the square of the [[dot product]] of <math>\mathbf{a} </math> and <math> \mathbf{b} </math>, or <math>(\mathbf{a} \cdot \mathbf{b})^2 = a^2 b^2 (\cos\theta) ^2</math>  .The right hand side of the inequality is equal to <math> \left( ||\mathbf{a}|| * ||\mathbf{b}|| \right)^2  = a^2b^2</math>.  The inequality then follows from <math> |\cos\theta | \le 1 </math>, with equality when one of <math> \mathbf{a,b} </math> is a multiple of the other, as desired.
+
== Lemmas ==
  
 
=== Complex Form ===
 
=== Complex Form ===
 
 
The inequality sometimes appears in the following form.
 
The inequality sometimes appears in the following form.
  
Line 29: Line 24:
 
<cmath>
 
<cmath>
 
\left| \sum_{i=1}^n a_ib_i \right| ^2 \le \left( \sum_{i=1}^n |a_i| \cdot |b_i| \right)^2 \le \left(\sum_{i=1}^n |a_i^2| \right) \left( \sum_{i=1}^n |b_i^2| \right)
 
\left| \sum_{i=1}^n a_ib_i \right| ^2 \le \left( \sum_{i=1}^n |a_i| \cdot |b_i| \right)^2 \le \left(\sum_{i=1}^n |a_i^2| \right) \left( \sum_{i=1}^n |b_i^2| \right)
</cmath>
 
 
== Upper Bound on (Σa)(Σb) ==
 
 
Let <math>a_1, a_2, \ldots, a_n</math> and <math>b_1, b_2, \ldots, b_n</math> be two sequences of positive real numbers with
 
<cmath>
 
0 < m \le \frac{a_i}{b_i} \le M
 
</cmath>
 
for <math>1 \le i \le n</math>. Then
 
<cmath>
 
\left(\sum_{i=1}^{n}a_i^2 \right) \left(\sum_{i=1}^{n}b_i^2 \right) \le \frac{(M+m)^2}{4Mm} \left( \sum_{i=1}^{n}a_ib_i \right)^2,
 
</cmath>
 
with equality if and only if, for some ordering of the pairs <math>(a_i,b_i) \mapsto (a_{\sigma(i)},b_{\sigma(i)})</math>, some <math>0 \le j \le n</math> exists such that <math>a_{\sigma(i)}=mb_{\sigma(i)}</math> for <math>1 \le \sigma(i) \le j</math> and <math>a_{\sigma(i)}=Mb_{\sigma(i)}</math> for <math>j+1 \le \sigma(i) \le n</math>, and
 
<cmath>
 
m\sum_{\sigma(i)=1}^{j}b_{\sigma(i)}^2 = M\sum_{\sigma(i)=j+1}^{n}b_{\sigma(i)}^2.
 
</cmath>
 
If we restrict that <math>m_1 \le a_i \le M_1</math> and <math>m_2 \le b_i \le M_2</math> for all <math>i</math>, then it's clear that for <math>a_i/b_i</math> to be <math>m=m_1/M_2</math> or <math>M=M_1/m_2</math> for all <math>i</math>, then <math>a_i=m_1 \Longleftrightarrow b_i=M_2</math> and <math>a_i=M_1 \Longleftrightarrow b_i=m_2</math>, so
 
<cmath>
 
m\sum_{\sigma(i)=1}^{j}b_{\sigma(i)}^2 = M\sum_{\sigma(i)=j+1}^{n}b_{\sigma(i)}^2
 
</cmath>
 
is equivalent to
 
<cmath>
 
\begin{align*}
 
m(jM_2^2) = M((n-j)m_2^2) &\Longleftrightarrow m_1M_2j = M_1m_2(n-j)\\
 
&\Longleftrightarrow j = \left(\frac{M_1m_2}{M_1m_2+m_1M_2}\right) n.
 
\end{align*}
 
</cmath>
 
(When this is not an integer, the maximum occurs when <math>j</math> is either the ceiling or floor of the right-hand side.) In the special case that <math>a_ib_i = k > 0</math> is constant for all <math>i</math>, we have <math>M_1=1/m_2</math> and <math>m_1=1/M_2</math>, so here <math>j</math> must be <math>n/2</math>.
 
 
=== Proof ===
 
 
Note that for all <math>i</math>, we have
 
<cmath>
 
0 \le \left(\frac{a_i}{b_i}-m\right)\left(M-\frac{a_i}{b_i}\right) = \frac{1}{b_i^2}(a_ib_iM-a_i^2-b_i^2Mm+a_ib_im)
 
</cmath>
 
or
 
<cmath>
 
(M+m)a_ib_i \ge a_i^2+(Mm)b_i^2,
 
</cmath>
 
with equality if and only if <math>a_i=mb_i</math> or <math>a_i=Mb_i</math>. Summing up these inequalities over <math>1 \le i \le n</math>, we obtain from AM-GM that
 
<cmath>
 
\begin{align*}
 
(M+m)\sum_{i=1}^{n}a_ib_i &\ge \sum_{i=1}^{n}a_i^2 + (Mm)\sum_{i=1}^{n}b_i^2\\
 
&\ge 2\sqrt{Mm \left(\sum_{i=1}^{n}a_i^2 \right) \left(\sum_{i=1}^{n}b_i^2 \right)},
 
\end{align*}
 
</cmath>
 
and squaring gives us the desired bound. For equality to occur, we must have <math>a_i=mb_i</math> or <math>a_i=Mb_i</math> for all <math>i</math>. If, without loss of generality, <math>a_i=mb_i</math> for <math>1 \le i \le j</math> and <math>a_i=Mb_i</math> for <math>j+1 \le i \le n</math> for some <math>0 \le j \le n</math>, then for the AM-GM to reach equality we must have (assume <math>M>m</math> since <math>M=m</math> is trivial)
 
<cmath>
 
\begin{align*}
 
\sum_{i=1}^{n}a_i^2 &= Mm\sum_{i=1}^{n}b_i^2\\
 
m^2\sum_{i=1}^{j}b_i^2 + M^2\sum_{i=j+1}^{n}b_i^2 &= Mm\sum_{i=1}^{j}b_i^2 + Mm\sum_{i=j+1}^{n}b_i^2\\
 
(m-M)m\sum_{i=1}^{j}b_i^2 &= (m-M)M\sum_{i=j+1}^{n}b_i^2\\
 
m\sum_{i=1}^{j}b_i^2 &= M\sum_{i=j+1}^{n}b_i^2.
 
\end{align*}
 
 
</cmath>
 
</cmath>
  
Line 127: Line 68:
 
<math>0\le||a||^2-\frac{\langle a,b\rangle|^2}{||b||^2}</math>
 
<math>0\le||a||^2-\frac{\langle a,b\rangle|^2}{||b||^2}</math>
 
<math>\implies\langle a,b\rangle|^2\le||a||^2||b||^2=\langle a,a\rangle\cdot\langle b,b\rangle</math>. <math>\square</math>
 
<math>\implies\langle a,b\rangle|^2\le||a||^2||b||^2=\langle a,a\rangle\cdot\langle b,b\rangle</math>. <math>\square</math>
 
=== Examples ===
 
 
The elementary form of the Cauchy-Schwarz inequality is a special case of the general form, as is the '''Cauchy-Schwarz Inequality for Integrals''': for integrable functions <math> f,g : [a,b] \mapsto \mathbb{R} </math>,
 
<cmath>
 
\biggl( \int_{a}^b f(x)g(x)dx \biggr)^2 \le \int_{a}^b \bigl[ f(x) \bigr]^2dx \cdot \int_a^b \bigl[ g(x) \bigr]^2 dx
 
</cmath>
 
with equality when there exist constants <math> \mu, \lambda </math> not both equal to zero such that for <math> t \in [a,b] </math>,
 
<cmath>
 
\mu \int_a^t f(x)dx = \lambda \int_a^t g(x)dx .
 
</cmath>
 
  
 
==Problems==
 
==Problems==
Line 175: Line 105:
  
 
[[Category:Algebra]]
 
[[Category:Algebra]]
[[Category:Inequality]]
+
[[Category:Inequalities]]
[[Category:Theorems]]
 

Revision as of 04:28, 18 May 2023

In algebra, the Cauchy-Schwarz Inequality, also known as the Cauchy–Bunyakovsky–Schwarz Inequality or informally as Cauchy-Schwarz, is an inequality with many ubiquitous formulations in abstract algebra, calculus, and contest mathematics. In high-school competitions, its applications are limited to elementary and linear algebra.

Its elementary algebraic formulation is often referred to as Cauchy's Inequality and states that for any list of reals $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$, \[(a_1^2 + a_2^2 + \cdots + a_n^2)(b_1^2 + b_2^2 + \cdots + b_n^2) \geq (a_1b_1 + a_2b_2 + \cdots + a_nb_n)^2,\] with equality if and only if there exists a constant $t$ such that $a_i = t b_i$ for all $1 \leq i \leq n$, or if one list consists of only zeroes. Along with the AM-GM Inequality, Cauchy-Schwarz forms the foundation for inequality problems in intermediate and olympiad competitions. It is particularly crucial in proof-based contests.

Its vector formulation states that for any vectors $\overrightarrow{v}$ and $\overrightarrow{w}$ in $\mathbb{R}^n$, where $\overrightarrow{v} \cdot \overrightarrow{w}$ is the dot product of $\overrightarrow{v}$ and $\overrightarrow{w}$ and $\| \overrightarrow{v} \|$ is the norm of $\overrightarrow{v}$, \[\|\overrightarrow{v}\| \|\overrightarrow{w}\| \geq |\overrightarrow{v} \cdot \overrightarrow{w}|\] with equality if and only if there exists a scalar $t$ such that $\overrightarrow{v} = t \overrightarrow{w}$, or if one of the vectors is zero. This formulation comes in handy in linear algebra problems at intermediate and olympiad problems.

The full Cauchy-Schwarz Inequality is written in terms of abstract vector spaces. Under this formulation, the elementary algebraic, linear algebraic, and calculus formulations are different cases of the general inequality.

Proofs

Here is a list of proofs of Cauchy-Schwarz.

Consider the vectors $\mathbf{a} = \langle a_1, \ldots a_n \rangle$ and ${} \mathbf{b} = \langle b_1, \ldots b_n \rangle$. If $\theta$ is the angle formed by $\mathbf{a}$ and $\mathbf{b}$, then the left-hand side of the inequality is equal to the square of the dot product of $\mathbf{a}$ and $\mathbf{b}$, or $(\mathbf{a} \cdot \mathbf{b})^2 = a^2 b^2 (\cos\theta) ^2$ .The right hand side of the inequality is equal to $\left( ||\mathbf{a}|| * ||\mathbf{b}|| \right)^2  =  a^2b^2$. The inequality then follows from $|\cos\theta | \le 1$, with equality when one of $\mathbf{a,b}$ is a multiple of the other, as desired.

Lemmas

Complex Form

The inequality sometimes appears in the following form.

Let $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ be complex numbers. Then \[\left| \sum_{i=1}^na_ib_i \right|^2 \le \left(\sum_{i=1}^{n}|a_i^2| \right) \left( \sum_{i=1}^n |b_i^2| \right)\] This appears to be more powerful, but it follows from \[\left| \sum_{i=1}^n a_ib_i \right| ^2 \le \left( \sum_{i=1}^n |a_i| \cdot |b_i| \right)^2 \le \left(\sum_{i=1}^n |a_i^2| \right) \left( \sum_{i=1}^n |b_i^2| \right)\]

General Form

Let $V$ be a vector space, and let $\langle \cdot, \cdot \rangle : V \times V \to \mathbb{R}$ be an inner product. Then for any $\mathbf{a,b} \in V$, \[\langle \mathbf{a,b} \rangle^2 \le \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle ,\] with equality if and only if there exist constants $\mu, \lambda$ not both zero such that $\mu\mathbf{a} = \lambda\mathbf{b}$.

Proof 1

Consider the polynomial of $t$ \[\langle t\mathbf{a + b}, t\mathbf{a + b} \rangle = t^2\langle \mathbf{a,a} \rangle + 2t\langle \mathbf{a,b} \rangle + \langle \mathbf{b,b} \rangle .\] This must always be greater than or equal to zero, so it must have a non-positive discriminant, i.e., $\langle \mathbf{a,b} \rangle^2$ must be less than or equal to $\langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle$, with equality when $\mathbf{a = 0}$ or when there exists some scalar $-t$ such that $-t\mathbf{a} = \mathbf{b}$, as desired.

Proof 2

We consider \[\langle \mathbf{a-b, a-b} \rangle = \langle \mathbf{a,a} \rangle + \langle \mathbf{b,b} \rangle - 2 \langle \mathbf{a,b} \rangle .\] Since this is always greater than or equal to zero, we have \[\langle \mathbf{a,b} \rangle \le \frac{1}{2} \langle \mathbf{a,a} \rangle + \frac{1}{2} \langle \mathbf{b,b} \rangle .\] Now, if either $\mathbf{a}$ or $\mathbf{b}$ is equal to $\mathbf{0}$, then $\langle \mathbf{a,b} \rangle^2 = \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle = 0$. Otherwise, we may normalize so that $\langle \mathbf {a,a} \rangle = \langle \mathbf{b,b} \rangle = 1$, and we have \[\langle \mathbf{a,b} \rangle \le 1 = \langle \mathbf{a,a} \rangle^{1/2} \langle \mathbf{b,b} \rangle^{1/2} ,\] with equality when $\mathbf{a}$ and $\mathbf{b}$ may be scaled to each other, as desired.

Proof 3

Consider $a-\lambda b$ for some scalar $\lambda$. Then: $0\le||a-\lambda b||^2$ (by the Trivial Inequality) $=\langle a-\lambda b,a-\lambda b\rangle$ $=\langle a,a\rangle-2\lambda\langle a,b\rangle+\lambda^2\langle y,y\rangle$ $=||a||^2-2\lambda\langle a,b\rangle+\lambda^2||b||^2$. Now, let $\lambda=\frac{\langle a,b\rangle}{||b||^2}$. Then, we have: $0\le||a||^2-\frac{\langle a,b\rangle|^2}{||b||^2}$ $\implies\langle a,b\rangle|^2\le||a||^2||b||^2=\langle a,a\rangle\cdot\langle b,b\rangle$. $\square$

Problems

Introductory

  • Consider the function $f(x)=\frac{(x+k)^2}{x^2+1},x\in (-\infty,\infty)$, where $k$ is a positive integer. Show that $f(x)\le k^2+1$. (Source)
  • (APMO 1991 #3) Let $a_1$, $a_2$, $\cdots$, $a_n$, $b_1$, $b_2$, $\cdots$, $b_n$ be positive real numbers such that $a_1 + a_2 + \cdots + a_n = b_1 + b_2 + \cdots + b_n$. Show that

\[\frac {a_1^2}{a_1 + b_1} + \frac {a_2^2}{a_2 + b_2} + \cdots + \frac {a_n^2}{a_n + b_n} \geq \frac {a_1 + a_2 + \cdots + a_n}{2}\]

Intermediate

  • Let $ABC$ be a triangle such that

\[\left( \cot \frac{A}{2} \right)^2 + \left( 2 \cot \frac{B}{2} \right)^2 + \left( 3 \cot \frac{C}{2} \right)^2 = \left( \frac{6s}{7r} \right)^2 ,\] where $s$ and $r$ denote its semiperimeter and inradius, respectively. Prove that triangle $ABC$ is similar to a triangle $T$ whose side lengths are all positive integers with no common divisor and determine those integers. (Source)

Olympiad

  • $P$ is a point inside a given triangle $ABC$. $D, E, F$ are the feet of the perpendiculars from $P$ to the lines $BC, CA, AB$, respectively. Find all $P$ for which

\[\frac{BC}{PD} + \frac{CA}{PE} + \frac{AB}{PF}\] is least.

(Source)

Other Resources

Books