betaFeedback

WorksMathematics

Conditionally Euclidean distance matrices

Abstract

We introduce a new class of matrices called conditional Euclidean distance matrices in this paper. These matrices are a generalisation of Euclidean distance matrices. We develop the theory of conditional Euclidean distance matrices and show that these matrices represent the squared Lorentzian distance between points of a Minkowski space. We also highlight the connection of conditional Euclidean distance matrices with the representation of hierarchical data in machine learning and the theory of general relativity in physics.

Introduction

Let Sn\mathcal{S}^{n} denote the set of all n×nn \times n symmetric matrices. A hollow symmetric matrix is a symmetric matrix with zero diagonal elements. Let Shn\mathcal{S}_{h}^{n} be the set of hollow symmetric matrices of order nn. By a centered symmetric matrix we mean a symmetric matrix with zero row (and hence column) sums. Let Sen\mathcal{S}_{e}^{n} be the set of all centered symmetric matrices of order nn given by:

Sen:={F∈Sn:Fe=0}.\mathcal{S}_{e}^{n} := \{F \in\mathcal{S}^{n}: F e = 0\}.

As shown by Critchley [1], Theorem 2.2, and Johnson and Tarazaga [2], pp.380, there is a one-to-one correspondence between Shn\mathcal{S}_{h}^{n} and Sen\mathcal{S}_{e}^{n}. The following two linear maps T\mathcal{T} and K\mathcal{K} define this one-to-one correspondence:

T:Shn→Sen:D↦−12(I−eeTn)D(I−eeTn),\mathcal{T} : \mathcal{S}_{h}^{n} \to\mathcal{S}_{e}^{n} : D \mapsto-\frac{1}{2}\left(I-\frac{ee^{T}}{n}\right)D\left(I-\frac{ee^{T}}{n}\right),
K:Sen→Shn:F↦Diag⁡(F)E+EDiag⁡(F)T−2F.\mathcal{K} : \mathcal{S}_{e}^{n} \to\mathcal{S}_{h}^{n} : F \mapsto\operatorname{Diag}(F)E + E\operatorname{Diag}(F)^{T} - 2F.

Let Dn\mathcal{D}^{n} denote the set of n×nn \times n Euclidean distance matrices (see (1)) and let

Ωn(e):={F∈Sen:F is positive semidefinite}.\Omega_{n}(e) := \{F \in\mathcal{S}_{e}^{n}: F \text{ is positive semidefinite}\}.

It is of interest to note that both Dn\mathcal{D}^{n} and Ωn(e)\Omega_{n}(e) forms convex cones in Shn\mathcal{S}_{h}^{n} and Sen\mathcal{S}_{e}^{n}, respectively. It is well known that the mappings T∣Dn\mathcal{T}|_{\mathcal{D}^{n}} and K∣Ωn(e)\mathcal{K}|_{\Omega_{n}(e)} are mutually inverse. Consider the following subset of Sen\mathcal{S}_{e}^{n}:

Ωn−(e):={F∈Sen:F has at most one negative eigenvalue}.\Omega_{n}^{-}(e) := \{F \in\mathcal{S}_{e}^{n}: F \text{ has at most one negative eigenvalue}\}.

Clearly Ωn(e)⊂Ωn−(e)\Omega_{n}(e) \subset\Omega_{n}^{-}(e). Further, Ωn−(e)\Omega_{n}^{-}(e) forms a cone in Sen\mathcal{S}_{e}^{n}. In this paper we are interested in identifying and studying the image of Ωn−(e)\Omega_{n}^{-}(e) under the linear map K\mathcal{K}.

Historical background

The motivation for work on hollow symmetric matrices with non-negative off diagonal entries takes its root from Euclidean geometry and originated in the classical paper [3] of Schoenberg. Euclidean distance matrices were first studied formally in the work [4], [5] and [6] of Gower. Euclidean distance matrices were characterized into their modern definition by Hayden and Wells in [7].

An n×nn \times n hollow symmetric matrix DD is called an Euclidean distance matrix (EDM) if for some positive integer rr, there exist points p1,…,pn∈Rrp^{1}, \ldots, p^{n} \in\mathbb{R}^{r} such that

dij=∥pi−pj∥2(1)d_{ij} = \lVert p^{i} - p^{j} \rVert^{2} \tag*{(1)}

for each i,j∈{1,…,n}i,j \in\{1,\ldots,n\}. Several characterizations and results on EDMs can be found in the works of Tarazaga et al. [8] and [9], Hayden et al. [10], Tarazaga [11], Alfakih [12], Bénasséni [13], Kurata et al. [14], [15], [16] and [17], Balaji et al. [18] and many more references within these articles. Kurata and Bapat in [19] considered the class of all hollow symmetric matrices and extended some of the properties of EDMs to this class. Their work motivates us to look at a subset of the class of hollow symmetric matrices that properly contains the class of EDMs, but most of the results on EDMs can be naturally generalised to this new class.

Notations and preliminaries

In this section we introduce some notations and preliminaries relevant to this work. We omit including the notations and preliminaries defined in the previous sections to avoid redundancy. Further some minimally used notations will be introduced as and when needed to abstain inundating the reader.

The notations ee and 0\mathbf{0} are used to represent the vectors of relevant order with all entries 11 and 00, respectively. The identity and all ones matrices are represented by II and EE, respectively. The transpose of a vector xx is denoted by xTx^{T}, and we use ATA^{T} to represent the transpose of a matrix. Two vectors xx and yy are orthogonal if xTy=0x^{T}y=0. For any vector xx and subspace WW, x⊥x^{\perp} and W⊥W^{\perp} denote the orthogonal complement of span⁡{x}\operatorname{span}\{x\} and WW, respectively. The notation A=(aij)A=(a_{ij}) is used to represent a matrix with its ijthij^{\mathrm{th}} entry as aija_{ij}. The rank of a matrix AA is denoted by rank⁡(A)\operatorname{rank}(A). For a matrix AA, Diag⁡(A)\operatorname{Diag}(A) represent the diagonal matrix formed by the diagonal entries of AA. The matrix A†A^{\dagger} is the Moore-Penrose of AA.

A matrix A∈SnA \in\mathcal{S}^{n} is called positive semidefinite if and only if xTAx≥0x^{T}Ax \geq0 for all x∈Rnx \in\mathbb{R}^{n}. A famous characterization for positive semidefinite matrices is that a symmetric matrix is positive semidefinite if and only if all of its eigenvalues are non-negative. A matrix AA is said to be positive (negative) semidefinite on a subspace WW, if xTAx≥0x^{T}Ax \geq0 (xTAx≤0x^{T}Ax \leq0) for any x∈Wx \in W.

Outline of the paper

In section 2, we introduce the class of conditional Euclidean matrices and explore its characterisation from various perspectives. We also study properties of the centered symmetric matrix associated with a coEDM in section 2. Next, the concept of Gale space is generalised for a hollow symmetric matrix in section 3 and we obtain similar results about these spaces as are known for EDMs. In section 4, we discuss some special properties of non-negative coEDMs. We conclude this paper by showing a connection of coEDMs with Minowski space, machine learning and in the theory of general relativity in section 5.

Conditional Euclidean distance matrix

For the rest of the paper, we use JJ to denote the matrix I−1nEI-\frac{1}{n}E. Suppose DD is a hollow-symmetric matrix and let F=−12JDJF=-\frac{1}{2}JDJ. It is well-known from [3] that DD is an EDM if and only if FF is a positive semidefinite matrix. We are interested in hollow-symmetric matrices for which FF is not positive semidefinite. A matrix that is not positive semidefinite has at least one negative eigenvalue. We recall

Ωn−(e)={F∈Sen:F has at most one negative eigenvalue},\Omega_n^{-}(e)=\{F\in\mathcal{S}_e^n:F\text{ has at most one negative eigenvalue}\},

and define the following.

Definition 1. A hollow symmetric matrix DD is a conditional Euclidean distance matrix (coEDM) if and only D∈K(Ωn−(e))D\in\mathcal{K}(\Omega_n^{-}(e)). We denote the set of all n×nn\times n coEDMs by Cn\mathcal{C}^n.

Since the image of a cone under a linear map is a cone, we conclude that the set of all n×nn\times n coEDMs forms a cone in Shn\mathcal{S}_h^n. Let

Ωn(1)(e):={F∈Sen∣F has exactly one negative eigenvalue}.\Omega_n^{(1)}(e):=\{F\in\mathcal{S}_e^n\mid F\text{ has exactly one negative eigenvalue}\}.

Then it is clear that the set Ωn−(e)\Omega_n^{-}(e) can be decomposed as the following disjoint union

Ωn−(e)=Ωn(e)∪Ωn(1)(e).\Omega_n^{-}(e)=\Omega_n(e)\cup\Omega_n^{(1)}(e).

Since K(Ωn−(e))=Cn\mathcal{K}(\Omega_n^{-}(e))=\mathcal{C}^n, we now have

Cn=K(Ωn−(e))=K(Ωn(e))∪K(Ωn(1)(e)).\mathcal{C}^n=\mathcal{K}(\Omega_n^{-}(e))=\mathcal{K}(\Omega_n(e))\cup\mathcal{K}(\Omega_n^{(1)}(e)).

Since the set Dn\mathcal{D}^n of n×nn\times n EDMs is given by K(Ωn(e))\mathcal{K}(\Omega_n(e)), we have

Cn=Dn∪K(Ωn(1)(e)).(2)\mathcal{C}^n=\mathcal{D}^n\cup\mathcal{K}(\Omega_n^{(1)}(e)). \tag*{(2)}

Thus, every EDM is a coEDM. However, the converse is not true. The following example shows such an instance.

Example 1. Consider the matrix

D=14[0−198−190418410].D=\frac{1}{4}\begin{bmatrix}0 & -19 & 8 \\ -19 & 0 & 41 \\ 8 & 41 & 0\end{bmatrix}.

Clearly, DD is not an EDM due to having negative entries. But it is a coEDM since the matrix DD can be written as D=K(F)D=\mathcal{K}(F), where

F=−12JDJ=14[−78−184−12−1−1213]F=-\frac{1}{2}JDJ=\frac{1}{4}\begin{bmatrix}-7 & 8 & -1 \\ 8 & 4 & -12 \\ -1 & -12 & 13\end{bmatrix}

is a centered symmetric matrix having exactly one negative eigenvalue.

In the next section, we study Cn\mathcal{C}^n, the set of all coEDMs in detail and provide some characterizations.

Characterization of coEDMs

Suppose DD is a hollow-symmetric matrix. From the results of Critchley [1] and Johnson [2], there exists a centered symmetric matrix FF such that

D=K(F)=EDiag⁡(F)+Diag⁡(F)E−2F.D=\mathcal{K}(F)=E\operatorname{Diag}(F)+\operatorname{Diag}(F)E-2F.

Since FF has zero row sums, it is easy to see that

F=−12(I−esT)D(I−seT),(3)F=-\frac{1}{2}(I-es^T)D(I-se^T), \tag*{(3)}

where s=1nes=\frac{1}{n}e. This shows that if D=K(F)D=\mathcal{K}(F), then FF is uniquely determined. Thus, if DD is a coEDM, then by Theorem 1, F∈Ωn(e)F\in\Omega_n(e). Since FF has at most one negative eigenvalue, there exists ω\omega such that FF is positive semidefinite on ω⊥\omega^\perp. Since FF is a zero row sum matrix, we can assume that ωTe=0\omega^T e=0. Using the above discussion, we obtain the following characterization of coEDMs.

Theorem 1. A hollow symmetric matrix DD is a conditional Euclidean distance matrix (coEDM) if and only if the matrix F=−12JDJF=-\frac{1}{2}JDJ is positive semidefinite on ω⊥\omega^\perp for some ω∈e⊥\omega\in e^\perp.

Gower in [5] showed that DD is a Euclidean distance matrix if and only if (3) is positive semidefinite for any ss with sTe=1s^T e=1 and sTD≠0s^T D\ne0. Later, Gower in [6] showed that the condition sTD≠0s^T D\ne0 is superfluous. Thus DD is a Euclidean distance matrix if and only if (3) is positive semidefinite for any ss with sTe=1s^T e=1. The next result provides a generalisation of Gower’s result for coEDMs.

Theorem 2. Let DD be a hollow symmetric n×nn \times n matrix. Then DD is a conditionally Euclidean distance matrix if and only if there exist ω∈e⊥\omega\in e^{\perp} such that the matrix

−12(I−esT)D(I−seT)-\frac{1}{2}(I-es^{T})D(I-se^{T})

is positive semidefinite on ω⊥\omega^{\perp} for any ss such that sTe=1s^{T}e=1, and sTω=0s^{T}\omega=0.

Proof. Suppose ω∈e⊥\omega\in e^{\perp} such that

L=−12(I−esT)D(I−seT)L=-\frac{1}{2}(I-es^{T})D(I-se^{T})

is positive semidefinite on ω⊥\omega^{\perp} for any ss such that sTe=1s^{T}e=1, and sTω=0s^{T}\omega=0. Since 1neTe=1\frac{1}{n}e^{T}e=1, 1neTω=0\frac{1}{n}e^{T}\omega=0, −12JDJ-\frac{1}{2}JDJ is positive semidefinite on ω⊥\omega^{\perp} and hence DD is a coEDM.

Conversely, suppose DD is a coEDM and let s=1nes=\frac{1}{n}e. Then there exists ω∈e⊥\omega\in e^{\perp} such that

F=−12(I−esT)D(I−seT)F=-\frac{1}{2}(I-es^{T})D(I-se^{T})

is positive semidefinite on ω⊥\omega^{\perp}. Consider a vector tt such that tTe=1t^{T}e=1 and tTω=0t^{T}\omega=0. Then for s=1nes=\frac{1}{n}e,

(I−etT)(I−esT)=I−etT,(I-et^{T})(I-es^{T})=I-et^{T},

and

(I−etT)F(I−teT)=−12(I−etT)D(I−teT).(I-et^{T})F(I-te^{T})=-\frac{1}{2}(I-et^{T})D(I-te^{T}).

Suppose x∈ω⊥x \in\omega^{\perp}, then

−12xT(I−etT)D(I−teT)x=xT(I−etT)F(I−teT)x≥0.-\frac{1}{2}x^{T}(I-et^{T})D(I-te^{T})x=x^{T}(I-et^{T})F(I-te^{T})x\geq0.

Thus, −12(I−esT)D(I−seT)-\frac{1}{2}(I-es^{T})D(I-se^{T}) is positive semidefinite on ω⊥\omega^{\perp} for any ss such that sTe=1s^{T}e=1 and sTω=0s^{T}\omega=0. The proof is complete.

The following result generalises the result of Gower [5] to coEDMs and provides a new equivalent condition for a matrix to be coEDM.

Corollary 1. Let DD be a hollow symmetric n×nn \times n matrix. Then DD is a conditional Euclidean distance matrix if and only if there exists ω∈e⊥\omega\in e^{\perp} such that yTDy≤0y^{T}Dy\leq0 for all y∈span⁡{1,ω}⊥y \in\operatorname{span}\{1,\omega\}^{\perp}.

Proof. Suppose DD is a coEDM. Let y∈span⁡{1,ω}⊥y \in\operatorname{span}\{1,\omega\}^{\perp}. Then by Theorem 2

yTDy=−2yTFy≤0.y^{T}Dy=-2y^{T}Fy\leq0.

Conversely, suppose yTDy≤0y^{T}Dy \le0 for all y∈span⁡{1,ω}⊥y \in\operatorname{span}\{1,\omega\}^{\perp}. Let s∈Rns \in\mathbb{R}^{n} such that eTs=1e^{T}s=1 and sTω=0s^{T}\omega=0. Let x∈ω⊥x \in\omega^{\perp} and take y=(I−seT)xy=(I-se^{T})x. Then y=x−(eTx)sy=x-(e^{T}x)s and hence yTe=yTω=0y^{T}e=y^{T}\omega=0. Thus

−12xT(I−esT)D(I−seT)x=−12yTDy≥0.-\frac{1}{2}x^{T}(I-es^{T})D(I-se^{T})x=-\frac{1}{2}y^{T}Dy\ge0.

Therefore, by Theorem 2, DD is a coEDM. This completes the proof.

The above result shows that DD is a coEDM if and only if DD is negative semidefinite on span⁡{1,ω}⊥\operatorname{span}\{1,\omega\}^{\perp}. For a given ω∈Rn\omega\in\mathbb{R}^{n}, we define Hωn:={x∈Rn:eTx=ωTx=0}H_{\omega}^{n}:=\{x\in\mathbb{R}^{n}:e^{T}x=\omega^{T}x=0\}. It is known that a non-zero EDM has exactly one positive eigenvalue. The following lemma shows that a coEDM can have at most two positive eigenvalues.

Theorem 3. Suppose DD is a conditional Euclidean distance matrix. Then DD has at most two positive eigenvalues.

Proof. Suppose DD is a coEDM. Then by Corollary 1, there exists ω∈e⊥\omega\in e^{\perp} such that yTDy≤0y^{T}Dy\le0 for all y∈Hωny\in H_{\omega}^{n}.

If possible, suppose DD has three positive eigenvalues λ\lambda, μ\mu, and γ\gamma with eigenvectors xx, yy and zz, respectively. Without loss of generality, we may assume that xx, yy and zz are orthogonal.

Since xTDx=λxTx>0x^{T}Dx=\lambda x^{T}x>0, x∉Hωnx\notin H_{\omega}^{n}. Similarly y∉Hωny\notin H_{\omega}^{n} and z∉Hωnz\notin H_{\omega}^{n}. Let

c=(eTz)(ωTy)−(eTy)(ωTz),c=(e^{T}z)(\omega^{T}y)-(e^{T}y)(\omega^{T}z),
d=(eTz)(ωTx)−(ωTz)(eTx),d=(e^{T}z)(\omega^{T}x)-(\omega^{T}z)(e^{T}x),

and

f=(eTy)(ωTx)−(ωTy)(eTx).f=(e^{T}y)(\omega^{T}x)-(\omega^{T}y)(e^{T}x).

In order to see that the constants cc, dd and ff are non-zero, we need to check if the matrices

[eTzeTyωTzωTy],[eTzeTxωTzωTx],[eTyeTxωTyωTx]\begin{bmatrix} e^{T}z & e^{T}y\\ \omega^{T}z & \omega^{T}y \end{bmatrix}, \quad \begin{bmatrix} e^{T}z & e^{T}x\\ \omega^{T}z & \omega^{T}x \end{bmatrix}, \quad \begin{bmatrix} e^{T}y & e^{T}x\\ \omega^{T}y & \omega^{T}x \end{bmatrix}

are non-singular. It is enough to show that the columns of these matrices are linearly independent. If possible suppose there are non-zero constants α\alpha and β\beta such that

α[eTzωTz]+β[eTyωTy]=0.\alpha \begin{bmatrix} e^{T}z\\ \omega^{T}z \end{bmatrix} + \beta \begin{bmatrix} e^{T}y\\ \omega^{T}y \end{bmatrix} =0.

Then αz+βy∈Hωn\alpha z+\beta y\in H_{\omega}^{n} and

(αz+βy)TD(αz+βy)=α2γzTz+β2μyTy>0,(\alpha z+\beta y)^{T}D(\alpha z+\beta y)=\alpha^{2}\gamma z^{T}z+\beta^{2}\mu y^{T}y>0,

which is a contradiction since DD is negative semidefinite on HωnH_{\omega}^{n}. Hence the constant cc is non-zero. It can be shown similarly that the constants dd and ff are non-zero.

Next, we note that cx−dy+ez∈Hωncx-dy+ez \in H_{\omega}^{n} and

(cx−dy+ez)TD(cx−dy+ez)=c2xTDx+d2yTDy+e2zTDz=c2λxTx+d2μyTy+e2γzTz>0,(cx-dy+ez)^{T}D(cx-dy+ez)=c^{2}x^{T}Dx+d^{2}y^{T}Dy+e^{2}z^{T}Dz = c^{2}\lambda x^{T}x+d^{2}\mu y^{T}y+e^{2}\gamma z^{T}z>0,

which is again a contradiction. Hence DD has at most two positive eigenvalues. The proof is complete.

One important aspect of EDMs is that they represent the distance between nn points in the Euclidean space. In our next result we obtain a similar representation of coEDMs and show that coEDMs represent perturbed distances between nn points in the Euclidean space.

Theorem 4. A n×nn \times n hollow symmetric matrix D:=(dij)D := (d_{ij}) is a conditional Euclidean distance matrix if and only if there exists vectors p1,p2,…,pn∈Rsp^{1},p^{2},\ldots,p^{n} \in\mathbb{R}^{s}, for some ss, ω:=(ωi)∈Rn\omega:= (\omega_i) \in\mathbb{R}^{n}, and α∈R\alpha\in\mathbb{R}, such that

dij=∥pi−pj∥2+α(ωi−ωj)2d_{ij}=\lVert p^{i}-p^{j}\rVert^{2}+\alpha(\omega_i-\omega_j)^{2}

for i,j=1,2,…,ni,j=1,2,\ldots,n.

Proof. Suppose DD is a coEDM. From (2), we know that

Cn=En∪K(Ωn(1)(e)).\mathcal{C}_{n}=\mathcal{E}_{n}\cup\mathcal{K}\left(\Omega_{n}^{(1)}(e)\right).

If DD is an EDM, then the result follows by using (1). Assume D∈K(Ωn(1)(e))D\in\mathcal{K}\left(\Omega_{n}^{(1)}(e)\right). Then there exists F∈Ωn(1)(e)F\in\Omega_{n}^{(1)}(e) such that D=K(F)D=\mathcal{K}(F). Let r=rank⁡(F)≠1r=\operatorname{rank}(F)\ne1 and λ1≥⋯≥λr−1>0>α\lambda_1\ge\cdots\ge\lambda_{r-1}>0>\alpha be the ordered non-zero eigenvalues of FF. We can write the spectral decomposition of FF as

F=ΓΛΓT+αωωT,F=\Gamma\Lambda\Gamma^{T}+\alpha\omega\omega^{T},

with Γ=(γ1,…,γr−1)\Gamma=(\gamma_1,\ldots,\gamma_{r-1}), and Λ=diag⁡(λ1,…,λr−1)(r−1)×(r−1)\Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_{r-1})_{(r-1)\times(r-1)}, where ΓTΓ=I\Gamma^{T}\Gamma=I, ΓTe=0\Gamma^{T}e=0, ΓTω=0\Gamma^{T}\omega=0 and ωTe=0\omega^{T}e=0. Since ΓΛΓT∈Ωn(e)\Gamma\Lambda\Gamma^{T}\in\Omega_n(e), the matrix Δ=K(ΓΛΓT)\Delta=\mathcal{K}(\Gamma\Lambda\Gamma^{T}) is an EDM. Applying the map K\mathcal{K} to FF, we get

D=K(F)=Δ+αK(ωωT).D=\mathcal{K}(F)=\Delta+\alpha\mathcal{K}(\omega\omega^{T}).

Let ω=(ωi)\omega=(\omega_i). By (1), there exists vectors p1,p2,…,pn∈Rr−1p^{1},p^{2},\ldots,p^{n}\in\mathbb{R}^{r-1} such that

dij=∥pi−pj∥2+α(ωi−ωj)2d_{ij}=\lVert p^{i}-p^{j}\rVert^{2}+\alpha(\omega_i-\omega_j)^{2}

for i,j=1,2,…,ni,j=1,2,\ldots,n. If r=1r=1, then the only non-zero eigenvalue of FF is negative. Therefore there exist α<0\alpha<0 and ω∈Rn\omega\in\mathbb{R}^{n} such that F=αωωTF=\alpha\omega\omega^{T}. Choosing p1=p2=⋯=pn=0∈Rnp^{1}=p^{2}=\cdots=p^{n}=0\in\mathbb{R}^{n}, we get

dij=K(F)=∥pi−pj∥2+α(ωi−ωj)2d_{ij}=\mathcal{K}(F)=\lVert p^{i}-p^{j}\rVert^{2}+\alpha(\omega_i-\omega_j)^{2}

for i,j=1,2,…,ni, j = 1, 2, \ldots, n.

For the reverse implication, suppose there exist vectors p1,p2,…,pn∈Rsp^1,p^2,\ldots,p^n \in\mathbb{R}^s, for some ss, ω:=(ωi)∈Rn\omega:= (\omega_i) \in\mathbb{R}^n and α∈R\alpha\in\mathbb{R} such that

dij=∥pi−pj∥2+α(ωi−ωj)2(4)d_{ij} = \lVert p^i-p^j\rVert^2+\alpha(\omega_i-\omega_j)^2 \tag*{(4)}

for i,j=1,2,…,ni, j = 1, 2, \ldots, n. In (4), without loss of generality, we can assume that α<0\alpha< 0, since if α>0\alpha> 0, the element dijd_{ij} is written as dij=∥yi−yj∥2d_{ij} = \lVert y^i-y^j\rVert^2 where

yi=(piT,αωi)T∈Rs+1,y^i = \left(p^{iT},\sqrt{\alpha}\omega_i\right)^T \in\mathbb{R}^{s+1},

which means DD is an EDM. Clearly, when α=0\alpha= 0, the matrix DD is also an EDM. Now suppose α<0\alpha< 0 in (4).

We can also assume, without loss of generality, that ωTe=0\omega^T e = 0. For, if ωTe≠0\omega^T e \ne0, we can replace ω\omega by ω−ωTene\omega-\frac{\omega^T e}{n}e in (4) without affecting any entry in DD. Now, we have

dij=∥pi∥2+∥pj∥2−2⟨pi,pj⟩+α(ωi2+ωj2−2ωiωj)=∥pi∥2+αωi2+∥pj∥2+αωj2−2(⟨pi,pj⟩+αωiωj).\begin{aligned} d_{ij} &= \lVert p^i\rVert^2+\lVert p^j\rVert^2-2\langle p^i,p^j\rangle+\alpha(\omega_i^2+\omega_j^2-2\omega_i\omega_j)\\ &=\lVert p^i\rVert^2+\alpha\omega_i^2+\lVert p^j\rVert^2+\alpha\omega_j^2-2(\langle p^i,p^j\rangle+\alpha\omega_i\omega_j). \end{aligned}

Define G:=(gij)G := (g_{ij}), where gij:=⟨pi,pj⟩+αωiωjg_{ij} := \langle p^i,p^j\rangle+\alpha\omega_i\omega_j. We claim that GG is positive semidefinite on ω⊥\omega^\perp. Note that

G=XXT+αωωT,G = XX^T+\alpha\omega\omega^T,

where XX has pip^i as its ithi^{\mathrm{th}} row, for each i=1,…,ni=1,\ldots,n. Suppose x∈ω⊥x\in\omega^\perp. Then

xTGx=xTXXTx+αxTωωTx=∥xTX∥2≥0.x^T Gx=x^TXX^Tx+\alpha x^T\omega\omega^Tx=\lVert x^T X\rVert^2\ge0.

Thus GG is positive semidefinite on ω⊥\omega^\perp. It is easy to see that

D=EDiag⁡(G)+Diag⁡(G)E−2G.D=E\operatorname{Diag}(G)+\operatorname{Diag}(G)E-2G.

Hence −12JDJ=JGJ-\frac{1}{2}JDJ=JGJ. Define

F=−12JDJ.F=-\frac{1}{2}JDJ.

Let x∈ω⊥x\in\omega^\perp. Then

xTJω=xT(I−1nE)ω=xTω=0.x^T J\omega=x^T\left(I-\frac{1}{n}E\right)\omega=x^T\omega=0.

Thus xTJ∈ω⊥x^T J\in\omega^\perp and therefore xTFx=xTJGJx≥0x^T F x=x^T JGJx\ge0. Hence, FF is positive semidefinite on ω⊥\omega^\perp. So, DD is a coEDM. This completes the proof.

The above result shows that any nn points in a Euclidean space, together with an additional coordinate specified by ω\omega, can be used to generate a coEDM. The next result provides a necessary and sufficient condition for a coEDM to be non-negative and is a direct consequence of Theorem 4.

Corollary 2. Suppose D:=(dij)D := (d_{ij}) is a conditional Euclidean distance matrix that is not an EDM and let p1,p2,…,pn∈Rs\mathbf{p}^{1},\mathbf{p}^{2},\ldots,\mathbf{p}^{n} \in\mathbb{R}^{s}, for some ss, ω:=(ωi)∈Rn\boldsymbol{\omega} := (\omega_i) \in\mathbb{R}^{n} and α∈R\alpha\in\mathbb{R}, such that

dij=∥pi−pj∥2+α(ωi−ωj)2d_{ij} = \lVert\mathbf{p}^{i} - \mathbf{p}^{j} \rVert^{2} + \alpha(\omega_i - \omega_j)^{2}

for i,j=1,2,…,ni,j = 1,2,\ldots,n. Then DD is non-negative if and only if

α≥−min⁡{(i,j):ωi≠ωj}∥pi−pj∥2(ωi−ωj)2.\alpha\geq- \min_{\{(i,j):\omega_i\ne\omega_j\}} \frac{\lVert\mathbf{p}^{i} - \mathbf{p}^{j} \rVert^{2}}{(\omega_i-\omega_j)^{2}}.

We will next illustrate the construction of coEDMs given in the proof of Theorem 4 and the non-negativity condition given in Corollary 2 through an example. The example uses the notations introduced in the proof of Theorem 4.

Example 2. Let

γ1=12[1−100],γ2=12[10−10],ω=12[100−1].\gamma_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ -1\\ 0\\ 0 \end{bmatrix}, \qquad \gamma_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ 0\\ -1\\ 0 \end{bmatrix}, \qquad \omega= \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ 0\\ 0\\ -1 \end{bmatrix}.

Define

Fα:=2γ1γ1T+2γ2γ2T+αωωT.F_\alpha:= 2\gamma_1\gamma_1^{T} + 2\gamma_2\gamma_2^{T} + \alpha\omega\omega^{T}.

For each α∈R\alpha\in\mathbb{R}, Fα∈Ωn(e)F_\alpha\in\Omega_n(e) and hence Dα:=K(Fα)D_\alpha:= \mathcal{K}(F_\alpha) is a coEDM. Since

K(vvT)=((vi−vj)2)\mathcal{K}(vv^{T}) = ((v_i-v_j)^2)

for any vector vv, we can easily compute DαD_\alpha as follows:

Dα=2K(γ1γ1T)+2K(γ2γ2T)+αK(ωωT)=[0411401111001100]+[0141101041011010]+α2[0114100110014110]=[0552502152012110]+α2[0114100110014110]=(∥pi−pj∥2+α(ωi−ωj)2).\begin{aligned} D_\alpha&= 2\mathcal{K}(\gamma_1\gamma_1^{T}) + 2\mathcal{K}(\gamma_2\gamma_2^{T}) + \alpha\mathcal{K}(\omega\omega^{T})\\ &= \begin{bmatrix} 0&4&1&1\\ 4&0&1&1\\ 1&1&0&0\\ 1&1&0&0 \end{bmatrix} + \begin{bmatrix} 0&1&4&1\\ 1&0&1&0\\ 4&1&0&1\\ 1&0&1&0 \end{bmatrix} + \frac{\alpha}{2} \begin{bmatrix} 0&1&1&4\\ 1&0&0&1\\ 1&0&0&1\\ 4&1&1&0 \end{bmatrix}\\ &= \begin{bmatrix} 0&5&5&2\\ 5&0&2&1\\ 5&2&0&1\\ 2&1&1&0 \end{bmatrix} + \frac{\alpha}{2} \begin{bmatrix} 0&1&1&4\\ 1&0&0&1\\ 1&0&0&1\\ 4&1&1&0 \end{bmatrix} = (\lVert\mathbf{p}^{i} - \mathbf{p}^{j} \rVert^{2} + \alpha(\omega_i-\omega_j)^{2}). \end{aligned}

Since

−min⁡{(i,j):ωi≠ωj}∥pi−pj∥2(ωi−ωj)2=−∥p1−p4∥2(ω1−ω4)2=−1,-\min_{\{(i,j):\omega_i\ne\omega_j\}} \frac{\lVert\mathbf{p}^{i}-\mathbf{p}^{j}\rVert^{2}}{(\omega_i-\omega_j)^{2}} = -\frac{\lVert\mathbf{p}^{1}-\mathbf{p}^{4}\rVert^{2}}{(\omega_1-\omega_4)^{2}} = -1,

the coEDM, DαD_{\alpha} is non-negative if and only if α≥−1\alpha\geq-1. Taking α=−12\alpha=-\frac{1}{2}, we obtain the following non-negative coEDM.

Dα=[0552502152012110]−14[0114100110014110]=14[01919419083198034330].D_{\alpha}= \begin{bmatrix} 0&5&5&2\\ 5&0&2&1\\ 5&2&0&1\\ 2&1&1&0 \end{bmatrix} -\frac{1}{4} \begin{bmatrix} 0&1&1&4\\ 1&0&0&1\\ 1&0&0&1\\ 4&1&1&0 \end{bmatrix} =\frac{1}{4} \begin{bmatrix} 0&19&19&4\\ 19&0&8&3\\ 19&8&0&3\\ 4&3&3&0 \end{bmatrix}.

We further note that for α=−12\alpha=-\frac{1}{2}, DαD_{\alpha} is not an EDM since FαF_{\alpha} has one negative eigenvalue.

Projected centered symmetric matrix

We recall that J=I−1nEJ=I-\frac{1}{n}E is the orthogonal projection matrix onto e⊥e^{\perp}. A different choice of basis of e⊥e^{\perp} will give rise to different factorizations of JJ. We present here two such factorizations. Define Un×(n−1):=[−eTI]U_{n\times(n-1)}:=\begin{bmatrix}-e^{T}\\I\end{bmatrix} and VV to be a n×(n−1)n\times(n-1) matrix whose columns form an orthonormal basis of e⊥e^{\perp}. It is easy to see that J=UU†=VVTJ=UU^{\dagger}=VV^{T}. The matrix VV is not unique. We choose the following VV

V=[yeTI+xeeT],where y=−1n and x=−1n+n.V=\begin{bmatrix}ye^{T}\\I+xee^{T}\end{bmatrix},\quad\text{where }y=-\frac{1}{\sqrt{n}}\text{ and }x=-\frac{1}{n+\sqrt{n}}.

We note that

V=U(I+xeeT),andU=V(I+xyeeT).V=U(I+xee^{T}),\quad\text{and}\quad U=V\left(I+\frac{x}{y}ee^{T}\right).

Consider the following two transformations TV:Shn→Sn−1\mathcal{T}_{V}:\mathcal{S}_{h}^{n}\to\mathcal{S}^{n-1} and KV:Sn−1→Shn\mathcal{K}_{V}:\mathcal{S}^{n-1}\to\mathcal{S}_{h}^{n} defined by

TV(A)=VTT(A)V=−12VTAV,\mathcal{T}_{V}(A)=V^{T}\mathcal{T}(A)V=-\frac{1}{2}V^{T}AV,

and

KV(X)=K(VXVT)=EDiag⁡(VXVT)+Diag⁡(VXVT)E−2VXVT.\mathcal{K}_{V}(X)=\mathcal{K}(VXV^{T})=E\operatorname{Diag}(VXV^{T})+\operatorname{Diag}(VXV^{T})E-2VXV^{T}.

We call TV(A)\mathcal{T}_{V}(A) the projected centered symmetric matrix of AA. It is easy to see that rank⁡(T(A))=rank⁡(TV(A))\operatorname{rank}(\mathcal{T}(A))=\operatorname{rank}(\mathcal{T}_{V}(A)) and T(A)=VTV(A)VT\mathcal{T}(A)=V\mathcal{T}_{V}(A)V^{T} for all A∈ShnA\in\mathcal{S}_{h}^{n}. Furthermore, the transformation TV\mathcal{T}_{V} restricted to Shn\mathcal{S}_{h}^{n} is the inverse of the transformation KV\mathcal{K}_{V} (see [20], Chapter 4).

Theorem 5. Let DD be an n×nn\times n hollow symmetric matrix. Then DD is a coEDM if and only if TV(D)\mathcal{T}_{V}(D) is positive semidefinite on {ω~}⊥\{\widetilde{\omega}\}^{\perp} for some ω~∈Rn−1\widetilde{\omega}\in\mathbb{R}^{n-1}.

Proof. Using Theorem 1, it is enough to show that TV(D)\mathcal{T}_{V}(D) is positive semidefinite on ω~⊥\widetilde{\omega}^{\perp} for some ω~∈Rn−1\widetilde{\omega}\in\mathbb{R}^{n-1} if and only if T(D)\mathcal{T}(D) is positive semidefinite on ω⊥\omega^{\perp} for some ω∈e⊥\omega\in e^{\perp}. Let ω∈e⊥\omega\in e^\perp such that J(D)\mathcal{J}(D) is positive semidefinite on ω⊥\omega^\perp. Define ω~:=VTω∈Rn−1\widetilde{\omega} := V^T\omega\in\mathbb{R}^{n-1} and let x∈ω~⊥x \in\widetilde{\omega}^\perp. Since

xTJV(D)x=xTVTJ(D)Vx,x^T\mathcal{J}_V(D)x = x^TV^T\mathcal{J}(D)Vx,

and xTVTω=xTω~=0x^TV^T\omega= x^T\widetilde{\omega} = 0, it follows that xTJV(D)x≥0x^T\mathcal{J}_V(D)x \ge0. Conversely, suppose ω~∈Rn−1\widetilde{\omega} \in\mathbb{R}^{n-1} such that JV(D)\mathcal{J}_V(D) is positive semidefinite on {ω~}⊥\{\widetilde{\omega}\}^\perp. Define ω:=Vω~∈Rn\omega:= V\widetilde{\omega} \in\mathbb{R}^n. Clearly ω∈e⊥\omega\in e^\perp. Let x∈ω⊥x \in\omega^\perp, and consider

xTJ(D)x=xTVJV(D)VTx.x^T\mathcal{J}(D)x = x^TV\mathcal{J}_V(D)V^Tx.

Since xTVω~=xTω=0x^TV\widetilde{\omega} = x^T\omega= 0, it is evident that xTJ(D)x≥0x^T\mathcal{J}(D)x \ge0. The proof is complete.

Theorem 6. Let D=[0dTdD~]D = \begin{bmatrix} 0 & d^T \\ d & \widetilde{D} \end{bmatrix} be an n×nn \times n real symmetric matrix whose diagonal entries are all zero, where d∈Rn−1d \in\mathbb{R}^{n-1}. Then DD is an coEDM if and only if

deT+edT−D~de^T + ed^T - \widetilde{D}

is positive semidefinite on ω⊥\omega^\perp for some ω∈Rn−1\omega\in\mathbb{R}^{n-1}.

Proof. From Theorem 5, DD is a coEDM if and only if −VTDV-V^TDV is positive semidefinite on ω⊥\omega^\perp for some ω∈Rn−1\omega\in\mathbb{R}^{n-1}. But V=UAV = UA, where AA is the non-singular matrix I+xeTI + xe^T. Thus DD is a coEDM if and only if −UTDU-U^TDU is positive semidefinite on ω⊥\omega^\perp for some ω∈Rn−1\omega\in\mathbb{R}^{n-1}. The result now follows because UTDU=−deT−edT+D~U^TDU = -de^T - ed^T + \widetilde{D}.

The pre-Gale space and the pre-Gale matrix

Let DD be an n×nn \times n EDM. Then for some positive integer ss, there exist points p1,…,pn∈Rsp^1,\ldots,p^n \in\mathbb{R}^s such that

dij=∥pi−pj∥2d_{ij} = \lVert p^i-p^j\rVert^2

for each i,j∈{1,…,n}i,j \in\{1,\ldots,n\}. The dimension of the affine span of these nn points is called the embedding dimension of DD. Let X:=[p1,…,pn]TX := [p^1,\ldots,p^n]^T and F=XXTF = XX^T. It is easy to see that F=−12JDJF = -\frac{1}{2}JDJ. The Gale space of an n×nn \times n EDM DD of embedding dimension rr, denoted by gal⁡(D)\operatorname{gal}(D), is defined as

gal⁡(D)=null⁡(XT)∩null⁡(eT).\operatorname{gal}(D) = \operatorname{null}(X^T) \cap\operatorname{null}(e^T).

It is well known that for EDMs with embedding dimension rr, the dimension of the Gale space is n−1−rn-1-r. Since null⁡(F)=null⁡(XT)\operatorname{null}(F) = \operatorname{null}(X^T), Gale space can also be defined as

gal⁡(D)=null⁡(F)∩null⁡(eT).\operatorname{gal}(D) = \operatorname{null}(F) \cap\operatorname{null}(e^T).

Any n×(n−1−r)n \times(n-1-r) matrix ZZ whose columns form a basis of gal⁡(D)\operatorname{gal}(D) is called a Gale matrix of DD. For EDMs, the Gale space and the Gale matrix have been studied in detail. The geometric significance of the Gale space and the Gale matrix is also studied in detail in the literature (see Alfakih [20]). Motivated by the significance of the Gale space in the theory of EDMs, we define the following for a hollow symmetric matrix.

Definition 2. The pre-Gale space of an n×nn \times n hollow symmetric matrix DD, denoted by pGal⁡(D)\operatorname{pGal}(D), is defined as

pGal⁡(D)=null⁡(F)∩null⁡(eT),\operatorname{pGal}(D) = \operatorname{null}(F) \cap\operatorname{null}(e^{T}),

where F=−12JDJF = -\frac{1}{2}JDJ.

Note that if DD is an EDM then its pre-Gale space and Gale space coincide. Let DD be an n×nn \times n hollow symmetric matrix and r~\tilde{r} be the dimension of pGal⁡(D)\operatorname{pGal}(D). Clearly r~=n−1−rank⁡(F)\tilde{r} = n - 1 - \operatorname{rank}(F).

Definition 3. Any n×r~n \times\tilde{r} matrix ZZ whose columns form a basis of pGal⁡(D)\operatorname{pGal}(D) is said to be a pre-Gale matrix of $D.

We now present some results on the pre-Gale space and the pre-Gale matrix of a hollow symmetric matrix. Our first result establishes a connection between pre-Gale matrices and a hollow symmetric matrix.

Lemma 1. Let DD be a hollow symmetric matrix and let ZZ be a pre-Gale matrix of DD. Further, let F=−12JDJF = -\frac{1}{2}JDJ, then

DZ=eξT,DZ = e\xi^{T},

where ξ=ZTdiag⁡(F)\xi= Z^{T}\operatorname{diag}(F).

Proof. Since the maps T\mathcal{T} and K\mathcal{K} are mutually inverse, we have

D=EDiag⁡(F)+Diag⁡(F)E−2F.D = E\operatorname{Diag}(F) + \operatorname{Diag}(F)E - 2F.

The result now follows from the fact that the columns of ZZ form a basis for pGal⁡(D)=null⁡(F)∩null⁡(eT)\operatorname{pGal}(D) = \operatorname{null}(F) \cap\operatorname{null}(e^{T}). □

The following result relates the affine dependence of columns of FF to the linear dependence of columns of a pre-Gale matrix ZZ.

Lemma 2. Let rank⁡(F)=r\operatorname{rank}(F) = r, f1,…,fnf^{1}, \ldots, f^{n} be columns of FF and z1,…,zn∈Rn−r−1z^{1}, \ldots, z^{n} \in\mathbb{R}^{n-r-1} be the rows of a pre-Gale matrix ZZ. Let SS be a subset of {1,…,n}\{1, \ldots, n\} of cardinality r+1r + 1. Then {fi:i∈S}\{f^{i}: i \in S\} are affinely dependent if and only if {zi:i∈Sc}\{z^{i}: i \in S^{c}\} are linearly dependent.

Proof. Without loss of generality, we assume that S={1,…,r+1}S=\{1,\ldots,r+1\} i.e. assume that f1,…,fr+1f^1,\ldots,f^{r+1} are affinely dependent. Then there exists a non-zero λ=(λi)∈Rr+1\lambda=(\lambda_i)\in\mathbb{R}^{r+1} such that

∑i=1r+1λifi=0and∑i=1r+1λi=0.\sum_{i=1}^{r+1}\lambda_i f^i=0 \quad\text{and}\quad\sum_{i=1}^{r+1}\lambda_i=0.

Let x=[λT 0T]T∈Rnx=[\lambda^T\ 0^T]^T\in\mathbb{R}^n. Then

∑i=1nxifi=0and∑i=1nxi=0.\sum_{i=1}^{n}x_i f^i=0 \quad\text{and}\quad\sum_{i=1}^{n}x_i=0.

Thus x∈pGal(D)x\in\mathrm{pGal}(D). Partition the pre-Gale matrix ZZ as Z=[Z1Z2]Z=\begin{bmatrix}Z_1\\Z_2\end{bmatrix}, where Z1Z_1 is of order (r+1)×(n−r−1)(r+1)\times(n-r-1). Then

[Z1Z2]y=x=[λ0]\begin{bmatrix}Z_1\\Z_2\end{bmatrix}y=x=\begin{bmatrix}\lambda\\0\end{bmatrix}

for some non-zero y∈Rn−r−1y\in\mathbb{R}^{n-r-1}. Consequently, the matrix Z2Z_2 is singular. Therefore the rows zr+2,…,znz^{r+2},\ldots,z^n are linearly dependent. The proof of the converse follows by reversing the above steps. This completes the proof.

Corollary 3. Let rank⁡(F)=r\operatorname{rank}(F)=r and z1,…,zn∈Rn−r−1z^1,\ldots,z^n\in\mathbb{R}^{n-r-1} be the rows of a pre-Gale matrix ZZ. If any r+1r+1 columns of FF are affinely independent, then there exists a pre-Gale matrix of the form Z=[Z~In−r−1]Z=\begin{bmatrix}\widetilde{Z}\\I_{n-r-1}\end{bmatrix}.

Proof. Without loss of generality, assume that f1,…,fr+1f^1,\ldots,f^{r+1} are affinely independent. Partition the pre-Gale matrix ZZ as Z=[Z1Z2]Z=\begin{bmatrix}Z_1\\Z_2\end{bmatrix}, where Z1Z_1 is of order (r+1)×(n−r−1)(r+1)\times(n-r-1). Then by Lemma 2, Z2Z_2 is non-singular. The result follows by multiplying ZZ on the right with Z2−1Z_2^{-1}.

Non-negative coEDMs

In this last section we obtain some results for non-negative coEDMs using their pre-Gale space. These results are generalisations of results known for EDMs (see Alfakih [20], Chapter 3). We establish a connection between the null space of a non-negative coEDM and its pre-Gale space in our next result.

Theorem 7. Let DD be a non-zero, non-negative coEDM of order nn and let ω∈Rn\omega\in\mathbb{R}^n such that F=−12JDJF=-\frac{1}{2}JDJ is positive semidefinite on ω⊥\omega^\perp. Then

null⁡(D)∩null⁡(ω⊥)⊆pGal(D).\operatorname{null}(D)\cap\operatorname{null}(\omega^\perp)\subseteq\mathrm{pGal}(D).

Proof. Let x∈null⁡(D)∩null⁡(ωT)x \in\operatorname{null}(D) \cap\operatorname{null}(\omega^{T}) and let F=−12JDJF=-\frac{1}{2}JDJ. Then

2xTFx=−(eTx)2(eTDe)n2.2x^{T}Fx=-\frac{(e^{T}x)^{2}(e^{T}De)}{n^{2}}.

Since FF is positive semidefinite on ω⊥\omega^{\perp}, xTFx≥0x^{T}Fx \ge0. Also, eTDe>0e^{T}De > 0. Thus, it follows that eTx=0e^{T}x=0 and xTFx=0x^{T}Fx=0. This proves that x∈pGal⁡(D)x \in\operatorname{pGal}(D) and hence the result follows.

The next result provides a sufficient condition for ee to be in the column space of a coEDM.

Theorem 8. Let DD be a non-zero, non-negative coEDM of order nn and let ω∈Rn\omega\in\mathbb{R}^{n} such that F=−12JDJF=-\frac{1}{2}JDJ is positive semidefinite on ω⊥\omega^{\perp}. If null⁡(D)⊆ω⊥\operatorname{null}(D) \subseteq\omega^{\perp}, then e∈col⁡(D)e \in\operatorname{col}(D).

Proof. From Theorem 7, we have

pGal⁡(D)⊥⊆col⁡(D).\operatorname{pGal}(D)^{\perp} \subseteq\operatorname{col}(D).

The result follows from the fact that e∈pGal⁡(D)⊥e \in\operatorname{pGal}(D)^{\perp}.

Theorem 9. Let DD be a non-zero, non-negative coEDM of order nn and let ω∈Rn\omega\in\mathbb{R}^{n} such that F=−12JDJF=-\frac{1}{2}JDJ is positive semidefinite on ω⊥\omega^{\perp}. If null⁡(D)⊆ω⊥\operatorname{null}(D) \subseteq\omega^{\perp}, then

rank⁡(D)=rank⁡(F)+1 or rank⁡(D)=rank⁡(F)+2.\operatorname{rank}(D)=\operatorname{rank}(F)+1\ \text{or}\ \operatorname{rank}(D)=\operatorname{rank}(F)+2.

Proof. Since

D=EDiag⁡(F)+Diag⁡(F)E−2F,D=E\operatorname{Diag}(F)+\operatorname{Diag}(F)E-2F,

rank⁡(D)≤rank⁡(F)+2\operatorname{rank}(D) \le\operatorname{rank}(F)+2. Further, pGal⁡(D)⊥⊆col⁡(D)\operatorname{pGal}(D)^{\perp} \subseteq\operatorname{col}(D) implies rank⁡(D)≥rank⁡(F)+1\operatorname{rank}(D) \ge\operatorname{rank}(F)+1, since dim⁡(pGal⁡(D))=n−1−rank⁡(F)\dim(\operatorname{pGal}(D))=n-1-\operatorname{rank}(F). The proof is complete.

Future scope: connection to Minkowski spaces, machine learning, and general relativity

Euclidean spaces play an important role for the representation of data in machine learning. Representing data in a Euclidean space is appropriate to compare lengths and angles. However, Euclidean space often fail to capture some special structures like hierarchical structures in the data. Since hierarchies can be formulated as trees, hyperbolic spaces are used in literature to represent hierarchically structured data (see [21]). In [22], Marc et al. proposed the representation of hierarchical data using the squared Lorentzian distance and showed it is a better choice as compared to the other commonly used metrics.

Definition 4. The (n+1)(n+1)-dimensional Minkowski space M1,n\mathbb{M}^{1,n} is the real vector space Rn+1\mathbb{R}^{n+1} equipped with the symmetric bilinear form:

⟨x,y⟩L=−x0y0+x1y1+⋯+xnyn.\langle x,y\rangle_{\mathcal{L}}=-x_0y_0+x_1y_1+\cdots+x_ny_n.

where x=(x0,x1,…,xn)Tx=(x_0,x_1,\ldots,x_n)^{T} and y=(y0,y1,…,yn)T∈Rn+1y=(y_0,y_1,\ldots,y_n)^{T}\in\mathbb{R}^{n+1}. The symmetric bilinear form ⟨⋅,⋅⟩L\langle\cdot,\cdot\rangle_{\mathcal{L}} is called the Lorentzian inner product. Further, the Lorentzian norm of a vector xx is defined to be

∥x∥L=⟨x,x⟩L.\|x\|_{\mathcal{L}}=\sqrt{\langle x,x\rangle_{\mathcal{L}}}.

For x,y∈M1,nx,y\in\mathbb{M}^{1,n}, ∥x−y∥L2\|x-y\|_{\mathcal{L}}^{2} is called the squared Lorentzian distance between xx and yy.

The literature on Lorentzian inner product can be found in [23] and [24]. Suppose D=(dij)D=(d_{ij}) is a coEDM that is not an EDM. Then by Theorem 4, there exists p1,…,pn∈Rsp^{1},\ldots,p^{n}\in\mathbb{R}^{s} for some ss, ω:=(ωi)∈Rn\omega:=(\omega_i)\in\mathbb{R}^{n} and α<0\alpha<0 such that

dij=∥pi−pj∥2+α(ωi−ωj)2d_{ij}=\|p^{i}-p^{j}\|^{2}+\alpha(\omega_i-\omega_j)^{2}

for i,j=1,…,ni,j=1,\ldots,n. This means

dij=∑k=1s(pki−pkj)2−(−αωi−−αωj)2d_{ij}=\sum_{k=1}^{s}(p_k^{i}-p_k^{j})^{2}-(\sqrt{-\alpha}\omega_i-\sqrt{-\alpha}\omega_j)^{2}

for i,j=1,…,ni,j=1,\ldots,n. Define for each i=1,…,ni=1,\ldots,n,

yi=(−αωi,p1i,…,psi)∈Rs+1.y^{i}=(\sqrt{-\alpha}\omega_i,p_1^{i},\ldots,p_s^{i})\in\mathbb{R}^{s+1}.

Then it is easy to see that

dij=⟨yi−yj,yi−yj⟩L=∥yi−yj∥L2.\begin{aligned} d_{ij}&=\langle y^{i}-y^{j},y^{i}-y^{j}\rangle_{\mathcal{L}}\\ &=\|y^{i}-y^{j}\|_{\mathcal{L}}^{2}. \end{aligned}

for i,j=1,…,ni,j=1,\ldots,n. This shows that the entries of an n×nn\times n coEDM (which is not an EDM) represent the pairwise squared Lorentzian distance between nn points in a Minkowski space.

Definition 5. A subset S⊆M1,nS\subseteq\mathbb{M}^{1,n} is called achronal if for every pair of distinct points in x,y∈Sx,y\in S

∥x−y∥L2≥0.\|x-y\|_{\mathcal{L}}^{2}\geq0.

The above definition of an achronal set can be easily deduced by using the definition of 1-Lipschitz function and the fact that every achronal set is precisely the graph of a 1-Lipschitz function (see [25]). Extensive literature on achronal sets, their physical interpretation and uses can be found in the book titled General relativity by Robert Wald [26].

The next result is a direct consequence of the above discussion.

Theorem 10. Suppose D:=(dij)D := (d_{ij}) is a n×nn \times n coEDM that is not an EDM and let y1,…,yn∈M1,sy^1,\ldots,y^n \in\mathbb{M}^{1,s} such that

dij=∥yi−yj∥c2d_{ij} = \lVert y^i-y^j\rVert_c^2

Then DD is non-negative if and only if the set {y1,…,yn}\{y^1,\ldots,y^n\} is an achronal subset of M1,s\mathbb{M}^{1,s}.

There are several future directions for the continuation of theory of coEDMs and its applications. First, the interlink between coEDMs and distances in Minkowski spaces can be used to make advances in the theory of coEDMs from a geometric point of view. Second, the existing use of squared Lorentzian distance in the machine learning algorithm suggests coEDMs can be a useful mathematical tool for the representation of hierarchical data. Lastly, achronal sets allow physicists to track how information can and cannot flow through a curved universe. This connection to the theory of general relativity suggest the use of mathematical theory of coEDMs in physics.

Authors’ address:

Shivani Goel, School of Analytics, Tata Institute of Social Sciences, Mumbai, India. E-mail: [email protected]

Hiroshi Kurata, Faculty of Economics, Kanagawa University, Kanagawa, Japan. E-mail: [email protected]

References

  1. [1]F. Critchley, On certain linear mappings between inner-product and squared-distance matrices, Linear Algebra and its Applications 105 (1988) 91–107. doi:10.1016/0024-3795(88)90006-7.DOI
  2. [2]C. R. Johnson, P. Tarazaga, Connections between the real positive semidefinite and distance matrix completion problems, Linear Algebra and its Applications 223–224 (1995) 375–391. doi:10.1016/0024-3795(95)00096-A.DOI
  3. [3]I. J. Schoenberg, Remarks to maurice fréchet’s article “sur la définition axiomatique d’une classe d’espaces distanciés vectoriellement applicable sur l’espace de hilbert”, Annals of Mathematics (3) (1935) 724–732. doi:10.2307/1968654.DOI
  4. [4]J. C. Gower, Some distance properties of latent root and vector methods used in multivariate analysis, Biometrika 53 (3–4) (1966) 325–338. doi:10.1093/biomet/53.3-4.325.DOI
  5. [5]J. C. Gower, Euclidean distance geometry, Mathematical Scientist 7 (1) (1982) 1–14.
  6. [6]J. Gower, Properties of Euclidean and non-Euclidean distance matrices, Linear Algebra and its Applications 67 (1985) 81–97. doi:10.1016/0024-3795(85)90187-9.DOI
  7. [7]T. Hayden, J. Wells, Approximation by matrices positive semidefinite on a subspace, Linear Algebra and its Applications 109 (1988) 115–130. doi:10.1016/0024-3795(88)90202-9.DOI
  8. [8]P. Tarazaga, T. Hayden, J. Wells, Circum-Euclidean distance matrices and faces, Linear Algebra and its Applications 232 (1996) 77–96. doi:10.1016/0024-3795(94)00031-X.DOI
  9. [9]P. Tarazaga, B. Sterba-Batwright, K. Wijewardena, Euclidean distance matrices: Special subsets, systems of coordinates and multibalanced matrices, Computational and Applied Mathematics 26 (3) (2007) 415–438. doi:10.1590/S0101-82052007000300006.DOI
  10. [10]T. L. Hayden, R. Reams, J. Wells, Methods for constructing distance matrices and the inverse eigenvalue problem, Linear Algebra and its Applications 295 (1–3) (1999) 97–112. doi:10.1016/S0024-3795(99)00065-8.DOI
  11. [11]P. Tarazaga, Faces of the cone of Euclidean distance matrices: Characterizations, structure and induced geometry, Linear Algebra and its Applications 408 (1) (2005) 1–13. doi:10.1016/j.laa.2005.03.038.DOI
  12. [12]A. Alfakih, On the nullspace, the rangespace and the characteristic polynomial of Euclidean distance matrices, Linear Algebra and its Applications 416 (2–3) (2006) 348–354. doi:10.1016/j.laa.2005.11.016.DOI
  13. [13]J. Bénasséni, A variance inequality ensuring that a pre-distance matrix is Euclidean, Linear Algebra and its Applications 416 (2–3) (2006) 365–372. doi:10.1016/j.laa.2005.11.026.DOI
  14. [14]H. Kurata, T. Sakuma, A group majorization ordering for Euclidean distance matrices, Linear Algebra and its Applications 420 (2–3) (2007) 586–595. doi:10.1016/j.laa.2006.08.013.DOI
  15. [15]H. Kurata, P. Tarazaga, Multispherical Euclidean distance matrices, Linear Algebra and its Applications 433 (3) (2010) 534–546. doi:10.1016/j.laa.2010.03.018.DOI
  16. [16]H. Kurata, S. Matsuura, Characterization of multispherical and block structures of Euclidean distance matrices, Linear Algebra and its Applications 439 (10) (2013) 3177–3183. doi:10.1016/j.laa.2013.09.008.DOI
  17. [17]H. Kurata, R. B. Bapat, Moore–penrose inverse of a Euclidean distance matrix, Linear Algebra and its Applications 472 (2015) 106–117. doi:10.1016/j.laa.2015.01.032.DOI
  18. [18]R. Balaji, R. Bapat, On Euclidean distance matrices, Linear Algebra and its Applications 424 (1) (2007) 108–117. doi:10.1016/j.laa.2006.05.013.DOI
  19. [19]H. Kurata, R. B. Bapat, Moore-penrose inverse of a hollow symmetric matrix and a predistance matrix, Special Matrices 4 (1) (2016) 270–282. doi:10.1515/spma-2016-0028.DOI
  20. [20]A. Y. Alfakih, Euclidean distance matrices and their applications in rigidity theory, 1st Edition, Springer, Cham, Switzerland, 2018. doi:10.1007/978-3-319-97846-8.DOI
  21. [21]M. Gromov, Hyperbolic groups, in: S. M. Gersten (Ed.), Essays in Group Theory, Vol. 8 of Mathematical Sciences Research Institute Publications, Springer, New York, 1987, pp. 75–263.DOI
  22. [22]M. Law, R. Liao, J. Snell, R. Zemel, Lorentzian distance learning for hyperbolic representations, in: K. Chaudhuri, R. Salakhutdinov (Eds.), Proceedings of the 36th International Conference on Machine Learning, Vol. 97 of Proceedings of Machine Learning Research, PMLR, 2019, pp. 3672–3681.
  23. [23]X. Fan, M. Xu, H. Chen, Y. Chen, M. Das, H. Yang, Enhancing hyperbolic knowledge graph embeddings via lorentz transformations, in: Findings of the Association for Computational Linguistics: ACL 2024, Association for Computational Linguistics, Bangkok, Thailand, 2024, pp. 4575–4589. doi:10.18653/v1/2024.findings-acl.272.DOI
  24. [24]J. G. Ratcliffe, Foundations of Hyperbolic Manifolds, Vol. 149 of Graduate Texts in Mathematics, Springer, New York, NY, 2013. doi:10.1007/978-1-4757-4013-4.
  25. [25]T. Barbot, Q. Mérigot, Anosov AdS representations are quasi-Fuchsian, Groups, Geometry, and Dynamics 6 (3) (2012) 441–483. doi:10.4171/GGD/163.DOI
  26. [26]R. M. Wald, General Relativity, University of Chicago Press, Chicago, IL, 1984. doi:10.7208/chicago/9780226870373.001.0001.DOI

Paper details

vlnc:W_3yur354s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents