Cauchy-Schwarz inequality proof

Alicia Y. Tsai; Authors: Laurent EI Ghaoui; Contributors: Phan Hoang, Tony Tin, Ha To Tam, Nguyen Van Kep, Le Dinh Nam, Juliette Decugis, Nguyen Quoc Cuong.; Giuseppe C. Calafiore

Cauchy-Schwarz inequality proof

For any two vectors $x,y \in \mathbb{R}^n$ , we have

$\begin{align*} x^Ty &\leq ||x||_2\cdot ||y||_2. \\ \end{align*}$

The above inequality is an equality if and only if $x,y$ are collinear. In other words:

$\begin{align*} (P) \quad \max\limits_{x: ||x||_2 \leq 1} x^Ty &= ||y||_2, \\ \end{align*}$

with optimal $x$ given by $x^* = y/||y||_2$ if $y$ is non-zero.

Proof: The inequality is trivial if either one of the vectors $x,y$ is zero. Let us assume both are non-zero. Without loss of generality, we may re-scale $x$ and assume it has unit Euclidean norm ( $||x||_2=1$ ). Let us first prove that

$\begin{align*} x^Ty &\leq ||y||_2. \\ \end{align*}$

We consider the polynomial

$\begin{align*} p(t) &= ||tx-y||_2^2 = t^2 -2t(x^Ty) +y^Ty. \\ \end{align*}$

Since it is non-negative for every value of $t$ , its discriminant $\Delta = (x^Ty)^2-y^Ty$ is non-positive. The Cauchy-Schwartz inequality follows.

The second result is proven as follows. Let $v(P)$ be the optimal value of the problem. The Cauchy-Schwartz inequality implies that $v(P) \leq ||y||_2$ . To prove that the value is attained (it is equal to its upper bound), we observe that if $x = y/||y||_2$ , then