Difference between revisions of "Cauchy-Schwarz Inequality"

m (Olympiad)
(Remove vandalism: Undo revision 215809 by Marianasinta (talk))
(Tag: Undo)
 
(32 intermediate revisions by 10 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.
  
[[Augustin Louis Cauchy]] wrote the first paper about the elementary form in 1821. The general form was discovered by [[Viktor Bunyakovsky]] in 1849 and independently by [[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 exist constants <math>\mu, \lambda </math> not both zero such that for all <math> 1 \le i \le n </math>, <math>\mu a_i = \lambda b_i </math>.
 
  
=== Discussion ===
+
== Proofs ==
 +
Here is a list of proofs of Cauchy-Schwarz.
  
 
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 28: Line 26:
 
</cmath>
 
</cmath>
  
== Upper Bound on (Σa)(Σb) ==
+
=== A Useful Inequality ===
 +
Also known as Sedrakyan's Inequality,  Bergström's Inequality, Engel's Form or Titu's Lemma the following inequality is a direct result of Cauchy-Schwarz inequality:
  
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
+
For any real numbers <math>(a_1,a_2,...,a_n)</math> and <math>(b_1,b_2,...,b_n)</math> where <math>(b_i>0, i\in \{1,2,..,n\})</math> the following is true: <cmath> \frac{a_1^{2}}{b_1}+\frac{a_2^{2}}{b_2}+\ldots+\frac{a_n^{2}}{b_n}\geq\frac{\left(a_1+a_2+...+a_n\right)^{2}}{b_1+b_2+...+b_n}.</cmath>
 +
 
 +
== Real Vector Spaces ==
 +
 
 +
Let <math>V </math> be a [[vector space]], and let <math> \langle \cdot, \cdot \rangle : V \times V \to \mathbb{R} </math> be an [[inner product]].  Then for any <math> \mathbf{a,b} \in V </math>,
 
<cmath>
 
<cmath>
0 < m \le \frac{a_i}{b_i} \le M
+
\langle \mathbf{a,b} \rangle^2 \le \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle ,
 
</cmath>
 
</cmath>
for <math>1 \le i \le n</math>. Then
+
with equality if and only if there exist constants <math>\mu, \lambda </math> not both zero such that <math> \mu\mathbf{a} = \lambda\mathbf{b} </math>. The following proofs assume the inner product to be real-valued and commutative, and so only apply to vector spaces over the real numbers.
 +
 
 +
=== Proof 1 ===
 +
 
 +
Consider the polynomial of <math> t </math>
 
<cmath>
 
<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,
+
\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 .
 
</cmath>
 
</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
+
This must always be greater than or equal to zero, so it must have a non-positive discriminant, i.e., <math> \langle \mathbf{a,b} \rangle^2 </math> must be less than or equal to <math> \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle </math>, with equality when <math> \mathbf{a = 0} </math> or when there exists some scalar <math>-t </math> such that <math> -t\mathbf{a} = \mathbf{b} </math>, as desired.
 +
 
 +
=== Proof 2 ===
 +
 
 +
We consider
 
<cmath>
 
<cmath>
m\sum_{\sigma(i)=1}^{j}b_{\sigma(i)}^2 = M\sum_{\sigma(i)=j+1}^{n}b_{\sigma(i)}^2.
+
\langle \mathbf{a-b, a-b} \rangle = \langle \mathbf{a,a} \rangle + \langle \mathbf{b,b} \rangle - 2 \langle \mathbf{a,b} \rangle .
 
</cmath>
 
</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
+
Since this is always greater than or equal to zero, we have
 
<cmath>
 
<cmath>
m\sum_{\sigma(i)=1}^{j}b_{\sigma(i)}^2 = M\sum_{\sigma(i)=j+1}^{n}b_{\sigma(i)}^2
+
\langle \mathbf{a,b} \rangle \le \frac{1}{2} \langle \mathbf{a,a} \rangle + \frac{1}{2} \langle \mathbf{b,b} \rangle .
 
</cmath>
 
</cmath>
is equivalent to
+
Now, if either <math> \mathbf{a} </math> or <math> \mathbf{b} </math> is equal to <math> \mathbf{0} </math>, then <math> \langle \mathbf{a,b} \rangle^2 = \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle = 0 </math>.  Otherwise, we may [[normalize]] so that <math> \langle \mathbf {a,a} \rangle = \langle \mathbf{b,b} \rangle = 1 </math>, and we have
 
<cmath>
 
<cmath>
\begin{align*}
+
\langle \mathbf{a,b} \rangle \le 1 = \langle \mathbf{a,a} \rangle^{1/2} \langle \mathbf{b,b} \rangle^{1/2} ,
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>
 
</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>.
+
with equality when <math>\mathbf{a} </math> and <math> \mathbf{b} </math> may be scaled to each other, as desired.
 +
 
 +
=== Proof 3 ===
 +
 
 +
Consider <math>a-\lambda b</math> for some scalar <math>\lambda</math>. Then:
 +
<math>0\le||a-\lambda b||^2</math> (by the Trivial Inequality)
 +
<math>=\langle a-\lambda b,a-\lambda b\rangle</math>
 +
<math>=\langle a,a\rangle-2\lambda\langle a,b\rangle+\lambda^2\langle y,y\rangle</math>
 +
<math>=||a||^2-2\lambda\langle a,b\rangle+\lambda^2||b||^2</math>.
 +
Now, let <math>\lambda=\frac{\langle a,b\rangle}{||b||^2}</math>. Then, we have:
 +
<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>
 +
 
 +
== Complex Vector Spaces ==
 +
 
 +
For any two vectors <math>\mathbf{a}, \mathbf{b}</math> in the complex vector space <math>W</math>, the following holds:
 +
<cmath>|\langle \mathbf{a}, \mathbf{b}\rangle| \leq ||\mathbf{a}||||\mathbf{b}||</cmath> with equality holding only when <math>\mathbf{a}, \mathbf{b}</math> are linearly dependent.
  
 
=== Proof ===
 
=== Proof ===
 +
The following proof, a geometric argument that uses only the algebraic properties of the inner product, was discovered by Tarung Bhimnathwala in 2021.
  
Note that for all <math>i</math>, we have
+
Define the unit vectors <math>\mathbf{u}</math>, <math>\mathbf{v}</math> as <math>\mathbf{u} = \frac{\mathbf{a}}{||\mathbf{a}||}</math> and <math>\mathbf{v} = \frac{\mathbf{b}}{||\mathbf{b}||}</math>. Put <math>\gamma = \frac{\langle \mathbf{u},\mathbf{v}\rangle}{|\langle \mathbf{u},\mathbf{v}\rangle|}</math>. In other words, <math>\gamma</math> is the complex argument of <math>\langle \mathbf{u},\mathbf{v}\rangle</math> and lies on the unit circle. If any of the denominators are zero, the entire result follows trivially. Let <math>\mathbf{p} = \frac{1}{2}(\mathbf{u}+\gamma \mathbf{v})</math> and <math>\mathbf{q} = \frac{1}{2}(\mathbf{u}-\gamma \mathbf{v})</math>. Importantly, we have  
 +
<cmath>
 +
    \langle \mathbf{p},\mathbf{q}\rangle = \frac{1}{4}(||\mathbf{u}||^2 -\langle \mathbf{u},\gamma \mathbf{v}\rangle + \langle \gamma \mathbf{v},\mathbf{u}\rangle - \gamma \bar{\gamma}||\mathbf{v}||^2)
 +
</cmath>
 +
<cmath>
 +
    = \frac{1}{4}(1 -\langle \mathbf{u},\gamma \mathbf{v}\rangle + \langle \gamma \mathbf{v},\mathbf{u}\rangle - 1)
 +
</cmath>
 
<cmath>
 
<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)
+
    = \frac{1}{4}(\langle \gamma \mathbf{v},\mathbf{u}\rangle - \overline{\langle \gamma \mathbf{v},\mathbf{u}\rangle})  
 
</cmath>
 
</cmath>
or
 
 
<cmath>
 
<cmath>
(M+m)a_ib_i \ge a_i^2+(Mm)b_i^2,
+
    = \frac{1}{2}\operatorname{Im}(\langle \gamma \mathbf{v},\mathbf{u}\rangle)  
 
</cmath>
 
</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>
 
<cmath>
\begin{align*}
+
    = \frac{1}{2}\operatorname{Im}(\gamma\overline{\langle \mathbf{u},\mathbf{v}\rangle})  
(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>
 
</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>
 
<cmath>
\begin{align*}
+
    = 0.
\sum_{i=1}^{n}a_i^2 &= Mm\sum_{i=1}^{n}b_i^2\\
+
</cmath>
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\\
+
Since <math>\mathbf{u}=\mathbf{p}+\mathbf{q}</math> and <math>\mathbf{v} = \bar{\gamma}(\mathbf{p}-\mathbf{q})</math>, this calculation shows that <math>\mathbf{p}</math> and <math>\mathbf{q}</math> form an orthogonal basis of the linear subspace spanned by <math>\mathbf{u}</math> and <math>\mathbf{v}</math>. Thus we can think of <math>\mathbf{u}</math> and <math>\mathbf{v}</math> as lying on the unit sphere in this subspace, which is isomorphic to <math>\mathbb{C}^2</math>. Another thing to note is that
(m-M)m\sum_{i=1}^{j}b_i^2 &= (m-M)M\sum_{i=j+1}^{n}b_i^2\\
+
<cmath>
m\sum_{i=1}^{j}b_i^2 &= M\sum_{i=j+1}^{n}b_i^2.
+
    ||\mathbf{p}||^2 + ||\mathbf{q}||^2 = \langle \mathbf{p},\mathbf{p} \rangle + \langle \mathbf{q},\mathbf{q} \rangle
\end{align*}
+
</cmath>
 +
<cmath>
 +
    = \frac{1}{4}(\langle \mathbf{u}+\gamma \mathbf{v},\mathbf{u}+\gamma \mathbf{v}\rangle + \langle \mathbf{u}-\gamma \mathbf{v},\mathbf{u}-\gamma \mathbf{v}\rangle)  
 +
</cmath>
 +
<cmath>
 +
    = \frac{1}{4}(2\langle \mathbf{u},\mathbf{u} \rangle + 2\gamma\bar{\gamma}\langle \mathbf{v},\mathbf{v} \rangle)
 +
</cmath>
 +
<cmath>
 +
    = \frac{1}{4}(2||\mathbf{u}||^2 + 2||\mathbf{v}||^2)
 +
</cmath>
 +
<cmath>
 +
    = 1.
 
</cmath>
 
</cmath>
  
== General Form ==
+
The previous two calculations established that <math>\mathbf{p}</math> and <math>\mathbf{q}</math> are orthogonal, and that the sum of their squared norms is <math>1</math>. Now we have
 
+
<cmath>
Let <math>V </math> be a [[vector space]], and let <math> \langle \cdot, \cdot \rangle : V \times V \to \mathbb{R} </math> be an [[inner product]].  Then for any <math> \mathbf{a,b} \in V </math>,
+
    |\langle \mathbf{u},\mathbf{v}\rangle| = |\langle \mathbf{p}+\mathbf{q},\bar{\gamma}(\mathbf{p}-\mathbf{q})\rangle|
 +
</cmath>
 
<cmath>
 
<cmath>
\langle \mathbf{a,b} \rangle^2 \le \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle ,
+
    = |\gamma||\langle \mathbf{p}+\mathbf{q},\mathbf{p}-\mathbf{q}\rangle|
 
</cmath>
 
</cmath>
with equality if and only if there exist constants <math>\mu, \lambda </math> not both zero such that <math> \mu\mathbf{a} = \lambda\mathbf{b} </math>.
 
 
=== Proof 1 ===
 
 
Consider the polynomial of <math> t </math>
 
 
<cmath>
 
<cmath>
\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 .
+
    = |\langle \mathbf{p}+\mathbf{q},\mathbf{p}-\mathbf{q}\rangle|
 
</cmath>
 
</cmath>
This must always be greater than or equal to zero, so it must have a non-positive discriminant, i.e., <math> \langle \mathbf{a,b} \rangle^2 </math> must be less than or equal to <math> \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle </math>, with equality when <math> \mathbf{a = 0} </math> or when there exists some scalar <math>-t </math> such that <math> -t\mathbf{a} = \mathbf{b} </math>, as desired.
 
 
=== Proof 2 ===
 
 
We consider
 
 
<cmath>
 
<cmath>
\langle \mathbf{a-b, a-b} \rangle = \langle \mathbf{a,a} \rangle + \langle \mathbf{b,b} \rangle - 2 \langle \mathbf{a,b} \rangle .
+
    = |||\mathbf{p}||^2 +\langle \mathbf{q},\mathbf{p}\rangle - \langle \mathbf{p},\mathbf{q}\rangle - ||\mathbf{q}||^2|
 
</cmath>
 
</cmath>
Since this is always greater than or equal to zero, we have
 
 
<cmath>
 
<cmath>
\langle \mathbf{a,b} \rangle \le \frac{1}{2} \langle \mathbf{a,a} \rangle + \frac{1}{2} \langle \mathbf{b,b} \rangle .
+
    = |||\mathbf{p}||^2 - ||\mathbf{q}||^2|
 
</cmath>
 
</cmath>
Now, if either <math> \mathbf{a} </math> or <math> \mathbf{b} </math> is equal to <math> \mathbf{0} </math>, then <math> \langle \mathbf{a,b} \rangle^2 = \langle \mathbf{a,a} \rangle \langle \mathbf{b,b} \rangle = 0 </math>.  Otherwise, we may [[normalize]] so that <math> \langle \mathbf {a,a} \rangle = \langle \mathbf{b,b} \rangle = 1 </math>, and we have
 
 
<cmath>
 
<cmath>
\langle \mathbf{a,b} \rangle \le 1 = \langle \mathbf{a,a} \rangle^{1/2} \langle \mathbf{b,b} \rangle^{1/2} ,
+
    = |||\mathbf{p}||^2 + ||\mathbf{q}||^2 - 2||\mathbf{q}||^2|
 
</cmath>
 
</cmath>
with equality when <math>\mathbf{a} </math> and <math> \mathbf{b} </math> may be scaled to each other, as desired.
 
 
=== 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>
 
<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
+
    = |1 - 2||\mathbf{q}||^2|
 
</cmath>
 
</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>
 
<cmath>
\mu \int_a^t f(x)dx = \lambda \int_a^t g(x)dx .
+
    \leq 1.
 
</cmath>
 
</cmath>
 +
Equality holds when either <math>||\mathbf{q}||=0</math> or <math>||\mathbf{q}||=1</math>, or equivalently when <math>\mathbf{u}=\pm \mathbf{v}</math> and <math>\mathbf{a} = \lambda \mathbf{b}</math>. Lastly, multiplying each side by <math>||\mathbf{a}||||\mathbf{b}||</math>, we have <cmath>|\langle \mathbf{a},\mathbf{b}\rangle| \leq ||\mathbf{a}||||\mathbf{b}||.</cmath>
  
 
==Problems==
 
==Problems==
Line 161: Line 181:
  
 
[[Category:Algebra]]
 
[[Category:Algebra]]
[[Category:Inequality]]
+
[[Category:Inequalities]]
[[Category:Theorems]]
 

Latest revision as of 15:28, 22 February 2024

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)\]

A Useful Inequality

Also known as Sedrakyan's Inequality, Bergström's Inequality, Engel's Form or Titu's Lemma the following inequality is a direct result of Cauchy-Schwarz inequality:

For any real numbers $(a_1,a_2,...,a_n)$ and $(b_1,b_2,...,b_n)$ where $(b_i>0, i\in \{1,2,..,n\})$ the following is true: \[\frac{a_1^{2}}{b_1}+\frac{a_2^{2}}{b_2}+\ldots+\frac{a_n^{2}}{b_n}\geq\frac{\left(a_1+a_2+...+a_n\right)^{2}}{b_1+b_2+...+b_n}.\]

Real Vector Spaces

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}$. The following proofs assume the inner product to be real-valued and commutative, and so only apply to vector spaces over the real numbers.

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$

Complex Vector Spaces

For any two vectors $\mathbf{a}, \mathbf{b}$ in the complex vector space $W$, the following holds: \[|\langle \mathbf{a}, \mathbf{b}\rangle| \leq ||\mathbf{a}||||\mathbf{b}||\] with equality holding only when $\mathbf{a}, \mathbf{b}$ are linearly dependent.

Proof

The following proof, a geometric argument that uses only the algebraic properties of the inner product, was discovered by Tarung Bhimnathwala in 2021.

Define the unit vectors $\mathbf{u}$, $\mathbf{v}$ as $\mathbf{u} = \frac{\mathbf{a}}{||\mathbf{a}||}$ and $\mathbf{v} = \frac{\mathbf{b}}{||\mathbf{b}||}$. Put $\gamma = \frac{\langle \mathbf{u},\mathbf{v}\rangle}{|\langle \mathbf{u},\mathbf{v}\rangle|}$. In other words, $\gamma$ is the complex argument of $\langle \mathbf{u},\mathbf{v}\rangle$ and lies on the unit circle. If any of the denominators are zero, the entire result follows trivially. Let $\mathbf{p} = \frac{1}{2}(\mathbf{u}+\gamma \mathbf{v})$ and $\mathbf{q} = \frac{1}{2}(\mathbf{u}-\gamma \mathbf{v})$. Importantly, we have \[\langle \mathbf{p},\mathbf{q}\rangle = \frac{1}{4}(||\mathbf{u}||^2 -\langle \mathbf{u},\gamma \mathbf{v}\rangle + \langle \gamma \mathbf{v},\mathbf{u}\rangle - \gamma \bar{\gamma}||\mathbf{v}||^2)\] \[= \frac{1}{4}(1 -\langle \mathbf{u},\gamma \mathbf{v}\rangle + \langle \gamma \mathbf{v},\mathbf{u}\rangle - 1)\] \[= \frac{1}{4}(\langle \gamma \mathbf{v},\mathbf{u}\rangle - \overline{\langle \gamma \mathbf{v},\mathbf{u}\rangle})\] \[= \frac{1}{2}\operatorname{Im}(\langle \gamma \mathbf{v},\mathbf{u}\rangle)\] \[= \frac{1}{2}\operatorname{Im}(\gamma\overline{\langle \mathbf{u},\mathbf{v}\rangle})\] \[= 0.\] Since $\mathbf{u}=\mathbf{p}+\mathbf{q}$ and $\mathbf{v} = \bar{\gamma}(\mathbf{p}-\mathbf{q})$, this calculation shows that $\mathbf{p}$ and $\mathbf{q}$ form an orthogonal basis of the linear subspace spanned by $\mathbf{u}$ and $\mathbf{v}$. Thus we can think of $\mathbf{u}$ and $\mathbf{v}$ as lying on the unit sphere in this subspace, which is isomorphic to $\mathbb{C}^2$. Another thing to note is that \[||\mathbf{p}||^2 + ||\mathbf{q}||^2 = \langle \mathbf{p},\mathbf{p} \rangle + \langle \mathbf{q},\mathbf{q} \rangle\] \[= \frac{1}{4}(\langle \mathbf{u}+\gamma \mathbf{v},\mathbf{u}+\gamma \mathbf{v}\rangle + \langle \mathbf{u}-\gamma \mathbf{v},\mathbf{u}-\gamma \mathbf{v}\rangle)\] \[= \frac{1}{4}(2\langle \mathbf{u},\mathbf{u} \rangle + 2\gamma\bar{\gamma}\langle \mathbf{v},\mathbf{v} \rangle)\] \[= \frac{1}{4}(2||\mathbf{u}||^2 + 2||\mathbf{v}||^2)\] \[= 1.\]

The previous two calculations established that $\mathbf{p}$ and $\mathbf{q}$ are orthogonal, and that the sum of their squared norms is $1$. Now we have \[|\langle \mathbf{u},\mathbf{v}\rangle| = |\langle \mathbf{p}+\mathbf{q},\bar{\gamma}(\mathbf{p}-\mathbf{q})\rangle|\] \[= |\gamma||\langle \mathbf{p}+\mathbf{q},\mathbf{p}-\mathbf{q}\rangle|\] \[= |\langle \mathbf{p}+\mathbf{q},\mathbf{p}-\mathbf{q}\rangle|\] \[= |||\mathbf{p}||^2 +\langle \mathbf{q},\mathbf{p}\rangle - \langle \mathbf{p},\mathbf{q}\rangle - ||\mathbf{q}||^2|\] \[= |||\mathbf{p}||^2 - ||\mathbf{q}||^2|\] \[= |||\mathbf{p}||^2 + ||\mathbf{q}||^2 - 2||\mathbf{q}||^2|\] \[= |1 - 2||\mathbf{q}||^2|\] \[\leq 1.\] Equality holds when either $||\mathbf{q}||=0$ or $||\mathbf{q}||=1$, or equivalently when $\mathbf{u}=\pm \mathbf{v}$ and $\mathbf{a} = \lambda \mathbf{b}$. Lastly, multiplying each side by $||\mathbf{a}||||\mathbf{b}||$, we have \[|\langle \mathbf{a},\mathbf{b}\rangle| \leq ||\mathbf{a}||||\mathbf{b}||.\]

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