While reading this thread I wanted to prove that Mahalanobis norm $\lVert{x-y}\rVert_m$ is a norm indeed. The norm is defined like so: $\lVert{x-y}\rVert_m=d(x-y,0)=d(x,y)=\sqrt{(x-y)^T S (x-y)}=\sqrt{(x-y,x-y)_m}$, where $(x,y)_m$ is the Mahalanobis inner product, and $(x,y)_m=x^T S y$. To proceed, I need to demonstrate the properties that every norm should satisfy, they are:
- $\lVert{a x}\rVert_m = |a| \lVert{x}\rVert_m$, for $a \in \mathbb{R}$
- $\lVert{x}\rVert_m = 0 \iff x=0$
- $0 \le \lVert{x}\rVert_m$
- $\lVert{x+y}\rVert_m \le \lVert{x}\rVert + \lVert{y}\rVert_m$
Although I was able to prove 1-3, I haven't been able to solve triangle inequality. Using $\lVert{x+y}\rVert_m^2 \le (\lVert{x}\rVert_m + \lVert{y}\rVert_m)^2$ I came up with a expression similar to Holder's inequality:
$$ y^T S x + x^T S y \le 2 {\sqrt{x^T S x}} {\sqrt{y^T S y}}, $$
From there I can argue that triangle's inequality is true because it became Holder's inequality, which is true too (I can cite a reference or dig deeper to prove Holder's inequality). But, how can I make the jump to Holder's inner product notation $|(x,y)_m|\le\|x\|\|y\|$ without saying that $\lVert{x}\rVert_m^2=(x,x)_m$? (the inner product is induced by the norm, but I haven't proved that yet, so I can't use it). Also, do I need to make any assumptions regarding the invertibility of the covariance matrix $S$ to ensure all this reasoning makes sense?
Let $S$ be a symmetric $n\times n$ matrix. The Mahalanobis norm is defined like so: $$ \|x\|_S=\sqrt{x^TSx}. $$ Necessarily, for $\|\cdot \|_S$ to be a norm, $S$ has to be positive-definite. By spectral theorem for symmetric matrices (see here or here), there are a diagonal $n\times n$ matrix $\Lambda=\mathrm{diag}(\lambda_1,\lambda_2,\ldots,\lambda_n)$ and an orthogonal $n\times n$ matrix $Q$ (i.e. $ Q^TQ=I$), such that $Q^T=Q^{-1}$ and: $$ S=Q^T\Lambda Q. $$ By definition, the matrix $S$ is positive-definite. Then: \begin{align*} \lambda_1 > 0 \\ \lambda_2> 0 \\ \ldots\\ \lambda_n> 0. \end{align*} Let the matrix: $$ U=\mathrm{diag}(\sqrt{\lambda_1},\sqrt{\lambda_2},\ldots,\sqrt{\lambda_n}) \, Q, $$ note that: $$ S=U^TU. $$ Set $\tilde{x}=Ux$ and $\tilde{y}=Uy$. Let $\|v \|_E=\sqrt{v_1^2+v_2^2+\ldots+v_2^2}$ the usual euclidean norm. Then: \begin{align*} \| x \|_S= \|\tilde{x}\|_E && (\ast)\\ \| y \|_S= \|\tilde{y}\|_E && (\ast\ast)\\ \|x+y \|_S= \|\tilde{x}+\tilde{y}\|_E. &&(\ast\ast\ast)\\ \end{align*} By usual triangular inequality we have : $$ \|\tilde{x}+\tilde{y}\|_E \leq \|\tilde{x}\|_E +\|\tilde{y}\|_E. $$ By equalities $(\ast)$, $(\ast\ast)$ and $(\ast\ast\ast)$ we have: $$ \|x+y \|_S \leq \| x \|_S+\| y \|_S $$