[Math] Triangle inequality for positive definite symmetric real matrix

metric-spacestriangles

Show that
\begin{equation}
\rho(\mathbf{x},\mathbf{y}) = \sqrt{\sum\limits_{i,j=1}^n a_{ij} (x_i-y_i)(x_j-y_j)},
\end{equation}
with $a_{ij} = a_{ji}$, $\mathbf{x} = (x_1,\ldots \;, x_n)$ and $\mathbf{y} = (y_1,\ldots \;,y_n)$, satisfies the triangle inequality.

$[a_{ij}]_{n \times n}$, by the way, is a symmetric, positive-definite matrix with real entries.

I'm often pretty terrible at proving the triangle inequality, so any insights would be greatly appreciated.

Best Answer

Let me elaborate on Alexander's comment. I'd do it in four steps, each of which is instructive in its own right:

  1. $\langle x, y \rangle = x^T A y = \sum_{i,j=1}^{n} x_{i} a_{ij} y_{j}$ is an inner product, that is to say, it is bilinear, symmetric and positive definite (this is because $A$ is symmetric and positive definite).

  2. An inner product satisfies the Cauchy-Schwarz inequality $|\langle x,y\rangle|^2 \leq \langle x,x\rangle \langle y, y \rangle$ (a proof can be found on the Wikipedia page I'm linking to, so I'm not repeating it here).

  3. Put $\|x\| = \sqrt{\langle x, x\rangle}$. The Cauchy-Schwarz inequality then reads $|\langle x,y \rangle| \leq \|x\| \|y\|$ and this implies that $\|x\|$ is a norm because $$\|x + y\|^2 = \langle x+ y, x + y \rangle = \langle x, x \rangle + \langle x,y \rangle + \langle y,x \rangle + \langle y, y \rangle$$ and by Cauchy-Schwarz we have $|\langle x,y \rangle + \langle y,x \rangle| \leq 2\|x\|\|y\|$ so that $\|x + y\|^2 \leq (\|x\| + \|y\|)^2$. Taking square-roots on both sides this gives the triangle inequality $$\|x + y\| \leq \|x\| + \|y\|$$ for norms. The remaining requirements for $\|\cdot\|$ to be a

  4. Every norm $\|\cdot\|$ on a vector space yields a metric by $d(x,y) = \|x-y\|$. I leave this to you to check in detail. The triangle inequality for $d$ follows from the triangle inequality for norms as follows $$d(x,y) = \|x - y\| = \|(x-z) + (z-y)\| \leq \|x - z\| + \|z-y\| = d(x,z) + d(z,y)$$ for all $x,y,z$.

Piecing the four points together, we get that $\|x - y\| = \sqrt{\langle x-y, x-y\rangle}$ is a metric, in particular it satisfies the triangle inequality.

Related Question