A problem on distance matrices of subsets of the Hamming cube

Abstract

Let $D$ denote the distance matrix for an $n+1$ point metric space $(X,d)$. In the case that $X$ is an unweighted metric tree, the sum of the entries in $D^{-1}$ is always equal to $2/n$. Such trees can be considered as affinely independent subsets of the Hamming cube $H_n$, and it was conjectured that the value $2/n$ was minimal among all such subsets. In this paper we confirm this conjecture and give a geometric interpretation of our result which applies to any subset of $H_n$.

1. Introduction

There is a long study of the interaction between properties of finite metric spaces and properties of their distance matrices. The most classical questions in this area concern whether the metric space can be isometrically embedded in a Euclidean space, a problem solved by Schoenberg 14, or else in some other standard normed space. Properties of the metric space are often reflected in linear algebraic properties of the distance matrix involving say the determinant or inverse of the matrix.

To fix some notation, let $(X,d)$ denote a finite metric space with elements $\{x_1,\dots ,x_m\}$ (with $m \ge 2$) and let $D = D_X$ denote its distance matrix $(d(x_i,x_j))_{i,j=1}^m$. Let $\mathbf{1}$ denote the vector $(1,\dots ,1)^T \in \mathbb{R}^m$ so that for any $m \times m$ matrix $A$, $\langle A \mathbf{1}, \mathbf{1} \rangle$ gives the sum of the entries in $A$.

One particular class of spaces for which this relationship has been much studied are those which are (isometric to) subsets of Hamming cubes $H_n = \{0,1\}^n$ with the Hamming metric $d_1$ (which is the $\ell ^1$ metric on $\mathbb{R}^n$, restricted to these spaces). (See, for example, 23456.) This class includes, for example, all unweighted metric trees. Much of 2 concerns extending Graham and Pollak’s 4 formula, $\det (D) = (-1)^n n 2^{n-1}$, for the distance matrix of an $n+1$ point unweighted metric tree.

If $X$ is an $n+1$ point unweighted metric tree in $H_n$, then $D$ is invertible. In 2 it was shown that the subsets of $H_n$ for which the distance matrix $D$ is invertible are precisely the ones for which the points form an affinely independent subset of $\mathbb{R}^n$. They showed that for an $n+1$ point unweighted metric tree the sum of the entries in $D^{-1}$, that is $\langle D^{-1} \mathbf{1}, \mathbf{1} \rangle$, is always equal to $2/n$ and conjectured, based on empirical evidence, that this value was minimal among all affinely independent subsets of $H_n$. The aim of this note is to prove this conjecture and to provide geometric interpretations for the value of this quantity.

A consequence of Theorem 5.1 will be the following two results.

Theorem 1.1.

Suppose that $X$ is an affinely independent subset of the Hamming cube $(H_n,d_1)$ with at least two points. Then

$$\begin{equation} \langle D^{-1} \mathbf{1}, \mathbf{1} \rangle = \left(\frac{n}{2} - 2 d_2(h,Z_X)^2\right)^{-1}, {\tag{1}} \end{equation}$$

where $d_2(h,Z_X)$ is the Euclidean distance from the point $h = \bigl (\frac{1}{2},\dots ,\frac{1}{2}\bigr )$ to the affine subspace $Z_X \subseteq \mathbb{R}^n$ spanned by the elements of $X$.

Corollary 1.2.

Suppose that $X$ is an affinely independent subset of the Hamming cube $(H_n,d_1)$ with at least two points. Then

$$\begin{equation*} \frac{2}{n} \le \langle D^{-1} \mathbf{1}, \mathbf{1} \rangle \le 2. \end{equation*}$$

Proof.

Let $x$ and $y$ be two distinct points in $X$. The point $m = (x+y)/2 = (m_1,\dots ,m_n)$ must lie in $Z_X$ and so $d_2(h,Z_X) \le \Vert h-m \Vert _2$. Note that for each $j$, $\bigl |m_j - \frac{1}{2}\bigr |$ is either $0$ or $\frac{1}{2}$, and, as $x$ and $y$ are distinct, the value 0 must occur for at least one value of $j$. Thus $\Vert h-m \Vert _2^2 \le (n-1)/4$ and so $\frac{1}{2} \le \frac{n}{2} - 2 d_2(h,Z_X)^2 \le \frac{n}{2}$. Together with 1, this then implies the result.

■

Remark 1.3.

Formula 1 is somewhat remarkable as the left-hand side only depends on the distances between the points, and not their positions. On the other hand, the quantity $d_2(h,Z_X)$ depends only on the linear relationship between the points of $X$, and does not appear to depend on their relative distances. This will be illustrated with some examples at the end of the paper.

Vital to the proof of 1 are the facts that the Hamming cube is of $1$-negative type, and that the natural embedding of $H_n$ into $\mathbb{R}^n$ is a so-called S-embedding. The definitions of these concepts are given in Section 2. Equation 1 is essentially a special case of a formula involving the $M$-constant $M(X)$ of the space $(X,d)$. The link between the $M$-constant and the radius of a particular sphere containing $X$ is due to Nickolas and Wolf 11, Section 3 (following earlier work of Alexander and Stolarsky 1), and it is this which provides the geometric meaning for many of the quantities considered. Working with $M(X)$ is advantageous as it is defined even when the matrix $D$ is not invertible, and this will allow us to consider arbitrary subsets of $H_n$. The relationship between $M(X)$ and $\langle D^{-1} \mathbf{1}, \mathbf{1} \rangle$ is developed in Section 3, and this provides sufficient information to prove the conjecture in 2. In the final sections we use the properties of S-embeddings to prove Theorem 1.1 and to give a geometric interpretation of the value of $\langle D^{-1} \mathbf{1}, \mathbf{1} \rangle$.

To simplify the statements of the results, we shall assume throughout that all metric spaces considered have at least two elements. (Without this restriction the statements are usually either false or meaningless.)

2. Negative type and $S$-embeddings

Definition 2.1.

Suppose that $(X,d)$ is a metric space and that $p \ge 0$. Then $(X,d)$ is of $p$-negative type if for each finite subset $\{x_1,\dots ,x_m\} \subseteq X$ and each set of scalars $\xi _1,\dots ,\xi _m \in \mathbb{R}$ with $\xi _1 + \dots + \xi _m = 0$,

$$\begin{equation} \sum _{i,j=1}^m d(x_i,x_j)^p \xi _i \xi _j \le 0. {\tag{2}} \end{equation}$$

In certain settings, spaces of $1$-negative type are also called quasihypermetric spaces (see for example 12) or spaces of generalized roundness $1$ (see 7).

A space is of strict $p$-negative type if 2 holds, with equality only in the trivial case where each $\xi _i$ is zero. (It is worth noting that a distinct but related concept, that of a strictly quasihypermetric space, appears in 10. For finite spaces, such as the ones considered in this paper, a space is of strict $1$-negative type if and only if it is strictly quasihypermetric.) It follows from the results of Wolf 16 and Sánchez 13 that a finite metric space of $1$-negative type is of strict $1$-negative type if and only if $D$ is non-singular and $\langle D^{-1}\mathbf{1}, \mathbf{1} \rangle \ne 0$.

By 15, Theorem 4.10 any subset of $\mathbb{R}^n$ with the $\ell ^1$ metric, and hence any subset of $H_n$, has $1$-negative type. Combining the results of Muragan 8, and Doust, Robertson, Stoneham and Weston 2 (see also Nickolas and Wolf 12) gives the following equivalences.

Theorem 2.2.

Suppose that $X = \{x_1,\dots ,x_m\} \subseteq H_n \subseteq \mathbb{R}^n$. Then the following are equivalent.

(1)

$X$ is of strict $1$-negative type.

(2)

$X$ is affinely independent (as a subset of $\mathbb{R}^n$).

(3)

$D$ is non-singular.

Proof.

The equivalence of (1) and (2) was shown in 8, Theorem 4.3. The equivalence of (2) and (3) was proven in 2, Corollary 2.5.

■

Clearly then, $H_n$ is of $1$-negative type, but not of strict $1$-negative type.

A celebrated theorem of Schoenberg 14 says that a metric space $(X,d)$ can be isometrically embedded in a Euclidean space if and only if it is of $2$-negative type. This gives the following.

Proposition 2.3.

Let $(X,d)$ be a finite metric space. Then the following are equivalent.

(1)

$(X,d)$ is of $1$-negative type (or quasihypermetric).

(2)

$(X,d^{1/2})$ embeds isometrically in a Euclidean space.

An embedding $\iota : X \to \mathbb{R}^n$ which maps $(X,d^{1/2})$ isometrically into $(\mathbb{R}^n,\Vert \cdot \Vert _2)$ is called an S-embedding. It is easy to check that the natural inclusion of $H_n$ in $\mathbb{R}^n$ is such an embedding, and hence so is the restriction to any subset of $H_n$.

3. The $M$-constant and maximal measures

The quantity $\langle D^{-1} \mathbf{1}, \mathbf{1} \rangle$ is closely related to the $M$-constant of the metric space, which we shall now introduce. Working with the $M$-constant is in fact usually preferable since it is defined even when the distance matrix $D$ is not invertible. For further background on the $M$-constant we refer the reader to 1 or 9.

Let $(X,d)$ be a compact metric space. For a signed Borel measure $\mu$ on $X$, let

$$\begin{equation*} I(\mu ) = \int _X \int _X d(x,y) \, d\mu (x) d\mu (y) \end{equation*}$$

and define $d_\mu : X \to \mathbb{R}$ by

$$\begin{equation*} d_\mu (x) = \int _X d(x,y) \, d\mu (y). \end{equation*}$$

Let $F_1$ denote the set of measure on $X$ of total mass one. The $M$-constant of $(X,d)$ is defined to be

$$\begin{equation*} M(X) = \sup _{\mu \in F_1} I(\mu ). \end{equation*}$$

If $I(\mu ) = M(X)$, then we say that $\mu$ is a maximal measure. It is clear that if $X$ is a metric subspace of $Y$ then $M(X) \le M(Y)$.

Suppose now that $X = \{x_1,\dots ,x_m\}$ is a finite metric space. In this case we shall write $\mu = (\alpha _1,\dots ,\alpha _m)$ to denote that $\mu (\{x_i\}) = \alpha _i$, $i=1,\dots ,m$. Then

$$\begin{equation*} I(\mu ) = \sum _{i,j=1}^m \alpha _i \alpha _j d(x_i,x_j) = \langle D \mu , \mu \rangle , \end{equation*}$$

and

$$\begin{equation*} d_\mu (x) = \sum _{i=1}^m \alpha _i d(x_i,x), \end{equation*}$$

although in most cases we shall retain the integral notation. We shall identify the measures of total mass one with the hyperplane of vectors whose elements sum to $1$. That is, $F_1 = \{v \in \mathbb{R}^m \; : \;\langle v, \mathbf{1} \rangle = 1\}$, and so $M(X) = \sup _{\mu \in F_1} \langle D \mu , \mu \rangle$. By considering $\mu = \frac{1}{m}\mathbf{1}$, we have $M(X) \ge \frac{1}{m^2} \langle D\mathbf{1}, \mathbf{1} \rangle \ge \frac{m-1}{m} d_0$, where $d_0$ is the smallest non-zero distance in $X$. In particular $M(X)$ is always strictly positive.

It is less clear that for a general compact metric space $M(X)$ should always be finite, and indeed this need not be the case (see 9, Theorem 3.1). Even if $M(X)$ is finite it may be that there are no maximal measures. Fortunately for subsets of the Hamming cube, these complications do not arise. Nickolas and Wolf 12, Theorem 4.7 showed that if $X$ is any $m$-point subset of $\mathbb{R}^n$ with the $\ell ^1$ metric then $M(X) \le \frac{m}{4} \operatorname {diam}(X)$.

We recall some important properties of these quantities.

Theorem 3.1.

Suppose that $(X,d)$ is a finite metric space of $1$-negative type and that $M(X) < \infty$.

(1)

A maximal measure exists.

(2)

If $\mu$ is a maximal measure, then $d_\mu (x) = M(X)$ for all $x \in X$.

(3)

If $\mu \in F_1$ and there is a constant $C$ such that $d_\mu (x) = C$ for all $x \in X$, then $\mu$ is maximal and so $M(X) = C$.

Proof.

(1) is 10, Theorem 4.11; (2) and (3) are from 10, Theorem 3.1.

■

Theorem 3.1 is closely related to the following result.

Theorem 3.2.

Suppose that $(X,d)$ is a finite metric space of $1$-negative type with distance matrix $D$. Then there exists $b \in \mathbb{R}^m$ such that $Db = \mathbf{1}$ and $\langle b, \mathbf{1} \rangle \ge 0$. Further

(1)

The value of $\langle b, \mathbf{1} \rangle$ is independent of $b$. That is, if $Db = Db' = \mathbf{1}$ then $\langle b, \mathbf{1} \rangle = \langle b', \mathbf{1} \rangle$.

(2)

$M(X) < \infty$ if and only if $\langle b, \mathbf{1} \rangle > 0$. In this case $\mu = \frac{1}{\langle b, \mathbf{1} \rangle } b$ is a maximal measure and$$\begin{equation*} M(X) = \frac{1}{\langle b, \mathbf{1} \rangle }. \end{equation*}$$

Proof.

The existence of $b$ is shown in 17, Theorem 4.2. The independence of the value of $\langle b, \mathbf{1} \rangle$ was noted in 17, Remark 4.4. Statement (2) is 17, Theorem 4.8.

■

Theorem 3.3.

Suppose that $(X,d)$ is a finite metric space of strict $1$-negative type with distance matrix $D$. Then $M(X) < \infty$ and

$$\begin{equation*} M(X) = \frac{1}{\langle D^{-1}\mathbf{1}, \mathbf{1} \rangle }. \end{equation*}$$

Proof.

By Theorem 2.2, $D$ must be invertible. Let $b = D^{-1}\mathbf{1}$. By 17, Theorem 4.3, $\langle b, \mathbf{1} \rangle > 0$ so by Theorem 3.2, $M(X) < \infty$ and $M(X) = \bigl (\langle D^{-1}\mathbf{1}, \mathbf{1} \rangle \bigr )^{-1}$.

■

Theorem 3.4.

$M(H_n) = \frac{n}{2}$.

Proof.

Due to the symmetry of the Hamming cube, the sum of the distances from any given point is independent of the point. Simple analysis shows that this sum is

$$\begin{equation*} \beta = \sum _{k=0}^n k \binom{n}{k} = n 2^{n-1} \end{equation*}$$

and so $D \mathbf{1} = \beta \mathbf{1}$. Let $b = \frac{1}{\beta } \mathbf{1}$, so $Db = \mathbf{1}$ and

$$\begin{equation*} \langle b, \mathbf{1} \rangle = \frac{1}{n 2^{n-1}} \langle \mathbf{1}, \mathbf{1} \rangle = \frac{2^n}{n 2^{n-1}} = \frac{2}{n}. \end{equation*}$$

By Theorem 3.2 then

$$\begin{equation*} M(H_n) = \frac{n}{2}. \end{equation*}$$ ■

Combining the above results gives a positive answer to the conjecture in 2.

Theorem 3.5.

Let $X$ be a subset of $H_n$. Then

(1)

$M(X) \le \frac{n}{2}$.

(2)

If $X$ is affinely independent, then $\langle D^{-1} \mathbf{1}, \mathbf{1} \rangle = \frac{1}{M(X)}$ and hence $\langle D^{-1} \mathbf{1}, \mathbf{1} \rangle \ge \frac{2}{n}$.

Proof.

(1)

As noted earlier if $X \subseteq H_n$ then $M(X) \le M(H_n)$, so the result follows immediately from Theorem 3.4.

(2)

This follows immediately from Theorem 2.2, Theorem 3.3 and (1).

■

The remainder of the paper is devoted to investigating the geometric interpretation of $M(X)$ in the context of subsets of the Hamming cube.

4. S-embeddings and spheres

There is a close connection between S-embeddings onto spheres and maximal measures. We begin with two lemmas.

Lemma 4.1.

Suppose that $u_1,\dots ,u_m \in \mathbb{R}^n$ and that $\alpha _1,\dots , \alpha _m \in \mathbb{R}$ satisfy $\sum _{i=1}^m \alpha _i = 1$. Then, for all $u \in \mathbb{R}^n$,

$$\begin{equation*} \sum _{i=1}^m \alpha _i \Vert u_i-u \Vert _2^2 = \bigl \Vert \sum _{i=1}^m \alpha _i u_i-u \bigr \Vert _2^2 + \frac{1}{2} \sum _{i,j=1}^m \alpha _i \alpha _j \Vert u_i-u_j \Vert _2^2. \end{equation*}$$

Proof.

With the notation of the lemma

$$\begin{align*} &\sum _{i=1}^m \alpha _i \Vert u_i-u \Vert _2^2\\ &\quad = \sum _{i=1}^m \alpha _i \Vert u_i \Vert _2^2 + \sum _{i=1}^m \alpha _i \Vert u \Vert _2^2 - 2 \sum _{i=1}^m \alpha _i \langle u_i, u \rangle \\ &\quad = \Vert u \Vert _2^2 - 2 \langle \sum _{i=1}^m \alpha _i u_i, u \rangle + \bigl \Vert \sum _{i=1}^m \alpha _i u_i \bigr \Vert _2^2 - \bigl \Vert \sum _{i=1}^m \alpha _i u_i \bigr \Vert _2^2 + \sum _{i=1}^m \alpha _i \Vert u_i \Vert _2^2 \\ &\quad = \bigl \Vert \sum _{i=1}^m \alpha _i u_i - u \bigr \Vert _2^2 - \bigl \Vert \sum _{i=1}^m \alpha _i u_i \bigr \Vert _2^2 + \sum _{i=1}^m \alpha _i \Vert u_i \Vert _2^2 \\ &\quad = \bigl \Vert \sum _{i=1}^m \alpha _i u_i - u \bigr \Vert _2^2 - \sum _{i,j=1}^m \alpha _i \alpha _j \langle u_i, u_j \rangle + \sum _{i=1}^m \alpha _i \Vert u_i \Vert _2^2 \\ &\quad = \bigl \Vert \sum _{i=1}^m \alpha _i u_i - u \bigr \Vert _2^2 + \sum _{i=1}^m \alpha _i \Vert u_i \Vert _2^2 - \frac{1}{2} \sum _{i,j=1}^m \alpha _i \alpha _j \left(\Vert u_i \Vert _2^2 + \Vert u_j \Vert _2^2 - \Vert u_i-u_j \Vert _2^2 \right) \\ &\quad = \bigl \Vert \sum _{i=1}^m \alpha _i u_i - u \bigr \Vert _2^2 + \sum _{i=1}^m \alpha _i \Vert u_i \Vert _2^2 \\ & \qquad - \frac{1}{2} \sum _{j=1}^m \alpha _j \sum _{i=1}^m \alpha _i \Vert u_i \Vert _2^2 - \frac{1}{2} \sum _{i=1}^m \alpha _i \sum _{j=1}^m \alpha _j \Vert u_j \Vert _2^2 + \frac{1}{2} \sum _{i,j=1}^m \alpha _i \alpha _j \Vert u_i-u_j \Vert _2^2 \\ &\quad = \bigl \Vert \sum _{i=1}^m \alpha _i u_i-u \bigr \Vert _2^2 + \frac{1}{2} \sum _{i,j=1}^m \alpha _i \alpha _j \Vert u_i-u_j \Vert _2^2. \end{align*}$$ ■

Lemma 4.2.

Let $(X,d)$, $X = \{x_1,\dots ,x_m\}$ be a finite metric space of $1$-negative type, and let $\iota : (X,d^{1/2}) \to (\mathbb{R}^n,\Vert \cdot \Vert _2)$ be an S-embedding of $X$. Suppose that $\mu = (\alpha _1,\dots ,\alpha _m) \in F_1$. Then, for all $x \in X$,

$$\begin{equation*} d_\mu (x) = \bigl \Vert \sum _{i=1}^m \alpha _i \iota (x_i)-\iota (x) \bigr \Vert _2^2 + \frac{I(\mu )}{2}. \end{equation*}$$

Proof.

Using Lemma 4.1

$$\begin{align*} d_\mu (x) & = \sum _{i=1}^m \alpha _i \Vert \iota (x_i) - \iota (x) \Vert _2^2 \\ &= \bigl \Vert \sum _{i=1}^m \alpha _i \iota (x_i)-\iota (x) \bigr \Vert _2^2 + \frac{1}{2} \sum _{i,j=1}^m \alpha _i \alpha _j \Vert \iota (x_i)-\iota (x_j) \Vert _2^2 \\ &= \bigl \Vert \sum _{i=1}^m \alpha _i \iota (x_i)-\iota (x) \bigr \Vert _2^2 + \frac{1}{2} \sum _{i,j=1}^m \alpha _i \alpha _j d(x_i,x_j) \\ &= \bigl \Vert \sum _{i=1}^m \alpha _i \iota (x_i)-\iota (x) \bigr \Vert _2^2 + \frac{I(\mu )}{2}. \end{align*}$$ ■

The content of the following result can be found in Theorem 3.2 of 11. We include a short proof for completeness.

Theorem 4.3.

Let $(X,d)$, $X = \{x_1,\dots ,x_m\}$ be a finite metric space of $1$-negative type, and let $\iota : (X,d^{1/2}) \to (\mathbb{R}^n,\Vert \cdot \Vert _2)$ be an S-embedding of $X$. Then

(1)

If $\mu = (\alpha _1,\dots ,\alpha _m)$ is a maximal measure on $X$, then $\iota (X)$ lies on a sphere in $\mathbb{R}^n$ with centre $\sum _{i=1}^m \alpha _i \iota (x_i)$ and radius$$\begin{equation*} r = \sqrt {\frac{M(X)}{2}}. \end{equation*}$$

(2)

Suppose that $\iota (X)$ lies on a sphere of radius $r$ with centre $c$ which lies inside the affine hull of $\{\iota (x_1),\dots ,\iota (x_m)\}$, say $c = \sum _{i=1}^m \beta _i \iota (x_i)$ with $\sum _{i=1}^m \beta _i = 1$. Then $\mu = (\beta _1,\dots ,\beta _m)$ is a maximal measure on $X$ and$$\begin{equation*} r = \sqrt {\frac{M(X)}{2}}. \end{equation*}$$

Proof.

(1)

Let $\mu = (\alpha _1,\dots ,\alpha _m) \in F_1$ be a maximal measure on $X$. Fix then $x \in X$. By Theorem 3.1 and Lemma 4.2$$\begin{equation*} M(X) = d_\mu (x) = \bigl \Vert \sum _{i=1}^m \alpha _i \iota (x_i) - \iota (x) \bigr \Vert _2^2 + \frac{I(\mu )}{2}. \end{equation*}$$

Since $\mu$ is maximal $I(\mu ) = M(X)$ and hence$$\begin{equation*} \bigl \Vert \sum _{i=1}^m \alpha _i \iota (x_i) - \iota (x) \bigr \Vert _2^2 = \frac{M(X)}{2} \end{equation*}$$

which proves (1).

(2)

Let $c$ be as in the statement of the theorem and suppose that $x \in X$, so that $\Vert c - \iota (x) \Vert _2^2 = r^2$. Let $\mu = (\beta _1,\dots ,\beta _m)$. By Lemma 4.2$$\begin{equation*} d_\mu (x) = \Vert c - \iota (x) \Vert _2^2 + \frac{I(\mu )}{2} = r^2 + \frac{I(\mu )}{2}. \end{equation*}$$

Since $d_\mu (x)$ is independent of $x$, from Theorem 3.1 we can conclude that $\mu$ is maximal on $X$ and that$$\begin{equation*} M(X) = r^2 + \frac{I(\mu )}{2} \end{equation*}$$

and hence that$$\begin{equation*} r^2 = \frac{M(X)}{2}. \end{equation*}$$

■

Suppose that $B = \{v_1,\dots ,v_k\}$ is a basis for a subspace $Z \subseteq \mathbb{R}^n$. Then there is a unique point $c \in Z$ which is equidistant from all the elements of $B$ and the origin. Indeed a small calculation shows that if $A$ is the $n \times k$ matrix whose $i$th column is $v_i$, then

$$\begin{equation} c = \sum _{i=1}^k \gamma _i v_i \qquad \text{where} \qquad \begin{pmatrix} \gamma _1 \\ \vdots \\ \gamma _k \end{pmatrix} = \frac{1}{2} (A^TA)^{-1} \begin{pmatrix} \Vert v_1 \Vert _2^2 \\ \vdots \\ \Vert v_k \Vert _2^2 \end{pmatrix}. {\tag{3}} \end{equation}$$

This implies the following.

Lemma 4.4.

Suppose that $X = \{x_1,\dots ,x_m\}$ is a finite subset of $\mathbb{R}^n$ and let $Z_X$ be the smallest affine subspace of $\mathbb{R}^n$ containing $X$. Then there is at most one sphere in $\mathbb{R}^n$ whose centre lies in $Z_X$ and which contains the points of $X$.

5. The $M$-constant for subsets of the Hamming cube

Suppose that $X = \{x_1,\dots ,x_m\} \subseteq H_n$. Let $Z_X$ denote the smallest affine subspace of $\mathbb{R}^n$ containing the points $\{x_1,\dots ,x_m\}$. We shall use $d_2(x,Z_X)$ to denote the Euclidean distance from a point $x \in \mathbb{R}^n$ to an affine subspace $Z_X$. Let $h = \bigl (\frac{1}{2},\dots ,\frac{1}{2}\bigr ) \in \mathbb{R}^n$.

Theorem 5.1.

Suppose that $X = \{x_1,\dots ,x_m\} \subseteq H_n$. Then

$$\begin{equation} M(X) = \frac{n}{2} - 2 d_2(h,Z_X)^2. {\tag{4}} \end{equation}$$

Proof.

Let $\iota : (H_n,d_1^{1/2}) \to (\mathbb{R}^n,\Vert \cdot \Vert _2)$ be the natural inclusion map of $H_n$ in $\mathbb{R}^n$. As noted in Section 2, this map is necessarily an S-embedding.

Since $\Vert x-h \Vert _2^2 = \frac{n}{4}$ for all $x \in H_n$, we have that $X = \iota (X)$ lies on the sphere $S \subseteq \mathbb{R}^n$ of radius $r = \sqrt {n}/2$ centred at $h$. Let $P$ be the orthogonal projection from $\mathbb{R}^n$ onto $Z_X$ and let $c_X = Ph$. If $u \in \iota (X) \subseteq Z_X$ then, by Pythagoras,

$$\begin{equation*} \Vert c_X-u \Vert _2^2 = \Vert h - u \Vert _2^2 - \Vert h - c_X \Vert _2^2 = \frac{n}{4} - d_2(h,Z_X)^2. \end{equation*}$$

That is, all points in $\iota (X)$ lie on a sphere $S_X$ with centre $c_X \in Z_X$ and radius $r$ with $r^2 = \frac{n}{4} - d_2(h,Z_X)^2$. (Note that by Lemma 4.4, there is only one such sphere.)

But by Theorem 4.3(2), the radius of such this sphere must also satisfy

$$\begin{equation*} r^2 = \frac{n}{4} - d_2(h,Z_X)^2 = \frac{M(X)}{2} \end{equation*}$$

which gives the result.

■

Equation 4 immediately gives the following characterization of when the maximum value of $M(X)$ is achieved.

Corollary 5.2.

$M(X)$ achieves its maximum value of $\frac{n}{2}$ if and only if $h$ lies in $Z_X$.

Combining Theorem 5.1 and Theorem 3.5 gives Theorem 1.1 stated in Section 1.

Following the proof of 11, Theorem 3.2, an alternative but less geometrically illuminating verification of Theorem 5.1 can be given by noting that for $\mu = (\alpha _1,\dots ,\alpha _m) \in F_1$, and $\{x_i\}_{i=1}^m \subseteq H_n$,

$$\begin{align*} I(\mu ) &=\sum _{i,j = 1}^m \alpha _i \alpha _j \Vert x_i - x_j \Vert _1 = \sum _{i,j = 1}^m \alpha _i \alpha _j \Vert x_i - x_j \Vert _2^2 \\ &= \sum _{i,j = 1}^m \alpha _i \alpha _j \Vert (x_i-h) - (x_j-h) \Vert _2^2 \\ &= \sum _{i,j = 1}^m \alpha _i \alpha _j \Vert (x_i-h) \Vert _2^2 + \sum _{i,j = 1}^m \alpha _i \alpha _j \Vert (x_j-h) \Vert _2^2 - 2 \sum _{i,j = 1}^m \alpha _i \alpha _j \langle x_i-h, x_j-h \rangle \\ &= \frac{n}{2} - 2 \bigl \Vert \sum _{i = 1}^m \alpha _i (x_i - h) \bigr \Vert _2^2 \\ & = \frac{n}{2} - 2 \bigl \Vert \sum _{i = 1}^m \alpha _i x_i - h \bigr \Vert _2^2. \end{align*}$$

Maximizing $I(\mu )$ then gives the result.

One consequence of Theorem 5.1 is that the value of $M(X)$ for $X \subseteq H_n$ is determined by the $M$-constant of any maximal affinely independent subset $Y$ of $X$. (Since, by Theorem 2.2, a maximal affinely independent subset of $X$ is also a maximal subset of strict $1$-negative type, this can also be deduced from Theorem 2.7 of 12.) Such a set $Y$ may be much smaller than $X$, and furthermore the value of $M(Y)$ may be calculated algorithmically rather than by an optimization process. Finding a suitable affinely independent subset can be easily done using Gaussian elimination. The distance matrix for $Y$ is then invertible, and Theorem 3.5 implies that $M(X) = M(Y) = (\langle D_Y^{-1}\mathbf{1}, \mathbf{1} \rangle )^{-1}$.

Alternatively, if $Y = \{y_0,\dots ,y_m\}$ and $v_i = y_i - y_0$, $i=1,\dots , m$, then one may use 3 to compute the centre $c$ of the sphere in $\operatorname {span}(v_1,\dots ,v_m)$ containing the points $\mathbf{0},v_1,\dots ,v_m$. Then $M(X) = M(Y) = 2 \Vert c \Vert _2^2$. In the case that $X$ is affinely independent, one may therefore use Theorem 1.1, the proof of Theorem 5.1, and Pythagoras to see that $\langle D^{-1}\mathbf{1}, \mathbf{1} \rangle$ is equal to $(2r^2)^{-1}$ where $r$ is the radius of the smallest sphere containing all the points in $X$.

We finish with two small examples which illustrate Remark 1.3 concerning the lack of an obvious relationship between the distance matrix $D$ and the subspace $Z_X$ which appear on the two sides of Equation 1.

Example 5.3.

Let $X_1 = \{(0,0,0),(1,1,1)\}$ and let $X_2 = X_1 \cup \{(1,0,0)\}$. In this case $Z_{X_1}$ is different to $Z_{X_2}$. The point $h$ lies in both subspaces and hence $M(X_1) = M(X_2) = \frac{3}{2}$. Of course the distance matrices are quite different with

$$\begin{equation*} D_{X_1}^{-1} = \begin{pmatrix} 0 & \tfrac{1}{3} \\ \tfrac{1}{3} & 0 \end{pmatrix}, \qquad D_{X_2}^{-1} = \begin{pmatrix} -\tfrac{1}{3} & \tfrac{1}{6} & \tfrac{1}{2} \\ \tfrac{1}{6} & -\tfrac{1}{12} & \tfrac{1}{4} \\ \tfrac{1}{2} & \tfrac{1}{4} & -\tfrac{3}{4} \end{pmatrix}, \end{equation*}$$

but the sum of the entries of each matrix inverse is $\frac{2}{3}$.

Example 5.4.

Let $X_1 = \{(0,0,0),(1,0,0),(0,1,0)\}$ and let $X_2 = X_1 \cup \{(1,1,0)\}$. Then $Z_{X_1} = Z_{X_2}$ and so by Theorem 5.1 we must have $M(X_1) = M(X_2)$. Here $X_1$ is affinely independent and $\langle D_{X_1}^{-1} \mathbf{1}, \mathbf{1} \rangle = M(X_1)^{-1} = 1$. However $X_2$ is not affinely independent and $D_{X_2}$ is not invertible. (Using Lagrange multipliers, one can confirm, directly from the definition, that $M(X_2) = 1$. Alternatively, one may use Theorem 4.3 since $X_2$ certainly lies in a sphere with centre in $Z_{X_2}$ and radius $1/\sqrt {2}$.)