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 denote the set of all symmetric matrices. A hollow symmetric matrix is a symmetric matrix with zero diagonal elements. Let be the set of hollow symmetric matrices of order . By a centered symmetric matrix we mean a symmetric matrix with zero row (and hence column) sums. Let be the set of all centered symmetric matrices of order given by:
As shown by Critchley [1], Theorem 2.2, and Johnson and Tarazaga [2], pp.380, there is a one-to-one correspondence between and . The following two linear maps and define this one-to-one correspondence:
Let denote the set of Euclidean distance matrices (see (1)) and let
It is of interest to note that both and forms convex cones in and , respectively. It is well known that the mappings and are mutually inverse. Consider the following subset of :
Clearly . Further, forms a cone in . In this paper we are interested in identifying and studying the image of under the linear map .
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 hollow symmetric matrix is called an Euclidean distance matrix (EDM) if for some positive integer , there exist points such that
for each . 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 and are used to represent the vectors of relevant order with all entries and , respectively. The identity and all ones matrices are represented by and , respectively. The transpose of a vector is denoted by , and we use to represent the transpose of a matrix. Two vectors and are orthogonal if . For any vector and subspace , and denote the orthogonal complement of and , respectively. The notation is used to represent a matrix with its entry as . The rank of a matrix is denoted by . For a matrix , represent the diagonal matrix formed by the diagonal entries of . The matrix is the Moore-Penrose of .
A matrix is called positive semidefinite if and only if for all . 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 is said to be positive (negative) semidefinite on a subspace , if () for any .
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 to denote the matrix . Suppose is a hollow-symmetric matrix and let . It is well-known from [3] that is an EDM if and only if is a positive semidefinite matrix. We are interested in hollow-symmetric matrices for which is not positive semidefinite. A matrix that is not positive semidefinite has at least one negative eigenvalue. We recall
and define the following.
Definition 1. A hollow symmetric matrix is a conditional Euclidean distance matrix (coEDM) if and only . We denote the set of all coEDMs by .
Since the image of a cone under a linear map is a cone, we conclude that the set of all coEDMs forms a cone in . Let
Then it is clear that the set can be decomposed as the following disjoint union
Since , we now have
Since the set of EDMs is given by , we have
Thus, every EDM is a coEDM. However, the converse is not true. The following example shows such an instance.
Example 1. Consider the matrix
Clearly, is not an EDM due to having negative entries. But it is a coEDM since the matrix can be written as , where
is a centered symmetric matrix having exactly one negative eigenvalue.
In the next section, we study , the set of all coEDMs in detail and provide some characterizations.
Characterization of coEDMs
Suppose is a hollow-symmetric matrix. From the results of Critchley [1] and Johnson [2], there exists a centered symmetric matrix such that
Since has zero row sums, it is easy to see that
where . This shows that if , then is uniquely determined. Thus, if is a coEDM, then by Theorem 1, . Since has at most one negative eigenvalue, there exists such that is positive semidefinite on . Since is a zero row sum matrix, we can assume that . Using the above discussion, we obtain the following characterization of coEDMs.
Theorem 1. A hollow symmetric matrix is a conditional Euclidean distance matrix (coEDM) if and only if the matrix is positive semidefinite on for some .
Gower in [5] showed that is a Euclidean distance matrix if and only if (3) is positive semidefinite for any with and . Later, Gower in [6] showed that the condition is superfluous. Thus is a Euclidean distance matrix if and only if (3) is positive semidefinite for any with . The next result provides a generalisation of Gower’s result for coEDMs.
Theorem 2. Let be a hollow symmetric matrix. Then is a conditionally Euclidean distance matrix if and only if there exist such that the matrix
is positive semidefinite on for any such that , and .
Proof. Suppose such that
is positive semidefinite on for any such that , and . Since , , is positive semidefinite on and hence is a coEDM.
Conversely, suppose is a coEDM and let . Then there exists such that
is positive semidefinite on . Consider a vector such that and . Then for ,
and
Suppose , then
Thus, is positive semidefinite on for any such that and . 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 be a hollow symmetric matrix. Then is a conditional Euclidean distance matrix if and only if there exists such that for all .
Proof. Suppose is a coEDM. Let . Then by Theorem 2
Conversely, suppose for all . Let such that and . Let and take . Then and hence . Thus
Therefore, by Theorem 2, is a coEDM. This completes the proof.
The above result shows that is a coEDM if and only if is negative semidefinite on . For a given , we define . 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 is a conditional Euclidean distance matrix. Then has at most two positive eigenvalues.
Proof. Suppose is a coEDM. Then by Corollary 1, there exists such that for all .
If possible, suppose has three positive eigenvalues , , and with eigenvectors , and , respectively. Without loss of generality, we may assume that , and are orthogonal.
Since , . Similarly and . Let
and
In order to see that the constants , and are non-zero, we need to check if the matrices
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 and such that
Then and
which is a contradiction since is negative semidefinite on . Hence the constant is non-zero. It can be shown similarly that the constants and are non-zero.
Next, we note that and
which is again a contradiction. Hence has at most two positive eigenvalues. The proof is complete.
One important aspect of EDMs is that they represent the distance between points in the Euclidean space. In our next result we obtain a similar representation of coEDMs and show that coEDMs represent perturbed distances between points in the Euclidean space.
Theorem 4. A hollow symmetric matrix is a conditional Euclidean distance matrix if and only if there exists vectors , for some , , and , such that
for .
Proof. Suppose is a coEDM. From (2), we know that
If is an EDM, then the result follows by using (1). Assume . Then there exists such that . Let and be the ordered non-zero eigenvalues of . We can write the spectral decomposition of as
with , and , where , , and . Since , the matrix is an EDM. Applying the map to , we get
Let . By (1), there exists vectors such that
for . If , then the only non-zero eigenvalue of is negative. Therefore there exist and such that . Choosing , we get
for .
For the reverse implication, suppose there exist vectors , for some , and such that
for . In (4), without loss of generality, we can assume that , since if , the element is written as where
which means is an EDM. Clearly, when , the matrix is also an EDM. Now suppose in (4).
We can also assume, without loss of generality, that . For, if , we can replace by in (4) without affecting any entry in . Now, we have
Define , where . We claim that is positive semidefinite on . Note that
where has as its row, for each . Suppose . Then
Thus is positive semidefinite on . It is easy to see that
Hence . Define
Let . Then
Thus and therefore . Hence, is positive semidefinite on . So, is a coEDM. This completes the proof.
The above result shows that any points in a Euclidean space, together with an additional coordinate specified by , 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 is a conditional Euclidean distance matrix that is not an EDM and let , for some , and , such that
for . Then is non-negative if and only if
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
Define
For each , and hence is a coEDM. Since
for any vector , we can easily compute as follows:
Since
the coEDM, is non-negative if and only if . Taking , we obtain the following non-negative coEDM.
We further note that for , is not an EDM since has one negative eigenvalue.
Projected centered symmetric matrix
We recall that is the orthogonal projection matrix onto . A different choice of basis of will give rise to different factorizations of . We present here two such factorizations. Define and to be a matrix whose columns form an orthonormal basis of . It is easy to see that . The matrix is not unique. We choose the following
We note that
Consider the following two transformations and defined by
and
We call the projected centered symmetric matrix of . It is easy to see that and for all . Furthermore, the transformation restricted to is the inverse of the transformation (see [20], Chapter 4).
Theorem 5. Let be an hollow symmetric matrix. Then is a coEDM if and only if is positive semidefinite on for some .
Proof. Using Theorem 1, it is enough to show that is positive semidefinite on for some if and only if is positive semidefinite on for some . Let such that is positive semidefinite on . Define and let . Since
and , it follows that . Conversely, suppose such that is positive semidefinite on . Define . Clearly . Let , and consider
Since , it is evident that . The proof is complete.
Theorem 6. Let be an real symmetric matrix whose diagonal entries are all zero, where . Then is an coEDM if and only if
is positive semidefinite on for some .
Proof. From Theorem 5, is a coEDM if and only if is positive semidefinite on for some . But , where is the non-singular matrix . Thus is a coEDM if and only if is positive semidefinite on for some . The result now follows because .
The pre-Gale space and the pre-Gale matrix
Let be an EDM. Then for some positive integer , there exist points such that
for each . The dimension of the affine span of these points is called the embedding dimension of . Let and . It is easy to see that . The Gale space of an EDM of embedding dimension , denoted by , is defined as
It is well known that for EDMs with embedding dimension , the dimension of the Gale space is . Since , Gale space can also be defined as
Any matrix whose columns form a basis of is called a Gale matrix of . 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 hollow symmetric matrix , denoted by , is defined as
where .
Note that if is an EDM then its pre-Gale space and Gale space coincide. Let be an hollow symmetric matrix and be the dimension of . Clearly .
Definition 3. Any matrix whose columns form a basis of 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 be a hollow symmetric matrix and let be a pre-Gale matrix of . Further, let , then
where .
Proof. Since the maps and are mutually inverse, we have
The result now follows from the fact that the columns of form a basis for . □
The following result relates the affine dependence of columns of to the linear dependence of columns of a pre-Gale matrix .
Lemma 2. Let , be columns of and be the rows of a pre-Gale matrix . Let be a subset of of cardinality . Then are affinely dependent if and only if are linearly dependent.
Proof. Without loss of generality, we assume that i.e. assume that are affinely dependent. Then there exists a non-zero such that
Let . Then
Thus . Partition the pre-Gale matrix as , where is of order . Then
for some non-zero . Consequently, the matrix is singular. Therefore the rows are linearly dependent. The proof of the converse follows by reversing the above steps. This completes the proof.
Corollary 3. Let and be the rows of a pre-Gale matrix . If any columns of are affinely independent, then there exists a pre-Gale matrix of the form .
Proof. Without loss of generality, assume that are affinely independent. Partition the pre-Gale matrix as , where is of order . Then by Lemma 2, is non-singular. The result follows by multiplying on the right with .
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 be a non-zero, non-negative coEDM of order and let such that is positive semidefinite on . Then
Proof. Let and let . Then
Since is positive semidefinite on , . Also, . Thus, it follows that and . This proves that and hence the result follows.
The next result provides a sufficient condition for to be in the column space of a coEDM.
Theorem 8. Let be a non-zero, non-negative coEDM of order and let such that is positive semidefinite on . If , then .
Proof. From Theorem 7, we have
The result follows from the fact that .
Theorem 9. Let be a non-zero, non-negative coEDM of order and let such that is positive semidefinite on . If , then
Proof. Since
. Further, implies , since . 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 -dimensional Minkowski space is the real vector space equipped with the symmetric bilinear form:
where and . The symmetric bilinear form is called the Lorentzian inner product. Further, the Lorentzian norm of a vector is defined to be
For , is called the squared Lorentzian distance between and .
The literature on Lorentzian inner product can be found in [23] and [24]. Suppose is a coEDM that is not an EDM. Then by Theorem 4, there exists for some , and such that
for . This means
for . Define for each ,
Then it is easy to see that
for . This shows that the entries of an coEDM (which is not an EDM) represent the pairwise squared Lorentzian distance between points in a Minkowski space.
Definition 5. A subset is called achronal if for every pair of distinct points in
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 is a coEDM that is not an EDM and let such that
Then is non-negative if and only if the set is an achronal subset of .
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]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]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]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]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]J. C. Gower, Euclidean distance geometry, Mathematical Scientist 7 (1) (1982) 1–14.
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]R. M. Wald, General Relativity, University of Chicago Press, Chicago, IL, 1984. doi:10.7208/chicago/9780226870373.001.0001.DOI