3
$\begingroup$

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.

  • 2
    try to prove that $ := x^t [a_{ij}] y$ is an inner product2011-03-28

1 Answers 1

5

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.

  • 0
    You could of course apply the cs inequality directly if you want to a short proof.2011-03-28