On the Löwner-John Ellipsoids of the Metric Polytope

Abstract

The collection of all $n$-point metric spaces of diameter $\le 1$ constitutes a polytope ${\mathcal{M}}_n\subset {\mathbb{R}}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$, called the \emph{Metric Polytope}. In this paper, we consider the best approximations of ${\mathcal{M}}_n$ by ellipsoids. We give an exact explicit description of the largest volume ellipsoid contained in ${\mathcal{M}}_n$. When inflated by a factor of $\hat{I}˜(n)$, this ellipsoid contains ${\mathcal{M}}_n$. It also turns out that the least volume ellipsoid containing ${\mathcal{M}}_n$ is a ball. When shrunk by a factor of $\hat{I}˜(n)$, the resulting ball is contained in ${\mathcal{M}}_n$. We note that the general theorems on such ellipsoid posit only that the pertinent inflation/shrinkage factors can be made as small as $O(n^2)$.

17 pages