Semi-norms and symmetric bilinear forms

Back to Blog

13.03.2012 (25.05.2015)

Let $V$ be a real vector space and $\cdot : V \times V \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 $\lVert \; \cdot \; \rVert : V \to \mathbb{R}$ is such that $\lVert x \rVert = \sqrt{|x \cdot x|}$. then $\lVert \; \cdot \; \rVert$ is a semi-norm if and only if $\cdot$ is semi-definite.

Definitions

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

• symmetric, if $x \cdot y = y \cdot x$,
• positive-semi-definite, if $x \cdot x \geq 0$,
• negative-semi-definite, if $x \cdot x \leq 0$,
• semi-definite, if $(x \cdot x)(y \cdot y) \geq 0$,
• indefinite, if it is not semi-definite, and
• fulfilling the Cauchy-Schwarz inequality, if $(x \cdot y)^2 \leq (x \cdot x)(y \cdot y)$,
• degenerate, if there exists $u \in V \setminus \{0\}$ such that $u \cdot v = 0$, for all $v \in V$,

for all $x, y \in V$.

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

• positive-homogeneous, if $f(\alpha x) = |\alpha|f(x)$,
• fulfilling the triangle inequality, if $f(x + y) \leq f(x) + f(y)$,
• convex if $f((1 − t)x + ty) \leq (1 - t)f(x) + tf(y)$, and
• quasi-convex, if $f((1 − t)x + ty) \leq \max\{f(x),f(y)\}$.

for all $x, y \in V$, $\alpha \in \mathbb{R}$, and $t \in [0, 1]$.

Cauchy-Schwarz inequality is equivalent to semi-definiteness

Cauchy-Schwarz $\implies$ Semi-definite

Assume $\cdot$ is indefinite. Then there exists $x, y \in V$ such that $x \cdot x > 0$ and $y \cdot y < 0$. It follows that $(x \cdot y)^2 \leq (x \cdot x)(y \cdot y)$ does not hold; the left-hand side is non-negative and the right-hand side is negative. Therefore $\cdot$ does not fulfill the Cauchy-Schwarz inequality.

Cauchy-Schwarz $\impliedby$ Semi-definite

Assume $\cdot$ is semi-definite.

Case $y \cdot y = 0$

Let $\alpha \in \mathbb{R}^{> 0}$. Then

$$\begin{equation} \begin{split} (x + \alpha y) \cdot (x + \alpha y) & = x \cdot x + 2 \alpha (x \cdot y) + \alpha^2 (y \cdot y) \\ {} & = x \cdot x + 2 \alpha (x \cdot y) \\ {} & \geq 0, \end{split} \end{equation}$$

It follows that

$$\begin{equation} \begin{split} -\frac{x \cdot x}{2 \alpha} \leq x \cdot y, \end{split} \end{equation}$$

Similarly,

$$\begin{equation} \begin{split} (x - \alpha y) \cdot (x - \alpha y) \geq 0 \end{split} \end{equation}$$

shows that

$$\begin{equation} \begin{split} x \cdot y \leq \frac{x \cdot x}{2 \alpha}, \end{split} \end{equation}$$

Therefore,

$$\begin{equation} \begin{split} |x \cdot y| \leq \frac{x \cdot x}{2 \alpha}. \end{split} \end{equation}$$

Since $\alpha$ is arbitrary, we have that $x \cdot y = 0$. Therefore the Cauchy-Schwarz inequality holds.

Case $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$. By semi-definiteness, and $x_{\parallel} \cdot x_{\perp} = 0$,

$$\begin{equation} \begin{split} |x_{\parallel} \cdot x_{\parallel}| & \leq |x_{\parallel} \cdot x_{\parallel}| + 2 |x_{\parallel} \cdot x_{\perp}| + |x_{\perp} \cdot x_{\perp}| \\ {} & = |x_{\parallel} \cdot x_{\parallel} + 2 x_{\parallel} \cdot x_{\perp} + x_{\perp} \cdot x_{\perp}| \\ {} & = |(x_{\parallel} + x_{\perp}) \cdot (x_{\parallel} + x_{\perp})| \\ {} & = |x \cdot x|. \end{split} \end{equation}$$

This is the Cauchy-Schwarz inequality.

Convexity implies quasi-convexity

Let $f : V \to \mathbb{R}$ be a convex function. Then

$$\begin{equation} \begin{split} 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{split} \end{equation}$$

for all $x, y \in V$, and $t \in [0, 1]$. Therefore $f$ is quasi-convex.

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{equation} \begin{split} 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{f\left(\frac{x}{f(x)}\right),f\left(\frac{y}{f(y)}\right)} \\ {} & = 1. \end{split} \end{equation}$$

Using positive-homogenuity and non-negativeness,

$$\begin{equation} \begin{split} f(x + y) \leq f(x) + f(y). \end{split} \end{equation}$$

Therefore $f$ fulfills the triangle inequality.

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

$$\begin{equation} \begin{split} f(x + y) & = 2f(0.5x + 0.5y) \\ {} & \leq f(x) + f(y), \end{split} \end{equation}$$

for all $x, y \in V$. Therefore $f$ fulfills the triangle inequality. Assume $f$ fulfills the triangle inequality. Then

$$\begin{equation} \begin{split} f((1−t)x + ty) & \leq f((1−t)x) + f(ty) \\ {} & = (1−t)f(x) + tf(y), \end{split} \end{equation}$$

for all $t \in [0,1]$. Therefore f is convex.

Semi-definiteness is equivalent to triangle inequality

Let $\cdot : V \times V \to \mathbb{R}$ be a symmetric bilinear form, and $\lVert\cdot\rVert : V \to \mathbb{R}$ be such that $\lVert x \rVert = \sqrt{|x \cdot x|}$.

Triangle-inequality $\implies$ Semi-definite

Assume $\cdot$ is indefinite. 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 $\lVert (1 − t)x + ty \rVert = 0$ for $t \in \mathbb{R}$. The solution is

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

The discriminant is always positive, since $(x \cdot x)(y \cdot y) < 0$. Therefore, there are two points $a, b \in V$, with $\lVert a \rVert = 0$ and $\lVert b \rVert = 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 $\lVert \cdot \rVert$ were convex, it would hold that $\rVert x \lVert = 0$. Since this is not the case, $\lVert \cdot \rVert$ is not convex and the triangle inequality does not hold.

Triangle-inequality $\impliedby$ Semi-definite

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

$$\begin{equation} \begin{split} \lVert x + y \rVert^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| \\ {} & \leq |x \cdot x| + 2 \sqrt{(x \cdot x)(y \cdot y)} + |y \cdot y| \\ {} & = |x \cdot x| + 2 \sqrt{|x \cdot x||y \cdot y|} + |y \cdot y| \\ {} & = |x \cdot x| + 2 \sqrt{|x \cdot x|}\sqrt{|y \cdot y|} + |y \cdot y| \\ {} & = \lVert x \rVert^2 + 2 \lVert x \rVert \lVert y \rVert + \lVert y \rVert^2 \\ {} & = (\lVert x \rVert + \lVert y \rVert)^2. \end{split} \end{equation}$$

Thus the triangle inequality holds.

Remark 1.7.8 - Page generated 01.01.2023 00:19.