Semi-norms and symmetric bilinear forms

Let $V$ be a real vector space and $\cdot : V^2 \to \mathbb{R}$ a symmetric bilinear form. In this post I will first show that Cauchy-Schwarz inequality is equivalent to $\cdot$ being semi-definite. I will then show that for a non-negative positive-homogeneous function $f : V \to \mathbb{R}$ the triangle inequality, convexity, and quasi-convexity are all equivalent. Finally, I will show that if  $|\cdot|: V \to \mathbb{R} : |x| = \sqrt{|x \cdot x|}$, then $|\cdot|$  is a semi-norm if and only if $\cdot$ is semi-definite. 

Definitions

A bilinear form $\cdot : V^2 \to \mathbb{R}$ is called

• symmetric, if $\forall x, y \in V: x \cdot y = y \cdot x$,
• positive-semi-definite, if $\forall x \in V: x\cdot x \geq 0$,
• negative-semi-definite, if $\forall x \in V: x \cdot x \leq 0$,
• semi-definite, if it is either positive-semi-definite or negative-semi-definite,
• indefinite, if it is not semi-definite, and
• fulfilling the Cauchy-Schwarz inequality, if $\forall x, y \in V: (x \cdot y)^2 \leq (x\cdot x)(y \cdot y).$

A function $f : V \to \mathbb{R}$ is called

• positive-homogeneous, if $\forall x \in V: \forall \alpha \in \mathbb{R}: f(\alpha x) = |\alpha| f(x)$,
• fulfilling the triangle inequality, if $\forall x, y \in V: f(x + y) \leq f(x) + f(y),$
• convex if $\forall x, y \in V: \forall t \in [0, 1] \subset \mathbb{R}: f((1 - t)x + ty) \leq (1 - t)f(x) + tf(y)$, and
• quasi-convex, if $\forall x, y \in V: \forall t \in [0, 1] \subset \mathbb{R}: f((1 - t)x + ty) \leq \max\{f(x), f(y)\}.$

Cauchy-Schwarz inequality is equivalent to semi-definiteness

Assume the Cauchy-Schwarz inequality holds but that $\cdot$ is indefinite. Then there exists $x, y \in V$ such that $x \cdot x > 0$ and $y \cdot y < 0$. Then $(x \cdot y)^2 \leq (x \cdot x)(y \cdot y)$ does not hold since the left-hand side is non-negative and the right-hand side is negative. This is a contradiction. Therefore $\cdot$ is semi-definite.

Assume $\cdot$ is semi-definite. First, if $y \cdot y = 0$, then the Cauchy-Schwarz inequality holds trivially. Assume $y \cdot y \neq 0$. Decompose $x$ as $x = x_{\parallel} + x_{\perp}$, where $x_{\parallel} = \frac{x \cdot y}{y \cdot y} y$ is the orthogonal projection of $x$ to $y$, and $x_{\perp} = x - x_{\parallel}$ is the rejection of $x$ from $y$. Then, by semi-definiteness, the Cauchy-Schwarz inequality states that

$$|x_{\parallel} \cdot x_{\parallel }| \leq |x \cdot x|.$$

Again by semi-definiteness, and $x_{\parallel} \cdot x_{\perp} = 0$,

$$|x_{\parallel} \cdot x_{\parallel}| \leq |x_{\parallel} \cdot x_{\parallel } + 2 x_{\parallel} \cdot x_{\perp} + x_{\perp} \cdot x_{\perp}| = |x \cdot x|.$$

Therefore the Cauchy-Schwarz inequality holds. QED.

Convexity implies quasi-convexity

Let $f : V \to \mathbb{R}$ be a convex function. Let $x, y \in V$, and $t \in [0, 1] \subset \mathbb{R}$. Now 

$$\begin{eqnarray} f((1 - t) x + tf(y)) & \leq & (1 - t)f(x) + tf(y) \\ {} & \leq & (1 - t) \max\{f(x), f(y)\} + t\max\{f(x), f(y)\}\\ {} & = & \max\{f(x), f(y)\}. \end{eqnarray}$$

Therefore $f$ is quasi-convex. QED.

Quasi-convexity + non-negativity + positive-homogenuity implies triangle inequality

Let $f : V \to \mathbb{R}$ be a non-negative quasi-convex positive-homogeneous function. For $x, y \in V$, let $t = f(y) / (f(x) + f(y))$. Now

$$\begin{eqnarray}f\left(\frac{x + y}{f(x) + f(y)}\right) & = & f\left((1 - t) \frac{x}{f(x)} + t\frac{y}{f(y)}\right) \\ {} & \leq & \max\left\{f\left(\frac{x}{f(x)}\right), f\left(\frac{y}{f(y)}\right)\right\} \\ {} & = & 1.\end{eqnarray}$$

Using positive-homogenuity and non-negativeness, 

$$f(x + y) \leq f(x) + f(y).$$

Therefore $f$ fulfills the triangle inequality. QED.

For positive-homogeneous functions convexity and triangle inequality are equivalent

Let $f : V \to \mathbb{R}$ be a positive-homogeneous function. Assume $f$ is convex. Then $f(x + y) = 2f(0.5 x + 0.5 y) \leq f(x) + f(y).$ Therefore $f$ fulfills the triangle inequality. Assume $f$ fulfills the triangle inequality. Let $t \in [0, 1] \in \mathbb{R}$. Then $f((1 - t)x + ty) \leq f((1 - t)x) + f(ty) = (1 - t)f(x) + tf(y)$. Therefore $f$ is convex. QED.

Semi-definiteness is equivalent to triangle inequality

Let $\cdot : V^2 \to \mathbb{R}$ be a symmetric bilinear form, and $|\cdot|: V \to \mathbb{R} : |x| = \sqrt{|x \cdot x|}$.  Assume $\cdot$ is indefinite. Then by indefiniteness there exists $x, y \in V$ such that $x \cdot x > 0$ and $y \cdot y < 0$. Now one can solve the quadratic equation $|(1 - t)x + ty| = 0$ for $t \in \mathbb{R}$. The solution is

$$t = \frac{x \cdot (x + y) \pm \sqrt{(x \cdot y)^2 - (x \cdot x)(y \cdot y)}}{(x+y)\cdot(x+y)}.$$

The discriminant is always positive, since $(x \cdot x)(y \cdot y) < 0$. Therefore, there are two points $a, b \in V$, with $|a| = 0$ and $|b| = 0$, which lie on the same line as $x$ and $y$. Either $x$ or $y$ is a convex combination of $a$ and $b$. Without loss of generality, assume it is $x$. If $|\cdot|$ were convex, it would hold that $|x| = 0$. Since this is not the case, $|\cdot|$ is not convex and the triangle inequality does not hold.

Assume $\cdot$ is semi-definite. Then the Cauchy-Schwarz inequality holds and $(x \cdot x)(y \cdot y) \geq 0$. Now,

$$\begin{eqnarray}|x+y|^2 & = & |(x + y) \cdot (x + y)| \\ {} & = & |x \cdot x + 2 x\cdot y + y\cdot y| \\ {} & \leq & |x \cdot x| + 2 |x\cdot y| + |y\cdot y| \\ {} & = & |x \cdot x| + 2 \sqrt{|x \cdot x|}\sqrt{|y \cdot y|} + |y \cdot y| \\ {} & = & (|x| + |y|)^2.\end{eqnarray}$$

Thus the triangle inequality holds. QED.