Cauchy-Schwartz Inequality

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

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

$(P) ;;;; max_{x ::: |x|_2 le 1} : x^Ty = |y|_2,$

with optimal given by x^ast = y/|y|_2 if 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 and assume it has unit Euclidean norm ( |x|_2 = 1 ). Let us first prove that

We consider the polynomial

p(t) = |t x - y|_2^2 = t^2 -2 t(x^Ty) + y^Ty.

Since it is non-negative for every value of , 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) le |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

$x^Ty = frac{y^Ty}{|y|_2} = |y|_2.$

The vector x = y/|y|_2 is feasible for the optimization problem (P) . This establishes a lower bound on the value of (P) , v(P) :

$|y|_2 le v(P) = max_{x ::: |x|_2 le 1} : x^Ty .$