Skip to main content
3 of 4
added 74 characters in body
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

EDIT Actually, Cauchy-Binet suffices as the OP notices in the comments. I'll leave my overkill proof here as for diversion.


The proof below appeals to a famous result of Schoenberg (I've simplified the statement a bit), and basic linear algebra.

Schoenberg's theorem (see e.g., [Prop. 3.2, 1]). Let $X$ be a nonempty set and $\psi: X \times X \mapsto \mathbb{R}$ be positive definite kernel. Then, there exists an RKHS $H$ and a map $\varphi : X \to H$ such that \begin{equation*} \|\varphi(x)-\varphi(y)\|_H^2 = \frac{1}{2}[\psi(x,x)+\psi(y,y)] - \psi(x,y). \end{equation*}

We show that the function $\psi(A,B) = \det(A^TB)$ is positive definite, which as a result of Schoenberg's theorem shows that \begin{equation*} 1-\det(A^TB) = \|\varphi(A)-\varphi(B)\|_H^2, \end{equation*} from which the triangle inequality is immediate.

To prove the positive definiteness of $\psi$, we show that it is an inner-product by invoking the Cauchy-Binet formula (using Wikipedia's notation, except that for us $A$ is $m \times n$): \begin{equation*} \det(A^TB) = \sum_{S \in \binom{[m]}{n}} \det(A^T_{[n],S})\det(B_{S,[n]}) = \sum_{S \in \binom{[m]}{n}} \det(A_{S,[n]})\det(B_{S,[n]}) = \langle \phi(A), \phi(B)\rangle. \end{equation*}

[1] C. Berg, J. P. R. Christensen, and P. Ressel. Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions, Springer GTM 100, 1984.

Suvrit
  • 28.6k
  • 7
  • 82
  • 150