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.

$\endgroup$
1
  • 2
    $\begingroup$ try to prove that $<x,y> := x^t [a_{ij}] y$ is an inner product $\endgroup$ Commented Mar 28, 2011 at 15:05

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You could of course apply the cs inequality directly if you want to a short proof. $\endgroup$ Commented Mar 28, 2011 at 15:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .