Let
$A \in \mathbb {R}^{n \times n}$
be a real symmetric matrix. Given a vector
$v = (v_1, \ldots , v_n) \in \mathbb {R}^n \backslash \{ 0 \}$
, we can associate a Euclidean distance matrix (EDM)
$\Delta = \Delta ^v$
(of embedding dimension one) by declaring the entries of
$\Delta $
to be
$\Delta _{ij} = (v_i - v_j)^2$
. Let
$(\cdot , \cdot )_{\text {F}}$
denote the Frobenius pairing on
$\mathbb {R}^{n \times n}$
given by
$(A,B)_{\text {F}} : = \text {tr}(A B^t)$
. If
$\mathbb {EDM}_n$
denotes the cone of Euclidean distance matrices in
$\mathbb {R}^{n \times n}$
, we denote by
$\mathbb {EDM}_n^{\ast }$
the cone dual to
$\mathbb {EDM}$
, namely,
$$ \begin{align*}\mathbb{EDM}_n^{\ast} : = \{ A \in \mathbb{R}^{n \times n} : (A,B)_{\text{F}} \geq 0 \mbox{ for all } B \in \mathbb{EDM}_n \}.\end{align*} $$
The purpose of this note is to prove the following result.
Theorem 1. Let
$A \in \mathbb {R}^{n \times n}$
be a real symmetric matrix with eigenvalues
$\lambda _1 \geq \lambda _2 \geq \cdots \geq \lambda _n$
. Then
$A \in \mathbb {EDM}_n^{\ast }$
if and only if
$$ \begin{align*} \lambda_1 \geq \sum_{k=2}^n r_k \lambda_k \end{align*} $$
for all Perron weights
$0 \leq r_k \leq 1$
.
Remark 2. Let us explain the meaning of the nonstandard terminology Perron weights. A symmetric matrix
$\Sigma \in \mathbb {R}^{n \times n}$
is said to be a Euclidean distance matrix if there is a vector
$v = (v_1, \ldots , v_n) \in \mathbb {R}^n$
such that
$\Sigma _{ij} = (v_i - v_j)^2$
. The well-known Schoenberg criterion [Reference Schoenberg3] states that a symmetric hollow matrix
$\Sigma $
(that is, a matrix with nonzero entries on its diagonal) is a Euclidean distance matrix if and only if it is negative semi-definite on the hyperplane
$H = \{ x \in \mathbb {R} : x^t \textbf {e} = 0 \}$
, where
$\textbf {e} = (1, \ldots , 1)^t$
. Of course, a Euclidean distance matrix is, in particular, a nonnegative matrix in the sense that each entry of the matrix is a nonnegative real number. As a consequence, the Perron–Frobenius theorem asserts that the largest eigenvalue of the Euclidean distance matrix
$\Sigma $
is positive and occurs with eigenvector in the nonnegative orthant
$\mathbb {R}_{\geq 0}^n$
. This eigenvalue is often called the Perron root of
$\Sigma $
, denoted
$r = r(\Sigma )$
. Therefore, if
$\delta _1 \geq \delta _2 \geq \cdots \geq \delta _n$
denote the eigenvalues of a nontrivial Euclidean distance matrix
$\Sigma $
(that is, a Euclidean distance matrix with
$\delta _1> 0$
), then
$\delta _1> 0$
and
$\delta _2, \ldots , \delta _n \leq 0$
. The Perron weights are then defined by
$$ \begin{align*}r_k : = - \frac{\delta_k}{\delta_1} \in [0,1] \quad\mbox{for } 2 \leq k \leq n.\end{align*} $$
Remark 3. Theorem 1 can be described in terms of zonahedra. Given a set of vectors
$w_1, \ldots , w_k \in \mathbb {R}^d$
, the zonahedron generated by
$w_1, \ldots , w_k$
is the Minkowski sum of line segments connecting each of the points. That is, for
$\vartheta _1,\ldots , \vartheta _k \in [0,1]$
, the zonahedron generated by
$w_1, \ldots , w_k$
is the set
$$ \begin{align*}Z(w_1, \ldots, w_k) : = \bigg \{ \sum_{i=1}^k \vartheta_i w_i : \vartheta_i \in [0,1] \bigg \}.\end{align*} $$
The dual EDM cone, therefore, consists of those symmetric matrices whose largest eigenvalue lies on the right of the zonahedron formed by the remaining eigenvalues.
Proof of Theorem 1
Let
$\lambda _1 \geq \lambda _2 \geq \cdots \geq \lambda _n$
denote the eigenvalues of the symmetric matrix
$A \in \mathbb {R}^{n \times n}$
and let
$\delta _1 \geq \delta _2 \geq \cdots \geq \delta _n$
denote the eigenvalues of a Euclidean distance matrix
$\Delta $
. If
$A = U^t \text {diag}(\lambda ) U$
and
$\Delta = V^t \text {diag}(\delta ) V$
denote the eigenvalue decompositions for A and
$\Delta $
,
$$ \begin{align*} \text{tr}(A \Delta) \ = \ \text{tr}(U^t \text{diag}(\lambda) U V^t \text{diag}(\delta) V) &= \text{tr}(VU^t \text{diag}(\lambda) UV^t \text{diag}(\delta) )\\ &= \text{tr}(Q^t \text{diag}(\lambda) Q \text{diag}(\delta)) \\ &= \sum_{i,j} \lambda_i \delta_j Q_{ij}^2, \end{align*} $$
where
$Q = UV^t$
is orthogonal. The Hadamard square (that is, the matrix
$Q \circ Q$
with entries
$Q_{ij}^2$
) of an orthogonal matrix is doubly stochastic (see, for example, [Reference Heinz2]). The class of
$n \times n$
doubly stochastic matrices forms a convex polytope, the Birkhoff polytope
$\mathcal {B}^n$
. The minimum of
$\text {tr}(A\Delta )$
is given by
$$ \begin{align*} \min_{S \in \mathcal{B}^n} \sum_{i,j=1}^n \lambda_i \delta_j S_{ij}. \end{align*} $$
This function is linear in S and, therefore, achieves its minimum on the boundary of the Birkhoff polytope. The Birkhoff–von Neumann theorem tells us that
$\mathcal {B}^n$
is the convex hull of the set of permutation matrices and, moreover, the vertices of
$\mathcal {B}^n$
are precisely the permutation matrices. Hence,
$$ \begin{align*} \min_{S \in \mathcal{B}^n} \sum_{i,j=1}^n \lambda_i \delta_j S_{ij} = \min_{\sigma \in S_n} \sum_{i=1}^n \lambda_i \delta_{\sigma(i)}, \end{align*} $$
where
$S_n$
denotes the symmetric group on n letters. An elementary argument (by induction, for instance) shows that
$$ \begin{align*} \min_{\sigma \in S_n} \sum_{i=1}^n \lambda_i \delta_{\sigma(i)} = \sum_{i=1}^n \lambda_i \delta_i. \end{align*} $$
From the discussion in Remark 2, this completes the proof.
Applications to graph theory. In [Reference Broder1], I addressed the problem of when a weighted finite graph (with possibly negative weights) has nonnegative Dirichlet energy. I showed that the Dirichlet energy was nonnegative if and only if the matrix describing the weighting was an element of the dual EDM cone. If the matrix is symmetric, the graph is said to be directed. The main theorem of this note has the following corollary.
Corollary 4. Let
$(G,A)$
be a directed weighted graph. Let
$V(G) = \{ x_1, \ldots , x_n \}$
denote the vertex set of G. The Dirichlet energy
$$ \begin{align*}\mathcal{E}(f) : = \sum_{i,j=1}^n A_{ij}(f(x_i) - f(x_j) )^2\end{align*} $$
is nonnegative for all graph functions
$f : V(G) \to \mathbb {R}$
if and only if the largest eigenvalue of A dominates the Perron-weighted average of the remaining eigenvalues.
Acknowledgement
I would like to thank my advisors Ben Andrews and Gang Tian for their constant support and encouragement.
