Difference between revisions of "Cauchy-Schwarz Inequality"

(Presented two forms for the linear algebraic formulation. If one of them is rarely used in comparison to the other, you should just delete it.)
Line 3: Line 3:
 
Its elementary algebraic formulation is often referred to as '''Cauchy's Inequality''' and states the following: 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_n = t b_n</math> for all <math>1 \leq t \leq n</math>, or if all the entries in one of the lists are zero. 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 elementary algebraic formulation is often referred to as '''Cauchy's Inequality''' and states the following: 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_n = t b_n</math> for all <math>1 \leq t \leq n</math>, or if all the entries in one of the lists are zero. 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 linear algebraic forulation states the following: for any vectors <math>\overrightarrow{v}</math> and <math>\overrightarrow{w}</math> in <math>\mathbb{R}^n</math>, <cmath>(\overrightarrow{v} \cdot \overrightarrow{v})(\overrightarrow{w} \cdot \overrightarrow{w}) \geq (\overrightarrow{v} \cdot \overrightarrow{w})^2, \textrm{ or equivalently}, \textrm{ } \|\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.
+
Its linear algebraic forulation states the following: for any vectors <math>\overrightarrow{v}</math> and <math>\overrightarrow{w}</math> in <math>\mathbb{R}^n</math>, <cmath>(\overrightarrow{v} \cdot \overrightarrow{v})(\overrightarrow{w} \cdot \overrightarrow{w}) \geq |\overrightarrow{v} \cdot \overrightarrow{w}|^2, \textrm{ or equivalently}, \textrm{ } \|\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.
  
 
=== Discussion ===
 
=== Discussion ===

Revision as of 22:24, 4 February 2022

In algebra, the Cauchy-Schwarz Inequality, also known as the Cauchy-Bunyakovsky-Schwarz Inequality or informally as Cauchy-Schwarz, is a ubiquitous inequality with many formulations. Its most general form is written in abstract vector spaces, but in contest math, its applications are limited to elementary algebraic and linear algebra.

Its elementary algebraic formulation is often referred to as Cauchy's Inequality and states the following: 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_n = t b_n$ for all $1 \leq t \leq n$, or if all the entries in one of the lists are zero. 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 linear algebraic forulation states the following: for any vectors $\overrightarrow{v}$ and $\overrightarrow{w}$ in $\mathbb{R}^n$, \[(\overrightarrow{v} \cdot \overrightarrow{v})(\overrightarrow{w} \cdot \overrightarrow{w}) \geq |\overrightarrow{v} \cdot \overrightarrow{w}|^2, \textrm{ or equivalently}, \textrm{ } \|\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.

Discussion

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.

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

Upper Bound on (Σa)(Σb)

Let $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ be two sequences of positive real numbers with \[0 < m \le \frac{a_i}{b_i} \le M\] for $1 \le i \le n$. Then \[\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,\] with equality if and only if, for some ordering of the pairs $(a_i,b_i) \mapsto (a_{\sigma(i)},b_{\sigma(i)})$, some $0 \le j \le n$ exists such that $a_{\sigma(i)}=mb_{\sigma(i)}$ for $1 \le \sigma(i) \le j$ and $a_{\sigma(i)}=Mb_{\sigma(i)}$ for $j+1 \le \sigma(i) \le n$, and \[m\sum_{\sigma(i)=1}^{j}b_{\sigma(i)}^2 = M\sum_{\sigma(i)=j+1}^{n}b_{\sigma(i)}^2.\] If we restrict that $m_1 \le a_i \le M_1$ and $m_2 \le b_i \le M_2$ for all $i$, then it's clear that for $a_i/b_i$ to be $m=m_1/M_2$ or $M=M_1/m_2$ for all $i$, then $a_i=m_1 \Longleftrightarrow b_i=M_2$ and $a_i=M_1 \Longleftrightarrow b_i=m_2$, so \[m\sum_{\sigma(i)=1}^{j}b_{\sigma(i)}^2 = M\sum_{\sigma(i)=j+1}^{n}b_{\sigma(i)}^2\] is equivalent to \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*} (When this is not an integer, the maximum occurs when $j$ is either the ceiling or floor of the right-hand side.) In the special case that $a_ib_i = k > 0$ is constant for all $i$, we have $M_1=1/m_2$ and $m_1=1/M_2$, so here $j$ must be $n/2$.

Proof

Note that for all $i$, we have \[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)\] or \[(M+m)a_ib_i \ge a_i^2+(Mm)b_i^2,\] with equality if and only if $a_i=mb_i$ or $a_i=Mb_i$. Summing up these inequalities over $1 \le i \le n$, we obtain from AM-GM that \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*} and squaring gives us the desired bound. For equality to occur, we must have $a_i=mb_i$ or $a_i=Mb_i$ for all $i$. If, without loss of generality, $a_i=mb_i$ for $1 \le i \le j$ and $a_i=Mb_i$ for $j+1 \le i \le n$ for some $0 \le j \le n$, then for the AM-GM to reach equality we must have (assume $M>m$ since $M=m$ is trivial) \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*}

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$

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 $f,g : [a,b] \mapsto \mathbb{R}$, \[\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\] with equality when there exist constants $\mu, \lambda$ not both equal to zero such that for $t \in [a,b]$, \[\mu \int_a^t f(x)dx = \lambda \int_a^t g(x)dx .\]

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