Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
try to prove that $<x,y> := x^t [a_{ij}] y$ is an inner product –  Alexander Thumm Mar 28 '11 at 15:05
add comment

1 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.

share|improve this answer
    
You could of course apply the cs inequality directly if you want to a short proof. –  Alexander Thumm Mar 28 '11 at 15:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.