Geometric Algebra and Distance Matrices

Abstract

We present a new approach to the problem of recognizing an Euclidean distance matrix, based on Conformal Geometric Algebra. Such matrices are symmetric and hollow with non negative entries that are equal to the squared distances among the set of points. In addition to find these points, the method presented here also provides the minimal dimension of the related space. A comparison with a linear algebra approach is also provided.

Supported by organization CAPES, FAPESP, CNPq.

1 Introduction

In Distance Geometry (DG) the fundamental object of study is the concept of distance [9], being established as a field in mathematics after the works of Blumenthal [2]. In recent years, DG has been applied to model problems in several areas of computer science, engineering and mathematics, such as sensor network localization, molecular geometry, GPS modelling among others [10].

An $n\times n$ matrix with real entries is called a distance matrix if there exists an ordered set $\{x_1,\ldots , x_n\}$ of points in $\mathbb {R}^m$ such that each entry $a_{ij}$ is the squared distance between $x_i$ and $x_j$. When the Euclidean metric is used, we refer to a matrix of this type as an Euclidean Distance Matrix (EDM). In this case, the set $\{x_1,\ldots , x_n\}$ is called a realization of the EDM. It is clear that an EDM is symmetric, has zeros in its main diagonal and all other entries are non-negative real numbers.

We present a geometric algebra (GA) based method to recognize an EDM, which provides also a realization in a space with the minimum possible dimension. The motivation for the use of GA was the geometric description based on sphere intersections of the approach presented in [1].

In the next section, we provide some important theoretical results on EDM’s. In Sect. 3, we describe a linear algebra approach for recognizing an EDM, based on the method presented in [1]. Finally, in the Sect. 4, we present the main contribution of this work, which is a Conformal GA (CGA) approach developed to simplify the notation and the understanding of the problem.

2 EDM Recognition Problem

We start giving a formal definition of an EDM to make it clear that this does not depend on a specific set of points.

Definition 1

Let D be an $n\times n$ matrix with real entries given by D(i, j). If there exists a sequence $\{x_i\}_{i=1}^n \subset \mathbb {R}^K$, for some positive integer K, such that

$$\begin{aligned} D(i,j)=\Vert x_i - x_j \Vert ^2, i,j \in \{1,\dots ,n\}, \end{aligned}$$

(1)

we call D an EDM.

The EDM recognition problem consists in finding a sequence of points that satisfies (1), called a realization. If there is a solution, there are infinitely many realizations for a given EDM, since any isometric transformation preserves the distances among the points of the realization. Also, if we add null coordinates at the right of each point, we obtain realizations in spaces with dimensions greater than K. We synthesize these results in the next proposition, given in [1].

Proposition 1

Let an $n\times n$ matrix D be an EDM. If D has a realization $\{x_i\}_{i=1}^n$, $x_i \in \mathbb {R}^K$, then there are infinitely many realizations of D in $\mathbb {R}^p$, for any $p\ge K$.

The idea of the method we discuss here is to find the minimum K such that there is a realization for an EDM. This number is called the embedding dimension of the EDM [1].

Definition 2

Let an $n\times n$ matrix D be an EDM and let us suppose that there is a realization for D in $\mathbb {R}^K$. If for any other realization of D in $\mathbb {R}^m$, $m\ge K$, then K is called the embedding dimension of D, denoted by dim(D).

There is an upper bound for the embedding dimension related to the dimension of the matrix. In [1], the authors prove that

$$dim(D)\le n-1,$$

for an $n\times n$ EDM D with $n\ge 2$.

3 A Linear Algebra Approach for the EDM Recognition Problem

The method presented in [1] is based on the proof of Theorem 1, given below, which depends on the two following lemmas.

Lemma 1

Let an $(n+1)\times (n+1)$ matrix D be an EDM and let $D_n$ be the submatrix of D given by its first n rows and columns. If $dim(D_n)=K$, then dim(D) is either K or $K+1.$

Lemma 2

Let D as in Lemma 1 and let m be such that $dim(D)\le m$. If $\{x_i\}_{i=1}^n$ in $\mathbb {R}^m$ is a set of points that realizes $D_n$, then there exists a point $x_{n+1} \in \mathbb {R}^m$ such that $\{x_i\}_{i=1}^{n+1}$ realizes D.

The proof of the next result, given in [1], yields an algorithm to recognize an EDM, which also finds a realization for that.

Theorem 1

Let K be a positive integer and D a symmetric matrix $n\times n$, $n\ge 2$, with null diagonal and no negative entries. D is an EDM with embedding dimension K if, and only if, there exists a set of points $\{x_i\}^n_{i=1}$ in $\mathbb {R}^K$ and an index set $I = \{i_1,\dots , i_{K + 1}\} \subset \{1,2,\ldots ,n\}$, such that

$$\left\{ \begin{array}{lcl} x_{i_1} &{}\; = \;&{} 0 \\ x_{i_j}(j-1) &{}\; \ne \;&{} 0,\; j \in I_{2,K+1}\\ x_{i_j}(i) &{}\; = \;&{}0, j \in I_{2,K},\; i \in I_{j,K} \end{array}\right. $$

where $\{x_i\}_{i=1}^n$ realizes D and $I_{a,b}=\{a,a+1,\ldots , b\}$ ($x_h(p)$ is the p-th component of the h-th vector).

The idea of the algorithm is to build the given matrix from its submatrices checking whether each one is an EDM and finding a solution for them. In the positive case, the results above are used to ensure that the initial matrix is an EDM and to construct a solution.

Given a hollow $n\times n$ symmetric matrix $A=(a_{ij})$ with non-negative entries, let $A_k$, $k=1,\ldots , n$, be the principal submatrices of A. Let us consider the submatrix $A_2$, which is an EDM with a realization in $\mathbb {R}$ given by $x_1=0$ and $x_2=\sqrt{a_{12}}$, where $dim(A_2)=1.$ From Lemma 1, if $A_3$ is an EDM, then $dim(A_3)$ is 1 or 2. From Lemma 2, there is $x_3 \in \mathbb {R}^2$ such that the set of points $x_1=(0,0)$, $x_2=(\sqrt{a_{12}},0)$, and $x_3$ realize $A_3$. Therefore, if we find a solution for $x_3$, we guarantee that $A_3$ is an EDM, we give a realization for it, and also determine its embedding dimension. To find $x_3$, it is necessary to solve the following nonlinear system:

$$\left\{ \begin{array}{lcl} \Vert x_1-x_3 \Vert ^2 &{}\; = \;&{} a_{13} \\ \Vert x_2-x_3 \Vert ^2 &{}\; = \;&{} a_{23}. \end{array}\right. $$

Geometrically, it means that $x_3$ lies on the intersection of spheres centered at $x_1$ and $x_2$, with radius $\sqrt{a_{13}}$ and $\sqrt{a_{23}}$, respectively. Since $x_1=(0,0)$, the first equation is simply $\Vert x_3\Vert ^2=a_{13}$, and subtracting it from the second one, we have

$$x_2^{\top }x_3=\dfrac{1}{2}(\Vert x_2\Vert ^2-a_{23}+a_{13}).$$

This equation returns a unique solution for the first coordinate of $x_3$, say $x_{31}$, but not the second since $x_2=(\sqrt{a_{12}},0).$ To find $x_{32}$, we use the first equation to get

$$x_{32}^2=a_{13}-x_{31}^2.$$

If $x_{32}^2$ is non-negative, we ensure that $A_3$ is an EDM, otherwise it is not. If $x_{32}>0$, we have two solutions for $x_3$, say $x_3^+$ and $x_3^-$, and we increase the embedding dimension to 2, i.e., $A_3$ is an EDM with $dim(A_3)=2$ and $\{x_1,x_2,x_3^+\}$ is a realization for $A_3$ ($x_3^-$ could be used instead of $x_3^+$). However, if $x_{32}=0,$ we have only one solution for $x_3$ and we can get rid of the second coordinate of the three points to have a realization for $A_3$, which means that the embedding dimension was kept in 1, and the realization would be simply given by $\{0,\sqrt{a_{12}},x_{31}\}$. For both cases, the realizations satisfy the conditions of Theorem 1. The procedure above is repeated until we reach the whole matrix A, increasing the size of the system to be solved if all submatrices are indeed EDM’s. As the realizations satisfy the conditions of Theorem 1, supposing that $dim(A_{n-1})=K$, we have at the end the following configuration for a realization $\{x_i\}_{i=1}^{n-1} \in \mathbb {R}^K$ of $A_{n-1}$:

$$\begin{aligned} x_1= & {} (0,\ldots ,0)\\ x_2= & {} (x_{21},0,\ldots ,0)\\ &\vdots &\\ x_{n-1}= & {} (x_{n-1,1},\ldots ,x_{n-1,K}). \end{aligned}$$

We do the same we did before and insert zeros in the last coordinate of each point. Again, from Lemmas 1 and 2, if A is an EDM, dim(A) is either K or $K+1$ and there exists $x_{n} \in \mathbb {R}^{K+1}$ such that $\{x_1,\ldots , x_{n}\}$ is a realization for A. The system to be solved is given by

$$\left\{ \begin{array}{lcl} \Vert x_1-x_{n} \Vert ^2 &{}\; = \;&{} a_{1n} \\ &{} \vdots &{} \\ \Vert x_{n-1}-x_n \Vert ^2 &{}\; = \;&{} a_{n-1,n} \end{array}\right. ,$$

and the procedure is a generalization of what was made for $A_3$. That is, we subtract the first equation from all the others, recalling that $x_1=(0,\ldots , 0)$, to obtain:

$$\left\{ \begin{array}{lcl} \Vert x_{n} \Vert ^2 &{}\; = \;&{} a_{1n} \\ x_2^{\top }x_n &{}\; = \; &{} b_2 \\ &{} \vdots &{} \\ x_{n-1}^{\top }x_n &{}\; = \; &{} b_{n-1} \end{array}\right. ,$$

where $b_j=\dfrac{\Vert x_j\Vert ^2-a_{j,n}+a_{1,n}}{2},$ for $2\le j \le n-1.$ Now, from the structure of the points $x_i$, $i=2,\ldots , n-1$, there is a triangular linear system that has either a unique solution or no solution for the first K coordinates of $x_n$. If no solution is found, A is not an EDM. Otherwise, we use the solution found, say $x_n^*$, to find the last coordinate $x_{n,K+1}$. As we did before, we get

$$x_{n,K+1}^2=a_{1n}-\Vert x_{n}^* \Vert ^2.$$

If $x_{n,K+1}^2$ is negative, A is not an EDM. Otherwise, if $x_{n,K+1}^2>0$ and $dim(A)=K+1$, we have two solutions for $x_{n}$, say $x_n^+$ and $x_n^-$, and choose one to give a realization for A. If $x_{n,K+1}^2=0$, there will be only one solution for $x_n$, we get rid of the last 0 coordinate of each point, and the embedding dimension remains unchanged, implying that $dim(A)=K.$

4 A Conformal Geometric Algebra Approach

Now, using CGA, we present a new formulation for the problem taking advantage of the geometric interpretation of the approach described in the previous section.

We recall that in CGA over $\mathbb {R}^n$ we use two extra basis vectors $\{e_{\infty }, e_0\}$ together with the canonical Euclidean basis to work in a space with dimension $n+2$. In this space, we can easily represent geometric objects such as points, planes, and spheres by vectors. A powerful tool of CGA is that operators and operands are entities of the same algebra, which means that transformations like reflections, rotations or translations are performed by elements of the algebra. It is important to notice that the increase in the dimension of the space along with the metric used make these transformations to be orthogonal. Another highlight of CGA is the intuitiveness of intersecting objects. A circle, for instance, can be constructed by the intersection of two spheres, the same for a line in the intersection of two planes. These intersections are achieved with the exterior product. The geometric objects we mentioned have also another representation, given by points that lie on them, and there is also another way to intersect these objects, using the inner product. Here, we mainly focus on the first representation and in the intersections with the exterior product. For more details about CGA, we recommend [4, 5, 11].

It can be proved (see, for instance, [11]) that a sphere in $\mathbb {R}^n$, with center $c \in \mathbb {R}^n$ and radius $r\in \mathbb {R}$, can be represented in CGA by the vector

$$\begin{aligned} S=C-\dfrac{1}{2}r^2e_{\infty }, \end{aligned}$$

(2)

where C is the representation of c in the conformal space $\mathbb {R}^{n+1,1}.$ This result can be achieved developing the inner product $S\cdot C$, regarding S as the conformal representation of $s\in \mathbb {R}^n$ and using one of the most important relations between vectors in $\mathbb {R}^n$ and its conformal representations, which says that the inner product $S\cdot C$ is proportional to the square distance between s and c:

$$\begin{aligned} S\cdot C = -\dfrac{1}{2}\Vert s-c\Vert ^2. \end{aligned}$$

(3)

The next key definition is the intersection of spheres through the exterior product. Given two spheres $S_1$ and $S_2$ as in (2), the bivector $S_1\wedge S_2$ represents their intersection. This result can be directly extended to any number of spheres and we also check a prior if, in fact, there is any intersection. For more details, see [7]. The next result, given in [7, 8], will be important for the new approach.

Proposition 2

The intersection of k spheres with affine independent centers in $\mathbb {R}^n$ is either an empty set, a single point or a $(n-k+1)$-sphere¹.

Also from [7, 8], it is possible to check the nature of the intersection, computing the parameter

$$t=\sigma \cdot \tilde{\sigma },$$

where $\sigma = \bigwedge _{i=1}^k S_i$ is the intersection of spheres $S_i$, $i=1, \ldots , k$, and $\tilde{\sigma }$ is the reverse² of $\sigma$. If $t<0$, there is no intersection; if $t=0$, it occurs in a single point; and if $t>0$, the intersection is a $(n-k+1)$-sphere. The parameter t can be computed as a determinant of a matrix with ij-th entries given by $S_i\cdot S_j$. It is also possible to compute explicitly the radius and the center of the intersection by the following formulas. If $\sigma$ is the intersection of k spheres, then

$$\begin{aligned} C_{\sigma } = -\frac{1}{2} \frac{\sigma e_{\infty } \sigma }{\left( e_{\infty } \cdot \sigma \right) ^{2}}\end{aligned}$$

(4)

$$\begin{aligned} r_{\sigma }^2 = \frac{(-1)^{(k + 1)} \sigma ^{2}}{\left( e_{\infty } \cdot \sigma \right) ^{2}} \end{aligned}$$

(5)

are respectively the conformal center and squared radius of $\sigma$. Note that $r_{\sigma }$ also returns the nature of the intersection analogously to what we did for t.

The idea of the method we are developing is to have always at most two points in the intersection. So, from Proposition 2, to satisfy this requirement in $\mathbb {R}^n$ it is necessary to have n spheres. Another important remark is that in the case the intersection is exactly a point pair, these points cannot be in the hyperplane generated by all centers. In fact, they must be symmetric (relatively to this hyperplane) in order to satisfy all distance restraints. Note also that the center of this point pair³ lies on this hyperplane.

Let $n+1$ spheres in $\mathbb {R}^{n+1}$ with different centers in $\mathbb {R}^n$, i.e., with the $n+1$-th entry equal to zero. The space generated by these $n+1$ points is normal to the vector $e_{n+1}$. In fact, if $c_i$ is the center of each sphere and $C_i$ is its conformal representation, $i=1,\ldots n+1$, then

$$ C_i=\alpha _1e_1+\alpha _{n}e_n+\alpha _{\infty }e_{\infty }+e_0, $$

for $i=1,\ldots , n+1$, and $\alpha _j \in \mathbb {R}$, $j=1,\ldots , n$. Since the $n+1$-th coordinate of each point is null, we have that $C_1\wedge \cdots \wedge C_{n+1}$ is a linear combination of $(n+1)$-blades that does not contain $e_{n+1}$. Moreover, there is only one $(n+1)$-blade in this combination that does not have the vector $e_{\infty }$, given by $e_1\wedge \cdots \wedge e_n \wedge e_0$. We are interested in this one because the plane given by all of those centers is

$$\varPi =C_1\wedge \cdots \wedge C_{n+1}\wedge e_{\infty },$$

and since $e_{\infty }\wedge e_{\infty }=0$, the plane $\varPi$ is a scalar multiple of $e_1\wedge \cdots \wedge e_n\wedge e_{\infty }\wedge e_0$, which means that the vector $e_{n+1}$ is normal to the plane $\varPi$.

Now, let us suppose that those spheres intersect at a point pair given by $\{p_+,p_-\}$, implying that $p_+$ and $p_-$ are symmetric relatively to the plane given by the centers. Let m be the center of this point pair, which lies in the plane $\varPi$ as we commented earlier. It is easy to see that the segment connecting each center $c_i$ to m is perpendicular to the line given by the point pair. Indeed, for each $c_i$ this is the height of an isosceles triangle whose equal sides meet at $c_i$ and are the radius of the sphere $S_i$ (the base is exactly the segment connecting the point pair). So, given m, it is possible to obtain $p_+$ and $p_-$ walking from m through the directions $\pm e_{n+1}:$

$$\begin{aligned} p_+=m+re_{n+1}, \quad p_-=m-re_{n+1}, \end{aligned}$$

(6)

where $r\in \mathbb {R}$ is the radius of the point pair. This is an alternative manner to extract the points of a point pair that takes advantage of the knowledge of the direction of the point pair.

We can now state the main result of this section, which suggests a CGA method to solve the EDM recognition problem. Let us first define the application $\mathcal {P}$ that maps a conformal point into its corresponding point in the Euclidean space:

$$\begin{aligned} \mathcal {P}:\mathbb {R}^{n+1,1} & \rightarrow & \mathbb {R}^n \\ X & \mapsto & x. \end{aligned}$$

Theorem 2

Let K be a positive integer and A an $n \times n$ hollow and symmetric matrix with non-negative entries, for $n \ge 2$. A is an EDM with $dim(A) = K$ if, and only if, there exists a realization $\{x_i\}^n_{i=1} \subset \mathbb {R}^K$ for A and a set of indexes $I = \{i_1,\dots , i_{K + 1}\} \subset \{1,\ldots , n\}$, such that

$$\begin{aligned} {\left\{ \begin{array}{ll} x_{i_1} &{}= 0, \\ x_{i_j} &{}= \mathcal {P}(\bigwedge _{p=1}^{j-1}{S_{j_p}})^+,\ \ j \in I_{2,K+1,} \end{array}\right. } \end{aligned}$$

(7)

where $S_{j_p}=\mathcal {C}(x_{i_p}) - \frac{1}{2}a_{i_p,i_j}e_\infty$, for each $j_p$, are the conformal representations of the spheres in $\mathbb {R}^{j-1}$.

Remark 1

Note that $\mathcal {P}(\bigwedge _{p=1}^{j-1}{S_{j_p}})^+$ refers to the corresponding point in $\mathbb {R}^n$ of one of the conformal points in the point pair computed by the exterior product.

Proof

The proof is by induction on the dimension of the matrix A. Beginning with $n=2$, the matrix A is given by

$$A = \begin{bmatrix} 0 &{} a_{12} \\ a_{12} &{} 0 \end{bmatrix}.$$

Supposing that all the entries outside the diagonal are strictly positive, we have that $a_{12}>0$, A is an EDM with $dim(A)=1$, and the points $x_1 = 0$ and $x_2 = \sqrt{a_{12}}$ define a realization for A.

Let us suppose, by induction, that for any EDM with order $n\ge 2$ and embedding dimension K, the theorem is valid, i.e. there exists a realization $\{x_i\}^n_{i=1} \subset \mathbb {R}^K$ for this EDM, with an index set $I = \{i_1,\dots , i_{K + 1}\} \subset \{1,\ldots , n\}$, satisfying (7). Let us consider A as an EDM with order $(n+1)$ and $dim(A) = K$, and $A_n$ be the n-th principal submatrix of A. By Lemma 1, $A_n$ is an EDM with $dim(A_n) = k$, where k is either K or $K-1$. Using the induction hypothesis, we have that $A_n$ has a realization $\{x_i\}^n_{i=1} \subset \mathbb {R}^k$ and that there is an index set $I = \{i_1,\dots , i_{k + 1}\} \subset \{1,\ldots ,n\}$, such that

$$\begin{aligned} {\left\{ \begin{array}{ll} x_{i_1} &{}= 0, \\ x_{i_j} &{}= \mathcal {P}(\bigwedge _{p=1}^{j-1}{S_{j_p}})^+,\ \ j \in I_{2,k+1}. \end{array}\right. } \end{aligned}$$

Define $y = \mathcal {P}(P)$, where

$$P = \bigwedge _{j=1}^{k+1}S_{(n+1)_j}$$

is the intersection of the $k+1$ spheres $S_{(n+1)_j} = \mathcal {C}(x_{i_j}) - \frac{1}{2}a_{i_j,n+1}e_\infty$ in $\mathbb {R}^{k+1}$. The points $x_{i_j}$, which are the centers of the spheres, lie in $\mathbb {R}^{k}$. Then, by (6) and the discussion that led to it, if the intersection P is a point pair, its direction is given by $e_{k+1}.$ Moreover, once we know the center of each sphere and their (squared) radius given by the entries of A, the solution set for y cannot be empty, otherwise A would not be an EDM.

Using formula (5), we check the nature of the intersection looking to the sign of $r^2$. If $r^2=0$, we take

$$x_{n+1}=c,$$

where c is the unique point in the intersection, obtained by (4). On the other hand, if $r^2>0$, then the intersection y results in a point pair, where we can still compute c and choose

$$x_{n+1}=p_+,\;\; (\text{ or } p_- \text{ equivalently}),$$

obtained by (6). For both cases, the sequence $\{x_i\}_{i=1}^{n+1}$ realizes the matrix A and satisfies the theorem conditions for $n+1$. Therefore, the theorem is proved for every $n\ge 2$.    $\square$

This proof induces an algorithm (see Algorithm 1) to check if a given matrix is an EDM, to find a realization for it, in the positive case, and also to provide its embedding dimension.

The algorithm starts with the submatrix $A_2$. From $A_3$, it computes the exterior product among the spheres to obtain P (step 5) and the value $r^2$ to find the nature of P (step 6). In the next steps, the algorithm proceeds accordingly. It is very important to note that the increment on the embedding dimension only happens when $r^2>0$ (steps 11 to 14). In fact, when $r^2=0$, the point to be included in the solution lies on the plane generated by the centers, i.e. the dimension of the space containing the realization does not change. The embedding dimension is incremented by one when the new point is out of this plane, which implies that the realization will be in $\mathbb {R}^{K+1}$, with $x_i$ (in step 12) and all the previous points in $\mathbb {R}^K$ gaining a new null $K+1$-th coordinate.

5 An Illustrative Example

In this section, we illustrate the proposed approach with an example. Let us consider

$$A= \left[ \begin{array}{cccc} 0 &{} 1 &{} 1 &{} 2\\ 1 &{} 0 &{} 2 &{} 1 \\ 1 &{} 2 &{} 0 &{} 1\\ 2 &{} 1 &{} 1 &{} 0 \end{array}\right] .$$

The first submatrix to be used is

$$A_2=\left[ \begin{array}{cc} 0 &{} 1 \\ 1 &{} 0 \end{array}\right] ,$$

where a realization is given by $x_1 = 0$ and $x_2 = \sqrt{a_{12}} = 1$. Following the procedure, we insert zeros in a second coordinate of $x_1$ and $x_2$. The conformal representation of these points are respectively $X_1=e_0$ and $X_2=e_1+0.5e_{\infty }+e_0,$ and the related spheres we need to intersect are given by

$$\begin{aligned} S_1= & {} X_1 - 0.5a_{31}e_{\infty } = e_0 - 0.5e_{\infty },\\ S_2= & {} X_2 - 0.5a_{32}e_{\infty } = (e_1 +0.5e_{\infty }+e_0) - e_{\infty } = e_1-0.5e_{\infty }+e_0. \end{aligned}$$

We can use several tools to compute $r^2$ and the center C of $P=S_1\wedge S_2$ (for example, [3, 12]). Using Gaalop [6], we obtain:

$$\begin{aligned} P = & {} S_1\wedge S_2 = 0.5 e_1\wedge e_{\infty } - e_1\wedge e_0,\\ r^2 = & {} \frac{(-1)^{2+1}P^2}{(e_{\infty }\cdot P)^2} = 1,\\ C = & {} -\frac{1}{2} \frac{P e_{\infty } P}{\left( e_{\infty } \cdot P\right) ^{2}} = e_0. \end{aligned}$$

Since $r^2 > 0$, we have that $x_3 = \mathcal {C} + e_2 = e_2.$ Now, we have $I=\{1,2,3\}$ and $K=2$. As we need the conformal points, let us see the current solution given by

$$X_1 = e_0, \quad X_2 = e_1+0.5e_{\infty }+e_0, \quad X_3 = e_2 +0.5e_{\infty }+e_0.$$

To find $X_4$, we insert a null coordinate in the previous solution and compute $S=S_1\wedge S_2\wedge S_3$. From

$$\begin{aligned} S_1= & {} X_1 - 0.5a_{41}e_{\infty } = e_0 - e_{\infty },\\ S_2= & {} X_2 - 0.5a_{42}e_{\infty } = (e_1 +0.5e_{\infty }+e_0) - 0.5e_{\infty } = e_1+e_0,\\ S_3= & {} X_3 - 0.5a_{43}e_{\infty } = (e_2 +0.5e_{\infty }+e_0) - 0.5e_{\infty } = e_2+e_0, \end{aligned}$$

we obtain

$$\begin{aligned} P = & {} \bigwedge _{i=1}^3S_i = -e_1\wedge e_2\wedge e_{\infty } +e_1\wedge e_2\wedge e_0 + e_1\wedge e_{\infty }\wedge e_0 - e_2\wedge e_{\infty }\wedge e_0,\\ r^2 = & {} \frac{(-1)^{3+1}P^2}{(e_{\infty }\cdot P)^2} = 0,\\ C = & {} -\frac{1}{2} \frac{P e_{\infty } P}{\left( e_{\infty } \cdot P\right) ^{2}} = e_1+e_2+e_{\infty }+e_0. \end{aligned}$$

Since $r^2=0$, $X_4 = C$, $dim(A)=2$, and the solution is kept in $\mathbb {R}^2$, given by

$$\{(0,0),(1,0),(0,1),(1,1)\}.$$

6 Conclusion

The application of CGA to the EDM recognition problem provided a much simpler description of the linear algebra approach used to solve this problem. In fact, the result given by Theorem 2 makes clear how the sequence of points in the realization is constructed and gives a geometric meaning for each of those points as intersections of spheres, which cannot be seen in Theorem 1. Another important remark is that, in Algorithm 1, one does not need to actually change the dimension of the space. The description and the computation are similar for each dimension, implying that it is possible to set the maximum dimension since the beginning of the algorithm and update the embedding dimension according to the value of $r^2.$ The geometric intuition given by the CGA approach will be useful for instances of the problem involving uncertainties in the matrix entries, since the idea of sphere intersections is preserved.