# Path Tracking using Echoes in an Unknown Environment: the Issue of
Symmetries and How to Break Them

Mireille Boutin  Department of Mathematics and Computer Science, Technische
Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands and
Department of Mathematics, Purdue University, 150 N. University St., West
Lafayette IN 47907<EMAIL_ADDRESS>and  Gregor Kemper  Technische Universität
München, Department of Mathematics, Boltzmannstr. 3, 85748 Garching, Germany
<EMAIL_ADDRESS>
###### Abstract.

This paper deals with the problem of reconstructing the path of a vehicle in
an unknown environment consisting of planar structures using sound. Many
systems in the literature do this by using a loudspeaker and microphones
mounted on a vehicle. Symmetries in the environment lead to solution
ambiguities for such systems. We propose to resolve this issue by placing the
loudspeaker at a fixed location in the environment rather than on the vehicle.
The question of whether this will remove ambiguities regardless of the
environment geometry leads to a question about breaking symmetries that can be
phrased in purely mathematical terms. We solve this question in the
affirmative if the geometry is in dimension three or bigger, and give
counterexamples in dimension two. Excluding the rare situations where the
counterexamples arise, we also give an affirmative answer in dimension two.
Our results lead to a simple path reconstruction algorithm for a vehicle
carrying four microphones navigating within an environment in which a
loudspeaker at a fixed position emits short bursts of sounds. This algorithm
could be combined with other methods from the literature to construct a path
tracking system for vehicles navigating within a potentially symmetric
environment.

###### Key words and phrases:

localization, SLAM, Cayley-Menger matrix, path reconstruction, acoustic SLAM,
Euclidean symmetries, hyperplane arrangements

###### 2020 Mathematics Subject Classification:

51K99, 51-08, 70E60

## Introduction

Several systems have been proposed to use sound to track the path of a vehicle
in an unknown environment (e.g.
[?krekovic2016echoslam,?dumbgen2022blind,?saqib2020model]). In order to track
the vehicle, the geometry of the environment must be at least partly
reconstructed as the vehicle navigates within it. Thus we are talking about
the problem of Simultaneous Localization and Mapping (SLAM), in which the path
of a user is determined while the shape and position of obstacles and other
physical structures in the environment is reconstructed. See for example the
book by ?durrant2006simultaneous [?durrant2006simultaneous] for a general
introduction to the SLAM problem. Our focus in this paper is on doing so using
sound. More specifically, we are interested in acoustic SLAM (aSLAM) where an
omnidirectional loudspeaker is used to produce a short burst of sound and
microphones capture the echoes of this sound as it bounces on the objects in
the environment. Our main interest is the correct reconstruction of the path
of the vehicle, not a precise reconstruction of all the details of the
environment. However, our results could provide the basis for a system to
perform the latter task as well.

We consider the problem of path tracking inside an environment in
${\mathbb{R}}^{n}$. The case of $n=3$ is of most interest. For example a
vehicle rolling on the ground of a house would hear the echoes reflected by
floors, ceilings and walls in ${\mathbb{R}}^{3}$. So even though the path of
the vehicle may be restricted to a 2D floor in this case, the overall problem
involves the (partial) reconstruction of a 3D environment. The 2D case is also
of considerable interest. For instance, some obstacle detection systems reduce
the problem to two dimensions (e.g., the Crazyflie drone and the e-puck robot
in [?dumbgen2022blind]).

When there are echoes from more than one surface, it is a priori unclear what
echo comes from which surface. The task of assigning a surface to an echo is
called “echo sorting” and is a current problem of interest (see for example
[?macwilliam2023simultaneous]). In a 3D environment consisting of planar
surfaces, the echoes corresponding to different surfaces can be sorted when
each surface is “heard” by at least four microphones in a known geometric
configuration [?Boutin:Kemper:2019]. One popular algorithm [?DPWLV1] uses five
microphones. In this paper we are using four microphones.

Systems that use fewer than four microphones but some additional sensors have
also been developed. For example, a smartphone equipped with a Visual-Inertial
Odometry (VIO) unit is used in [?shih2019can]. Another example is BatMapper
[?zhou2017batmapper], which combines the cell phone audio sensing capability
with a gyroscope and accelerometer. But systems based on a vehicle carrying a
speaker and a single microphone, and no other sensors, have been shown to lead
to ambiguities in the reconstruction [?krekovic2016look, ?krekovic2020shapes].

In this paper we highlight the fact that, with any number of microphones, path
ambiguities are unavoidable if the loudspeaker is carried on the vehicle.
These ambiguities stem from symmetries in the environment. For example, a
vehicle situated in a rectangular room would be unable to determine in which
corner of the room it is situated based on the geometry of the surfaces around
it. This is illustrated in Figure 1.

Figure 1. Loudspeaker on the vehicle. The microphones (red) and the
loudspeaker (blue) are positioned on the vehicle. In both vehicle positions
indicated, the echoes from a sound heard by the microphones will be exactly
the same. So the positions are indistinguishable.

Symmetries in the environment make it mathematically impossible to determine
the position of a vehicle carrying its own loudspeaker. In order to address
the issue, we put the loudspeaker in a fixed position in the environment
rather than on the vehicle. This is illustrated in Figure 2.

Figure 2. Loudspeaker at a fixed position. The sound travels along the dashed
lines. Virtually, it comes from the mirror points (violet). The fixed position
of the loudspeaker (blue) is such that there is no symmetry among the mirror
points. Vehicle positions are distinguishable.

A main result of this paper (Theorems 1 and 3) is that putting the loudspeaker
in a generic position in the environment makes the issue of symmetries
disappear. This is what we mean by “breaking symmetries.” The theorems are
phrased in purely mathematical terms.

Our setup is as follows. A vehicle equipped with four microphones is moving
inside an environment (e.g., a room or building) consisting of planar surfaces
called “walls.” The vehicle may be flying in the room or moving on the ground.
The wall positions are unknown and the microphone geometry is non-planar and
known. More specifically, we know precisely the distance between the
microphones, but the position of the microphone arrangement in the environment
is unknown. An omnidirectional loudspeaker is placed at a fixed unknown
location inside the environment. The loudspeaker emits a short high-frequency
signal (at a known time) and the signal bounces off the wall, creating echoes.
The microphones listen to the sound of the original signal and the first order
echoes to determine the distance to their respective source; the higher order
echoes are discarded. We are assuming that the vehicle did not move while it
was receiving the echoes, or that the change in position was so small that it
can be neglected. We are also assuming that the vehicle was in a generic
position at the time of reception. We are interested in reconstructing the
path of the vehicle in the environment.

Our work builds on the methods from two previous papers
[?Boutin:Kemper:2019,?Boutin:Kemper:2022]. In [?Boutin:Kemper:2019] the
vehicle is a drone with 3D freedom of translation and 3D freedom of rotation.
In [?Boutin:Kemper:2022], the vehicle is restricted to either 3D translation
and yaw rotation (e.g., a hovering drone) or to movements on a ground plane
(e.g., a car). In all cases, the vehicle knows its own position and is
equipped with four microphones: the goal is to determine the positions of the
walls. In other words, we assume that the localization problem is solved, and
so only the mapping problem remains. One problem is that “ghost walls,” i.e.,
walls that are detected but do not really exist, may appear. The main result
of [?Boutin:Kemper:2019] is that ghost walls are only possible for few vehicle
positions given full freedom of motion in 3D (translation and rotation)
regardless of the wall positions. When the vehicle motion restricted, we
showed in [?Boutin:Kemper:2022] that a few wall positions will lead to ghost
walls being detected.

Having solved the problem of reconstructing the wall positions when the
position of the vehicle is known, we now turn to the problem of determining
the path of the vehicle in this paper. The methods of
[?Boutin:Kemper:2019,?Boutin:Kemper:2022] can be used to try to recover the
geometry of the environment in an arbitrary coordinate system (e.g., a local
coordinate system for the microphone positions on the drone.) This can be
repeated at various locations along the path of the vehicle. Since the
coordinate system in which the wall positions are expressed will vary from one
location to the next, it will be necessary to transform them to a common
coordinate system; finding the transformations to the common coordinate system
is equivalent to determining the path of the vehicle in that system.
Determining this change of coordinate is the crux of the problem.

8 lays out a procedure to do this. The algorithm is stated assuming that the
environment has a 3D geometry, but it could be easily adapted to 2D. It uses
“mirror points,” which are reflections of the loudspeaker position with
respect to walls, as shown in Figure 2. Some of these mirror points, possibly
together with the loudspeaker position, are located by the algorithm every
time that the loudspeaker emits a sound burst. Together, we think of the
mirror points and the loudspeaker position as “sound sources.” The idea is to
match the detected sound sources to sound sources that have been detected from
previous sound bursts, while the vehicle was at different positions. If enough
sound sources can be matched, the current position of the vehicle is computed.
This also yields the current attitude of the vehicle in terms of its principal
axes. As the vehicle moves along its path, the algorithm builds a collection
of detected sound sources. From these it is possible to determine the actual
geometry of the walls, but we did not include this step into the formulation
of the algorithm. We view 8 more as a proof-of-concept than a ready-to-use
procedure, as the ideas behind it can be combined with other methods to
improve applicability, accuracy and efficiency. For example, the technical
issues arising from the task of determining arrival times of echoes have been
left out and could be addressed with existing methods from the literature
(e.g., [?cao2020effective]). Also, the matching procedures could be improved
by utilizing more sophisticated SLAM techniques such as graph-based SLAM
[?grisetti2010tutorial].

##  1\. Problem Setup

Consider an environment consisting of finite, planar surfaces in
${\mathbb{R}}^{n}$. A vehicle equipped with four non-coplanar microphones is
moving inside the environment. An omnidirectional loudspeaker is placed at a
position in ${\mathbb{R}}^{n}$ which need not be known. The speaker produces a
series of short high-pitch sounds. The times of the sound emissions are known.
We are assuming that the vehicle is not moving while it is receiving the
echoes of the different walls. The task at hand is to determine the position
and orientation of the vehicle at those moments where it receives the sound.
Thus, we reconstruct the movements of the vehicle at discrete moments along
the path.

Each sound impulse bounces on some of the surfaces and is heard by some
microphones. Using the ray acoustic model, any surface that reflects a sound
impulse can be represented by a “mirror point” (see Figure 2). The mirror
point of a wall is the reflection of the loudspeaker position with respect to
the plane defined by the wall. This point can be viewed as a virtual source of
sound. The set of all sound sources for a given emission thus consists of the
loudspeaker combined with all the virtual sound sources. This is a set of
points whose geometry plays an important role in the following.

##  2\. Breaking symmetries

As explained in the introduction, we wish to put our loudspeaker in a position
such that the mirror points do not display any symmetry, even if the
environment geometry does. An example is shown in Figure 2. The aim in this
section is to show that regardless of the environment geometry, this can be
achieved by a generic choice of the loudspeaker position. This section is
phrased in purely mathematical terms. In particular, the “environment” is now
treated as a finite set of hyperplanes in ${\mathbb{R}}^{n}$.

A hyperplane arrangement, given by a finite set of affine hyperplanes in
${\mathbb{R}}^{n}$, can have symmetries, i.e., nonidentity elements of the
Euclidean group permuting the hyperplanes. Symmetries may be “broken” by
choosing a point in ${\mathbb{R}}^{n}$ (the loudspeaker position in our
application) and then considering all reflections of that point in the
hyperplanes (the “mirror points”), instead of considering the hyperplane
arrangement itself. Can the point be placed such that all symmetries are
broken, and no additional symmetries arise between the reflected points?
Looking at situations such as the one shown in Figure 2, one might expect so,
but at least in dimension two, the answer is not in general, as Remark 2(b)
below shows. However, the following result, Theorem 1, gives a positive answer
in the case of dimension $\geq 3$ (Remark 2(a) makes this precise). Theorem 3
then deals with the two-dimensional case, thus qualifying the observation that
breaking symmetries is in general not possible. The results say that a generic
choice of point breaks all symmetries. In both theorems, the “no symmetries”
statement is made in a strong way: the set of reflections of the chosen point
has no nonidentity isometry. Neither do there exist isometries between subsets
of reflection points, as long as those subsets are geometrically “large
enough.”

In the following, $\operatorname{ref}_{H}(\mathbf{v})$ denotes the reflection
of a point $\mathbf{v}\in{\mathbb{R}}^{n}$ in an affine hyperplane
$H\subset{\mathbb{R}}^{n}$. The point $\mathbf{v}$ can be thought of as the
loudspeaker position, and the $\operatorname{ref}_{H}(\mathbf{v})$ as the
mirror points. In our application, $\mathbf{v}$ together with the
$\operatorname{ref}_{H}(\mathbf{v})$ forms the set of sound sources.

######  Theorem 1.

Let $\mathcal{H}$ be a finite set of affine hyperplanes in ${\mathbb{R}}^{n}$.
Then there is a nonzero polynomial $f\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$ such
that for all $\mathbf{v}\in{\mathbb{R}}^{n}$ with $f(\mathbf{v})\neq 0$ and
for $H_{1},\ldots,H_{m},H^{\prime}_{1},\ldots,H^{\prime}_{m}\in\mathcal{H}$
such that the normal vectors of $H_{1},\ldots,H_{m}$ span a vector space of
dimension $\geq 3$, we have: if the reflections
$\mathbf{w}_{i}:=\operatorname{ref}_{H_{i}}(\mathbf{v})$,
$\mathbf{w}^{\prime}_{i}:=\operatorname{ref}_{H^{\prime}_{i}}(\mathbf{v})$ of
$\mathbf{v}$ satisfy

$\lVert\mathbf{w}_{i}-\mathbf{w}_{j}\rVert=\lVert\mathbf{w}^{\prime}_{i}-\mathbf{w}^{\prime}_{j}\rVert\quad(1\leq
i<j\leq m),$

then $H_{i}=H^{\prime}_{i}$ and therefore
$\mathbf{w}_{i}=\mathbf{w}^{\prime}_{i}$ for all $i$. Moreover, for
$H_{1},H_{2},H_{3}\in\mathcal{H}$ with $H_{1}\neq H_{2}$ we have

$\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}\neq\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}\neq\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\operatorname{ref}_{H_{3}}(\mathbf{v})\bigr{\rVert}.$
(1)

In other words, each distance between $\mathbf{v}$ and a reflection point is
unique among the distances between $\mathbf{v}$ and reflection points and
distances between two reflection points.

The theorem will be proved together with Theorem 3 below.

######  Remark 2.

  1. (a)

A hyperplane arrangement $\mathcal{H}$ in which all the normal vectors of the
hyperplanes are contained in a two-dimensional subspace is itself “morally”
two-dimensional. So let us assume that our hyperplane arrangement has three
hyperplanes with linearly independent normal vectors. Then choosing the
$\mathbf{w}_{i}$ as all the reflections of $\mathbf{v}$ means that the
hypothesis of Theorem 1 is met. So if $\varphi$ is a Euclidean transformation
that permutes the $\mathbf{w}_{i}$, we can apply the theorem to the
$\mathbf{w}_{i}$ and $\mathbf{w}^{\prime}_{i}:=\varphi(\mathbf{w}_{i})$. This
yields $\mathbf{w}_{i}=\mathbf{w}^{\prime}_{i}$, implying that $\varphi$
restricts to the identity on the affine space generated by
$\mathbf{w}_{1},\ldots,\mathbf{w}_{m}$. This makes it precise that
$\mathbf{w}_{1},\ldots,\mathbf{w}_{m}$ have no symmetries.

  2. (b)

Theorem 1 says nothing in the case of dimension $n=2$, since in that case no
hyperplanes $H_{1},\ldots,H_{m}$ can possibly meet the dimension hypothesis on
the normal vectors. In fact, the following construction shows that in
dimension two, breaking symmetries by taking reflections of a point is
impossible for some arrangements of hyperplanes (which in 2D are just lines).
Let $H_{1},\ldots,H_{m}\subset{\mathbb{R}}^{2}$ be lines through the
coordinate origin and let
$\operatorname{rot}_{2\varphi}\in\operatorname{SO}_{2}$ be a rotation about an
angle $2\varphi$, with $\varphi$ not a multiple of $\pi$. We have

$\operatorname{rot}_{2\varphi}\circ\operatorname{ref}_{H_{i}}=\operatorname{rot}_{\varphi}\circ\operatorname{ref}_{H_{i}}\circ\operatorname{ref}_{H_{i}}\circ\operatorname{rot}_{\varphi}\circ\operatorname{ref}_{H_{i}}=\operatorname{rot}_{\varphi}\circ\operatorname{ref}_{H_{i}}\circ\operatorname{rot}_{\varphi}^{-1}=\operatorname{ref}_{\operatorname{rot}_{\varphi}(H_{i})},$
(2)

so it we set $H^{\prime}_{i}:=\operatorname{rot}_{\varphi}(H_{i})$, and, with
$\mathbf{v}\in{\mathbb{R}}^{2}$ arbitrary,
$\mathbf{w}_{i}:=\operatorname{ref}_{H_{i}}(\mathbf{v})$,
$\mathbf{w}^{\prime}_{i}:=\operatorname{ref}_{H^{\prime}_{i}}(\mathbf{v})$,
then

$\lVert\mathbf{w}_{i}-\mathbf{w}_{j}\rVert=\lVert\operatorname{rot}_{2\varphi}(\mathbf{w}_{i})-\operatorname{rot}_{2\varphi}(\mathbf{w}_{j})\rVert\underset{\lx@cref{creftype~refnum}{eqRotRef}}{=}\lVert\mathbf{w}^{\prime}_{i}-\mathbf{w}^{\prime}_{j}\rVert,$

but $H_{i}\neq H^{\prime}_{i}$ and
$\mathbf{w}_{i}\neq\mathbf{w}^{\prime}_{i}$. So the assertion of Theorem 1
fails.

To turn this into an example about symmetries, choose $\varphi=\pi/k$ with
$k\geq 3$ an integer, choose a line $H$ through the origin, and set
$\mathcal{H}:=\\{H_{i}:=\operatorname{rot}_{i\varphi}(H)\mid
i=0,\ldots,k-1\\}$. Then the symmetry group of $\mathcal{H}$ is a dihedral
group of order $4k$, generated by $\operatorname{rot}_{\varphi}$ and
$\operatorname{ref}_{H}$. For the reflections
$\mathbf{w}_{i}=\operatorname{ref}_{H_{i}}(\mathbf{v})$, Equation 2 yields
$\mathbf{w}_{i+1}=\operatorname{rot}_{2\varphi}(\mathbf{w}_{i})$, setting
$\mathbf{w}_{k}:=\mathbf{w}_{0}$. So the $\mathbf{w}_{i}$ form a regular
polygon with $k$ vertices and dihedral symmetry group of order $2k$. Figure 3
shows this for $k=3$.

$H_{1}$$H_{2}$$H_{3}$$\mathbf{v}$$\mathbf{w}_{1}$$\mathbf{w}_{2}$$\mathbf{w}_{3}$

$H_{1}$$H_{2}$$H_{3}$$\mathbf{v}$$\mathbf{w}_{1}$$\mathbf{w}_{2}$$\mathbf{w}_{3}$$\mathbf{m}$

Figure 3. Left: no matter where $\mathbf{v}$ is, its reflections
$\mathbf{w}_{i}$ in the $H_{i}$ always form an equilateral triangle. Right:
the same geometry, but now a microphone position (red) has been introduced and
the hyperplanes have been reduced to limited walls. This shows that the
geometry on the left can be realized in such a way that the echoes can
actually be heard.

Notice that the symmetry of the triangle that swaps $\mathbf{w}_{1}$ and
$\mathbf{w}_{2}$ is new since it is a reflection in a line that is not a
symmetry axis of the hyperplane arrangement. $\triangleleft$

The next result is a variant of Theorem 1 which does work in dimension $2$. It
requires an additional hypothesis on the hyperplane arrangement, which in
dimension $2$ just stipulates that the intersection of three lines in the
arrangement must be empty. So one might say that precisely the situation from
Remark 2(b), shown in Figure 3, is excluded. The additional hypothesis is mild
in the sense that a generic hyperplane arrangement satisfies it. Comparing
Theorems 1 and 3, one sees that the extra hypothesis allows to replace the
“dimension $\geq 3$” in Theorem 1 by “dimension $\geq 2$.” Since
$\lVert\mathbf{w}_{1}-\mathbf{w}_{2}\rVert=\lVert\mathbf{w}^{\prime}_{1}-\mathbf{w}^{\prime}_{2}\rVert$
cannot be enough to conclude $\mathbf{w}_{i}=\mathbf{w}^{\prime}_{i}$, it is
also clear that the hypothesis $\bigl{|}\\{H_{1},\ldots,H_{m}\\}\bigr{|}\geq
3$ is needed in Theorem 3.

######  Theorem 3.

Let $\mathcal{H}$ be a finite set of affine hyperplanes in ${\mathbb{R}}^{n}$
such that no three hyperplanes from $\mathcal{H}$ meet in codimension $2$.
Then there is a nonzero polynomial $f\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$ such
that for all $\mathbf{v}\in{\mathbb{R}}^{n}$ with $f(\mathbf{v})\neq 0$ and
for $H_{1},\ldots,H_{m},H^{\prime}_{1},\ldots,H^{\prime}_{m}\in\mathcal{H}$
such that the normal vectors of $H_{1},\ldots,H_{m}$ span a vector space of
dimension $\geq 2$ and $\bigl{|}\\{H_{1},\ldots,H_{m}\\}\bigr{|}\geq 3$, we
have: if the reflections
$\mathbf{w}_{i}:=\operatorname{ref}_{H_{i}}(\mathbf{v})$,
$\mathbf{w}^{\prime}_{i}:=\operatorname{ref}_{H^{\prime}_{i}}(\mathbf{v})$ of
$\mathbf{v}$ satisfy

$\lVert\mathbf{w}_{i}-\mathbf{w}_{j}\rVert=\lVert\mathbf{w}^{\prime}_{i}-\mathbf{w}^{\prime}_{j}\rVert\quad(1\leq
i<j\leq m),$

then $H_{i}=H^{\prime}_{i}$ and therefore
$\mathbf{w}_{i}=\mathbf{w}^{\prime}_{i}$ for all $i$. Moreover, for
$H_{1},H_{2},H_{3}\in\mathcal{H}$ with $H_{1}\neq H_{2}$ we have

$\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}\neq\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}\neq\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\operatorname{ref}_{H_{3}}(\mathbf{v})\bigr{\rVert}.$
(3)

In other words, each distance between $\mathbf{v}$ and a reflection point is
unique among the distances between $\mathbf{v}$ and reflection points and
distances between two reflection points.

###### Proof of Theorems 1 and 3.

We first need to construct the polynomial $f$. It follows from Lemma 4(a) (see
below this proof) that for hyperplanes $H_{1},H_{2},H_{3}\in\mathcal{H}$, the
polynomial $g_{H_{1},H_{2},H^{\prime}}\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$
given by

$g_{H_{1},H_{2},H_{3}}(\mathbf{v})=\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\operatorname{ref}_{H_{3}}(\mathbf{v})\bigr{\rVert}^{2}-\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}^{2}$

is nonzero. If $H_{1}\neq H_{2}$, there is $\mathbf{v}\in{\mathbb{R}}^{n}$
such that
$\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}\neq\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}$:
one needs to avoid the hyperplane consisting of all points that have equal
distance to $H_{1}$ and $H_{2}$. So the polynomial $h_{H_{1},H_{2}}$ defined
by

$h_{H_{1},H_{2}}(\mathbf{v})=\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}^{2}-\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}^{2}$

also is nonzero. The first part of the construction of $f$ is now given by

$f_{\operatorname{part}1}:=\Biggl{(}\prod_{H_{1},H_{2},H_{3}\in\mathcal{H}}g_{H_{1},H_{2},H_{3}}\Biggr{)}\Biggl{(}\prod_{\begin{subarray}{c}H_{1},H_{2}\in\mathcal{H}\\\
H_{1}\neq H_{2}\end{subarray}}h_{H_{1},H_{2}}\Biggr{)}.$

So if $f_{\operatorname{part}1}(\mathbf{v})\neq 0$ then Equation 1 and
Equation 3 are satisfied.

The second part of the construction of $f$ takes different routes for Theorem
1 or 3. In the following, we will call affine hyperplanes linearly independent
if their normal vectors are linearly independent. It is easy to see that $k$
hyperplanes are linearly independent if and only if they meet in codimension
$k$: just consider the system of linear equations for determining their
intersection.

Case of Theorem 1:

We take three linearly independent hyperplanes
$H_{1},H_{2},H_{3}\in\mathcal{H}$ and three further hyperplanes
$H^{\prime}_{1},H^{\prime}_{2},H^{\prime}_{3}\in\mathcal{H}$ such that

$\bigl{\lVert}\operatorname{ref}_{H_{i}}(\mathbf{v})-\operatorname{ref}_{H_{j}}(\mathbf{v})\bigr{\rVert}=\bigl{\lVert}\operatorname{ref}_{H^{\prime}_{i}}(\mathbf{v})-\operatorname{ref}_{H^{\prime}_{j}}(\mathbf{v})\bigr{\rVert}\quad(1\leq
i<j\leq 3)\quad\text{for all}\ \mathbf{v}\in{\mathbb{R}}^{n}.$

By Lemma 4(b), this implies $H_{i}\cap H_{j}=H^{\prime}_{i}\cap
H^{\prime}_{j}$ for all $i$ and $j$. Writing $\operatorname{Aff}(M)$ for the
affine subspace spanned by some point set $M$ and using the linear
independence of the $H_{i}$, we conclude

$H_{1}=\operatorname{Aff}\bigl{(}(H_{1}\cap H_{2})\cup(H_{1}\cap
H_{3})\bigr{)}=\operatorname{Aff}\bigl{(}(H^{\prime}_{1}\cap
H^{\prime}_{2})\cup(H^{\prime}_{1}\cap H^{\prime}_{3})\bigr{)}\subseteq
H^{\prime}_{1},$

so $H_{1}=H^{\prime}_{1}$. The same argument shows $H_{i}=H^{\prime}_{i}$ for
all $i$. We write this as
$(H_{1},H_{2},H_{3})=(H^{\prime}_{1},H^{\prime}_{2},H^{\prime}_{3})$. Going to
the contrapositive, we have shown that for $H_{1},H_{2},H_{3}\in\mathcal{H}$
linearly independent and for
$H^{\prime}_{1},H^{\prime}_{2},H^{\prime}_{3}\in\mathcal{H}$ with
$(\underline{H}):=(H_{1},H_{2},H_{3})\neq(H^{\prime}_{1},H^{\prime}_{2},H^{\prime}_{3})=:(\underline{H}^{\prime})$,
the polynomial
$f_{\underline{H},\underline{H}^{\prime}}\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$
defined by

$f_{\underline{H},\underline{H}^{\prime}}(\mathbf{v})=\sum_{1\leq i<j\leq
3}\Bigl{(}\bigl{\lVert}\operatorname{ref}_{H_{i}}(\mathbf{v})-\operatorname{ref}_{H_{j}}(\mathbf{v})\bigr{\rVert}^{2}-\bigl{\lVert}\operatorname{ref}_{H^{\prime}_{i}}(\mathbf{v})-\operatorname{ref}_{H^{\prime}_{j}}(\mathbf{v})\bigr{\rVert}^{2}\Bigr{)}^{2}$

is nonzero. We set

$f_{\operatorname{part}2}:=\prod_{\begin{subarray}{c}H_{1},H_{2},H_{3}\in\mathcal{H}\\\
\text{linearly
independent}\end{subarray}}\,\,\,\prod_{\begin{subarray}{c}H^{\prime}_{1},H^{\prime}_{2},H^{\prime}_{3}\in\mathcal{H}\\\
\text{with}(\underline{H})\neq(\underline{H}^{\prime})\end{subarray}}f_{\underline{H},\underline{H}^{\prime}}.$

Case of Theorem 3:

Let $H_{1},H_{2}\in\mathcal{H}$ be linearly independent, which means that they
are not parallel. Then Lemma 4(c) tells us that for
$H^{\prime}_{1},H^{\prime}_{2}\in\mathcal{H}$ with
$\\{H_{1},H_{2}\\}\neq\\{H^{\prime}_{1},H^{\prime}_{2}\\}$ the polynomial
$f_{\underline{H},\underline{H}^{\prime}}$ given by

$f_{\underline{H},\underline{H}^{\prime}}(\mathbf{v})=\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\operatorname{ref}_{H_{2}}(\mathbf{v})\bigr{\rVert}^{2}-\bigl{\lVert}\operatorname{ref}_{H^{\prime}_{1}}(\mathbf{v})-\operatorname{ref}_{H^{\prime}_{2}}(\mathbf{v})\bigr{\rVert}^{2}$

is nonzero. In this case we set

$f_{\operatorname{part}2}:=\prod_{\begin{subarray}{c}H_{1},H_{2}\in\mathcal{H}\\\
\text{linearly
independent}\end{subarray}}\,\,\,\prod_{\begin{subarray}{c}H^{\prime}_{1},H^{\prime}_{2}\in\mathcal{H}\
\text{with}\\\
\\{H_{1},H_{2}\\}\neq\\{H^{\prime}_{1},H^{\prime}_{2}\\}\end{subarray}}f_{\underline{H},\underline{H}^{\prime}}.$

In both cases we set $f:=f_{\operatorname{part}1}\cdot
f_{\operatorname{part}2}$. So $f(\mathbf{v})\neq 0$ implies Equation 1 and
Equation 3.

To prove the other assertions of the theorems, let
$\mathbf{v}\in{\mathbb{R}}^{n}$ with $f(\mathbf{v})\neq 0$ and take
$H_{1},\ldots,H_{m},H^{\prime}_{1},\ldots,H^{\prime}_{m}\in\mathcal{H}$ as in
the theorems such that the
$\mathbf{w}_{i}=\operatorname{ref}_{H_{i}}(\mathbf{v})$ and
$\mathbf{w}^{\prime}_{i}:=\operatorname{ref}_{H^{\prime}_{i}}(\mathbf{v})$
satisfy

$\lVert\mathbf{w}_{i}-\mathbf{w}_{j}\rVert=\lVert\mathbf{w}^{\prime}_{i}-\mathbf{w}^{\prime}_{j}\rVert\quad(1\leq
i<j\leq m).$ (4)

Let $i\in\\{1,\ldots,m\\}$ be arbitrary. We need to show
$H_{i}=H^{\prime}_{i}$. Again the arguments for Theorem 1 and 3 differ.

Case of Theorem 1:

By hypothesis we can choose $j$ and $k$ in $\\{1,\ldots,m\\}$ such that
$H_{i},H_{j},H_{k}$ have linearly independent normal vectors. Assume that
$H_{i}\neq H^{\prime}_{i}$. Then
$f_{H_{i},H_{j},H_{k},H^{\prime}_{i},H^{\prime}_{j},H^{\prime}_{k}}(\mathbf{v})\neq
0$ implies that at least one of the differences
$\lVert\mathbf{w}_{i}-\mathbf{w}_{j}\rVert^{2}-\lVert\mathbf{w}^{\prime}_{i}-\mathbf{w}^{\prime}_{j}\rVert^{2}$,
$\lVert\mathbf{w}_{i}-\mathbf{w}_{k}\rVert^{2}-\lVert\mathbf{w}^{\prime}_{i}-\mathbf{w}^{\prime}_{k}\rVert^{2}$,
or
$\lVert\mathbf{w}_{j}-\mathbf{w}_{k}\rVert^{2}-\lVert\mathbf{w}^{\prime}_{j}-\mathbf{w}^{\prime}_{k}\rVert^{2}$
is nonzero, contradicting Equation 4. We conclude $H_{i}=H^{\prime}_{i}$, as
desired.

Case of Theorem 3:

By hypothesis we can choose $j\in\\{1,\ldots,m\\}$ such that $H_{i},H_{j}$ are
linearly independent. It follows that
$\\{H_{i},H_{j}\\}=\\{H^{\prime}_{i},H^{\prime}_{j}\\}$, since otherwise
$f_{H_{i},H_{j},H^{\prime}_{i},H^{\prime}_{j}}(\mathbf{v})\neq 0$ would imply
$\lVert\mathbf{w}_{i}-\mathbf{w}_{j}\rVert\neq\lVert\mathbf{w}^{\prime}_{i}-\mathbf{w}^{\prime}_{j}\rVert$,
contradicting Equation 4. Also by hypothesis there exists
$k\in\\{1,\ldots,m\\}$ such that $H_{i}\neq H_{k}\neq H_{j}$. $H_{k}$ cannot
be parallel to both $H_{i}$ and $H_{j}$. So $H_{i}$ and $H_{k}$ or $H_{j}$ and
$H_{k}$ are linearly independent. In the first case, we get, as above,
$\\{H_{i},H_{k}\\}=\\{H^{\prime}_{i},H^{\prime}_{k}\\}$, and in the second
case we get $\\{H_{j},H_{k}\\}=\\{H^{\prime}_{j},H^{\prime}_{k}\\}$. But
either case, together with
$\\{H_{i},H_{j}\\}=\\{H^{\prime}_{i},H^{\prime}_{j}\\}$, implies
$H_{i}=H^{\prime}_{i}$, $H_{j}=H^{\prime}_{j}$ and $H_{k}=H^{\prime}_{k}$.

In both cases we have seen that $H_{i}=H^{\prime}_{i}$, which finishes the
proof. ∎

The following lemma was used in the above proof.

######  Lemma 4.

Assume the hypotheses of Theorem 1.

  1. (a)

Let $H_{1},H_{2},H_{3}\in\mathcal{H}$. Then there exists
$\mathbf{v}\in{\mathbb{R}}^{n}$ such that
$\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\operatorname{ref}_{H_{3}}(\mathbf{v})\bigr{\rVert}\neq\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}$.

  2. (b)

Let $H_{1},H_{2},H^{\prime}_{1},H^{\prime}_{2}\in\mathcal{H}$. If
$\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\operatorname{ref}_{H_{2}}(\mathbf{v})\bigr{\rVert}=\bigl{\lVert}\operatorname{ref}_{H^{\prime}_{1}}(\mathbf{v})-\operatorname{ref}_{H^{\prime}_{2}}(\mathbf{v})\bigr{\rVert}$
for all $\mathbf{v}\in{\mathbb{R}}^{n}$, then either $H_{1}\cap
H_{2}=H^{\prime}_{1}\cap H^{\prime}_{2}$, or $H_{1}=H_{2}$ and
$H^{\prime}_{1}=H^{\prime}_{2}$.

  3. (c)

Under the hypotheses of Theorem 3, the assertion of part (b) can be sharpened
as follows: either $\\{H_{1},H_{2}\\}=\\{H^{\prime}_{1},H^{\prime}_{2}\\}$, or
$H_{1}$ is parallel to $H_{2}$ and so is $H^{\prime}_{1}$ to $H^{\prime}_{2}$.

###### Proof.

  1. (b)

Take $\mathbf{v}\in H_{1}\cap H_{2}$. Then
$\operatorname{ref}_{H_{1}}(\mathbf{v})=\mathbf{v}=\operatorname{ref}_{H_{2}}(\mathbf{v})$,
so
$\operatorname{ref}_{H^{\prime}_{1}}(\mathbf{v})=\operatorname{ref}_{H^{\prime}_{2}}(\mathbf{v})=:\mathbf{w}$
by hypothesis. If $\mathbf{w}=\mathbf{v}$, this implies $\mathbf{v}\in
H^{\prime}_{1}\cap H^{\prime}_{2}$. On the other hand, if
$\mathbf{w}\neq\mathbf{v}$, then $H^{\prime}_{1}$ consists of all points that
have equal distance to $\mathbf{v}$ and to $\mathbf{w}$, and the same for
$H^{\prime}_{2}$; hencce $H^{\prime}_{1}=H^{\prime}_{2}$. We conclude that
either $H_{1}\cap H_{2}\subseteq H^{\prime}_{1}\cap H^{\prime}_{2}$ or
$H^{\prime}_{1}=H^{\prime}_{2}$. From this part (b) follows by reversing the
roles of the $H_{i}$ and the $H^{\prime}_{i}$.

  2. (c)

The assertion of part (b) holds, but now we have the additional hypothesis of
Theorem 3. Assume that $H_{1}$ is not parallel to $H_{2}$, which implies
$H_{1}\neq H_{2}$, and also that $H_{1}\cap H_{2}$ is nonempty of codimension
$2$. So part (b) yields $H_{1}\cap H_{2}=H^{\prime}_{1}\cap H^{\prime}_{2}$.
This implies that $H^{\prime}_{1}$ is not parallel to $H^{\prime}_{2}$, and
that the intersection of all four hyperplanes has codimension $2$. So by the
hypothesis of Theorem 3, these four hyperplanes are in fact only two
(distinct) ones, so $\\{H_{1},H_{2}\\}=\\{H^{\prime}_{1},H^{\prime}_{2}\\}$.

  3. (a)

Assume
$\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v})-\operatorname{ref}_{H_{3}}(\mathbf{v})\bigr{\rVert}=\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v})-\mathbf{v}\bigr{\rVert}$
for all $\mathbf{v}\in{\mathbb{R}}^{n}$. Then in particular for $\mathbf{v}\in
H_{2}$ this implies
$\operatorname{ref}_{H_{1}}(\mathbf{v})=\operatorname{ref}_{H_{3}}(\mathbf{v})$.
As in the proof of part (b), either $\mathbf{v}\in H_{1}\cap H_{3}$ or
$H_{1}=H_{3}$ follows. But the latter is impossible since it would imply
$\bigl{\lVert}\operatorname{ref}_{H_{1}}(\mathbf{v}^{\prime})-\operatorname{ref}_{H_{3}}(\mathbf{v}^{\prime})\bigr{\rVert}=0\neq\bigl{\lVert}\operatorname{ref}_{H_{2}}(\mathbf{v}^{\prime})-\mathbf{v}^{\prime}\bigr{\rVert}$
for $\mathbf{v}^{\prime}\notin H_{2}$, contradicting our assumption. So we
conclude $H_{2}\subseteq H_{1}\cap H_{3}$. But an affine hypersurface cannot
be contained in the intersection of two affine hypersurfaces unless they are
equal, which we have already excluded. So our assumption leads to an
unescapable contradiction. ∎

##  3\. The Cayley-Menger matrix and affine subspaces

This section introduces some geometric tools that will be needed in Section 4.

For vectors (or “points”) $\mathbf{v}_{0},\ldots,\mathbf{v}_{m}\in V$ in a
vector space over a field $K$, recall that the affine subspace spanned by
them, written here as
$\operatorname{Aff}(\mathbf{v}_{0},\ldots,\mathbf{v}_{m})$, is the subset of
$V$ consisting of all linear combinations
$\sum_{i=0}^{m}\alpha_{i}\mathbf{v}_{i}$ with $\sum_{i=0}^{m}\alpha_{i}=1$.
Its dimension is defined to be the dimension of the associated linear space,
which consists of all linear combinations with $\sum_{i=0}^{m}\alpha_{i}=0$,
and which is generated by the differences $\mathbf{v}_{i}-\mathbf{v}_{0}$.

If $V$ is a Euclidean space, the Cayley-Menger matrix (see ?Cayley:1841
[?Cayley:1841]) of the $\mathbf{v}_{i}$ is

$C:=\begin{pmatrix}0&1&1&1&\cdots&1\\\ 1&0&D_{0,1}&D_{0,2}&\cdots&D_{0,m}\\\
1&D_{1,0}&0&D_{1,2}&\cdots&D_{1,m}\\\ 1&D_{2,0}&D_{2,1}&0&\cdots&D_{2,m}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&D_{m,0}&D_{m,1}&D_{m,2}&\cdots&0\end{pmatrix}\in{\mathbb{R}}^{(m+2)\times(m+2)}$
(5)

with $D_{i,j}:=\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert^{2}$. For ease of
talking about the rank of the Cayley-Menger matrix and some other matrices, we
find it convenient to introduce the bordered rank of a matrix $M$ as

$\operatorname{b-rank}(M):=\operatorname{rank}\left(\begin{array}[]{c|ccc}0&1&\cdots&1\\\
\hline\cr 1\\\ \vdots&&M\\\ 1\end{array}\right)-2.$ (6)

The following results are likely to be folklore, but we could not find a
reference in the literature.

######  Proposition 5.

Let $\mathbf{v}_{0},\ldots,\mathbf{v}_{m}\in V$ be points in a Euclidean space
and set $A:=\operatorname{Aff}(\mathbf{v}_{0},\ldots,\mathbf{v}_{m})$.

  1. (a)

With $D_{i,j}:=\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert^{2}$ we have

$\operatorname{b-rank}\bigl{(}D_{i,j}\bigr{)}_{i,j=0,\ldots,m}=\operatorname{b-rank}\bigl{(}\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle\bigr{)}_{i,j=0,\ldots,m}=\\\
\operatorname{rank}\bigl{(}\langle\mathbf{v}_{i}-\mathbf{v}_{0},\mathbf{v}_{j}-\mathbf{v}_{0}\rangle\bigr{)}_{i,j=1,\ldots,m}=\dim(A).$

In particular, the Cayley-Menger matrix has rank equal to $\dim(A)+2$.

  2. (b)

A point $\mathbf{w}\in A$ is uniquely determined by the distances between
$\mathbf{w}$ and the $\mathbf{v}_{i}$. More specifically, assume, after
possibly renumbering the $\mathbf{v}_{i}$, that
$A=\operatorname{Aff}(\mathbf{v}_{0},\ldots,\mathbf{v}_{n})$ with $n=\dim(A)$.
Then with $d_{i}:=\lVert\mathbf{w}-\mathbf{v}_{i}\rVert^{2}$ and

$I:=\begin{pmatrix}0&1&\cdots&1\\\
1&\langle\mathbf{v}_{0},\mathbf{v}_{0}\rangle&\cdots&\langle\mathbf{v}_{0},\mathbf{v}_{n}\rangle\\\
\vdots&\vdots&&\vdots\\\
1&\langle\mathbf{v}_{n},\mathbf{v}_{0}\rangle&\cdots&\langle\mathbf{v}_{n},\mathbf{v}_{n}\rangle\end{pmatrix}\in{\mathbb{R}}^{(n+2)\times(n+2)},$
(7)

the $\alpha_{i}$ given by

$\begin{pmatrix}\alpha_{0}\\\ \vdots\\\
\alpha_{n}\end{pmatrix}:=\begin{pmatrix}0&1/2&&\\\ \vdots&&\ddots\\\
0&&&1/2\end{pmatrix}I^{-1}\begin{pmatrix}2\\\
\lVert\mathbf{v}_{0}\rVert^{2}-d_{0}\\\ \vdots\\\
\lVert\mathbf{v}_{n}\rVert^{2}-d_{n}\end{pmatrix}$ (8)

satisfy $\mathbf{w}=\sum_{i=0}^{n}\alpha_{i}\mathbf{v}_{i}$ and
$\sum_{i=0}^{n}\alpha_{i}=1$.

######  Remark 6.

A generalized version of 5(a) concerns the situation where $V$ is a vector
space over a field $K$ of characteristic $\neq 2$ equipped with a quadratic
form $q$. Then the above rank formula holds with
$D_{i,j}:=q(\mathbf{v}_{i}-\mathbf{v}_{j})$ and $\langle\cdot,\cdot\rangle$
the bilinear form associated to $q$, and furthermore with $\dim(A)$ replaced
by $\operatorname{rank}(q|_{{}_{U}})$, the rank of $q$ restricted to the
linear space associated to $A$. $\triangleleft$

###### Proof of 5 and 6.

We start with proving Remark 6, from which 5(a) follows as a special case.
Form the matrix $I\in K^{(m+2)\times(m+2)}$ as in Equation 7, using all the
vectors $\mathbf{v}_{0},\ldots,\mathbf{v}_{m}$, not just the first $n$ of
them. Now subtract the second row of $I$ from every row below it, and then the
second column from every column to the right of it. The result is the matrix

$\widetilde{I}=\left(\begin{array}[]{cc|ccc}0&1&0&\cdots&0\\\
1&\ast&\ast&\cdots&\ast\\\ \hline\cr 0&\ast\\\ \vdots&\vdots&&G\\\
0&\ast\end{array}\right),$

where the stars stand for entries that we do not need to specify, and the
$(i,j)$-th entry of $G\in K^{m\times m}$ is

$\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle-\langle\mathbf{v}_{0},\mathbf{v}_{j}\rangle-\langle\mathbf{v}_{i},\mathbf{v}_{0}\rangle+\langle\mathbf{v}_{0},\mathbf{v}_{0}\rangle=\langle\mathbf{v}_{i}-\mathbf{v}_{0},\mathbf{v}_{j}-\mathbf{v}_{0}\rangle.$
(9)

We have

$\operatorname{b-rank}\bigl{(}\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle\bigr{)}_{i,j=0,\ldots,m}=\operatorname{rank}(I)-2=\operatorname{rank}(\widetilde{I})-2=\operatorname{rank}(G),$

so the second equation in the formula in 5(a) is proved. We can also start
with the Cayley-Menger matrix $C$ (see Equation 5) with
$D_{i,j}:=q(\mathbf{v}_{i}-\mathbf{v}_{j})$, and perform the same row and
column operations that we performed on $I$. The resulting matrix is

$\widetilde{C}=\left(\begin{array}[]{cc|ccc}0&1&0&\cdots&0\\\
1&\ast&\ast&\cdots&\ast\\\ \hline\cr 0&\ast\\\ \vdots&\vdots&&H\\\
0&\ast\end{array}\right),$

where the $(i,j)$-th entry of $H\in K^{m\times m}$ is

$D_{i,j}-D_{0,j}-D_{i,0}=\langle\mathbf{v}_{i}-\mathbf{v}_{j},\mathbf{v}_{i}-\mathbf{v}_{j}\rangle-\langle\mathbf{v}_{0}-\mathbf{v}_{j},\mathbf{v}_{0}-\mathbf{v}_{j}\rangle-\langle\mathbf{v}_{i}-\mathbf{v}_{0},\mathbf{v}_{i}-\mathbf{v}_{0}\rangle=\\\
-2\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle+2\langle\mathbf{v}_{0},\mathbf{v}_{j}\rangle+2\langle\mathbf{v}_{i},\mathbf{v}_{0}\rangle-2\langle\mathbf{v}_{0},\mathbf{v}_{0}\rangle,$

so $H=-2G$ by Equation 9. As above, we get
$\operatorname{b-rank}\bigl{(}D_{i,j}\bigr{)}_{i,j=0,\ldots,m}=\operatorname{rank}(G)$,
and the second equation in the formula in 5(a) follows.

It remains to show that
$\operatorname{rank}(G)=\operatorname{rank}(q|_{{}_{U}})$. Replacing every
$\mathbf{v}_{i}$ by $\mathbf{v}_{i}-\mathbf{v}_{0}$ does not change $G$ or the
subspace $U$, so making this replacement we may assume $\mathbf{v}_{0}=0$. Now
$U$ is generated (as a vector space) by the $\mathbf{v}_{i}$, and we may also
replace $V$ by $U$. Since $V$ is now finite-dimensional we may assume
$V=K^{n}$. So we have
$\langle\mathbf{v},\mathbf{w}\rangle=\mathbf{v}^{T}A\mathbf{w}$ with $A\in
K^{n\times n}$ symmetric, and
$\operatorname{rank}(A)=\operatorname{rank}(q)=\operatorname{rank}(q|_{{}_{U}})$.
So we need to show $\operatorname{rank}(G)=\operatorname{rank}(A)$.

By Equation 9 and since $\mathbf{v}_{0}=0$, the entries of $G$ are the
$\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle$, so With
$E:=(\mathbf{v}_{1}|\mathbf{v}_{2}|\cdots|\mathbf{v}_{m})\in K^{n\times m}$ we
have $G=E^{T}AE$. Since the $\mathbf{v}_{i}$ generate $V$, $E$ has rank $n$,
so the linear map $K^{m}\to K^{n}$ defined by $E$ is surjective. Likewise, the
linear map $K^{n}\to K^{m}$ defined by $E^{T}$ is injective, so the map given
by $E^{T}AE=G$ has an image of dimension equal to $\operatorname{rank}(A)$.
This shows $\operatorname{rank}(G)=\operatorname{rank}(A)$, so the proof of
Remark 6 and 5(a) is finished.

Now we prove 5(b). The hypothesis $\mathbf{w}\in A$ implies that there exist
$\alpha_{0},\ldots,\alpha_{n}\in{\mathbb{R}}$ such that
$\mathbf{w}=\sum_{i=0}^{n}\alpha_{i}\mathbf{v}_{i}$ and
$\sum_{i=0}^{n}\alpha_{i}=1$. With $I$ as defined in Equation 7, we get

$I\cdot\begin{pmatrix}-\lVert\mathbf{w}\rVert^{2}\\\ 2\alpha_{0}\\\ \vdots\\\
2\alpha_{n}\end{pmatrix}=\begin{pmatrix}2\\\
-\lVert\mathbf{w}\rVert^{2}+2\langle\mathbf{v}_{0},\mathbf{w}\rangle\\\
\vdots\\\
-\lVert\mathbf{w}\rVert^{2}+2\langle\mathbf{v}_{n},\mathbf{w}\rangle\end{pmatrix}=\begin{pmatrix}2\\\
\lVert\mathbf{v}_{0}\rVert^{2}-\lVert\mathbf{w}-\mathbf{v}_{0}\rVert^{2}\\\
\vdots\\\
\lVert\mathbf{v}_{n}\rVert^{2}-\lVert\mathbf{w}-\mathbf{v}_{n}\rVert^{2}\end{pmatrix}=\begin{pmatrix}2\\\
\lVert\mathbf{v}_{0}\rVert^{2}-d_{0}\\\ \vdots\\\
\lVert\mathbf{v}_{n}\rVert^{2}-d_{n}\end{pmatrix}$

Since $I$ is invertible by 5(a), the desired equation Equation 8 follows from
this. ∎

If we have points $\mathbf{v}_{0},\ldots,\mathbf{v}_{n}$ in an $n$-dimensional
Euclidean space $V$ not lying in a proper affine subspace (i.e.,
$V=\operatorname{Aff}(\mathbf{v}_{0},\ldots,\mathbf{v}_{n})$), then by 5(b)
any $\mathbf{w}\in V$ can determined from the distances
$\lVert\mathbf{w}-\mathbf{v}_{i}\rVert$. Given several such points
$\mathbf{w}_{1},\ldots,\mathbf{w}_{m}$, their mutual distances
$\lVert\mathbf{w}_{i}-\mathbf{w}_{j}\rVert$ can then be worked out. The
following result allows the computation of the mutual distances in a direct
way, and without any knowledge of the $\mathbf{v}_{i}$; only the distances
between them are needed.

######  Proposition 7.

Let $\mathbf{v}_{0},\ldots,\mathbf{v}_{n}\in V$ be points in an
$n$-dimensional Euclidean space that do not lie in a proper affine subspace,
and let $C\in{\mathbb{R}}^{(n+2)\times(n+2)}$ be their Cayley-Menger matrix.
Let $\mathbf{w}_{1},\ldots,\mathbf{w}_{m}\in V$ be further points and form the
matrix $\Delta\in{\mathbb{R}}^{(n+2)\times m}$ whose $i$-th column is
$\bigl{(}1,\lVert\mathbf{w}_{i}-\mathbf{v}_{0}\rVert^{2},\ldots,\lVert\mathbf{w}_{i}-\mathbf{v}_{n}\rVert^{2})^{T}$.
Then we have

$\begin{pmatrix}0&\lVert\mathbf{w}_{1}-\mathbf{w}_{2}\rVert^{2}&\lVert\mathbf{w}_{1}-\mathbf{w}_{3}\rVert^{2}&\cdots&\lVert\mathbf{w}_{1}-\mathbf{w}_{m}\rVert^{2}\\\
\lVert\mathbf{w}_{2}-\mathbf{w}_{1}\rVert^{2}&0&\lVert\mathbf{w}_{2}-\mathbf{w}_{3}\rVert^{2}&\cdots&\lVert\mathbf{w}_{2}-\mathbf{w}_{m}\rVert^{2}\\\
\lVert\mathbf{w}_{3}-\mathbf{w}_{1}\rVert^{2}&\lVert\mathbf{w}_{3}-\mathbf{w}_{2}\rVert^{2}&0&\cdots&\lVert\mathbf{w}_{3}-\mathbf{w}_{m}\rVert^{2}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
\lVert\mathbf{w}_{m}-\mathbf{w}_{1}\rVert^{2}&\lVert\mathbf{w}_{m}-\mathbf{w}_{2}\rVert^{2}&\lVert\mathbf{w}_{m}-\mathbf{w}_{2}\rVert^{2}&\cdots&0\end{pmatrix}=\Delta^{T}C^{-1}\Delta.$
(10)

###### Proof.

By 5(a), $C$ has rank $n+2$, so $C^{-1}$ exists. Let us first consider the
case of two points $\mathbf{w},\mathbf{w}^{\prime}\in V$. For ease of notation
write $d_{i}:=\lVert\mathbf{w}-\mathbf{v}_{i}\rVert^{2}$,
$e_{i}:=\lVert\mathbf{w}^{\prime}-\mathbf{v}_{i}\rVert^{2}$, and
$f:=\lVert\mathbf{W}-\mathbf{w}^{\prime}\rVert^{2}$. So with
$D_{i,j}:=\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert^{2}$, the Cayley-Menger
matrix of the points
$\mathbf{v}_{0},\ldots,\mathbf{v}_{n},\mathbf{w},\mathbf{w}^{\prime}$ is

$\widetilde{C}=\begin{pmatrix}0&1&1&\cdots&1&1&1\\\
1&0&D_{0,1}&\cdots&D_{0,n}&d_{0}&e_{0}\\\
1&D_{1,0}&0&\cdots&D_{1,n}&d_{1}&e_{1}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
1&D_{n,0}&D_{n,1}&\cdots&0&d_{n}&e_{n}\\\ 1&d_{0}&d_{1}&\cdots&d_{n}&0&f\\\
1&e_{0}&e_{1}&\cdots&e_{n}&f&0\end{pmatrix}=\left(\begin{array}[]{ccccc|cc}&&&&&1&1\\\
&&&&&d_{0}&e_{0}\\\ &&C&&&d_{1}&e_{1}\\\ &&&&&\vdots&\vdots\\\
&&&&&d_{n}&e_{n}\\\ \hline\cr 1&d_{0}&d_{1}&\cdots&d_{n}&0&f\\\
1&e_{0}&e_{1}&\cdots&e_{n}&f&0\end{array}\right).$

We have

$\begin{pmatrix}1&d_{0}&d_{1}&\cdots&d_{n}\\\
1&e_{0}&e_{1}&\cdots&e_{n}\end{pmatrix}=\left(\begin{pmatrix}1&d_{0}&d_{1}&\cdots&d_{n}\\\
1&e_{0}&e_{1}&\cdots&e_{n}\end{pmatrix}C^{-1}\right)\cdot C,$

which tells us how the rows in the block below $C$ can be written in a unique
way as a linear combination of the rows of $C$. Since
$\operatorname{rank}(\widetilde{C})=\operatorname{rank}(C)$ (again by 5(a)),
the same linear combination of the $n+2$ upper rows must represent the two
bottom rows. Therefore

$\begin{pmatrix}0&f\\\
f&0\end{pmatrix}=\begin{pmatrix}1&d_{0}&d_{1}&\cdots&d_{n}\\\
1&e_{0}&e_{1}&\cdots&e_{n}\end{pmatrix}C^{-1}\begin{pmatrix}1&1\\\
d_{0}&e_{0}\\\ d_{1}&e_{1}\\\ \vdots&\vdots\\\ d_{n}&e_{n}\end{pmatrix}.$

We obtain

$\lVert\mathbf{w}-\mathbf{w}^{\prime}\rVert^{2}=f=\begin{pmatrix}1&d_{0}&d_{1}&\cdots&d_{n}\end{pmatrix}\cdot
C^{-1}\cdot\begin{pmatrix}1\\\ e_{0}\\\ e_{1}\\\ \vdots\\\
e_{n}\end{pmatrix}=\begin{pmatrix}1\\\
\lVert\mathbf{w}-\mathbf{v}_{0}\rVert^{2}\\\
\lVert\mathbf{w}-\mathbf{v}_{1}\rVert^{2}\\\ \vdots\\\
\lVert\mathbf{w}-\mathbf{v}_{n}\rVert^{2}\end{pmatrix}^{T}C^{-1}\begin{pmatrix}1\\\
\lVert\mathbf{w}^{\prime}-\mathbf{v}_{0}\rVert^{2}\\\
\lVert\mathbf{w}^{\prime}-\mathbf{v}_{1}\rVert^{2}\\\ \vdots\\\
\lVert\mathbf{w}^{\prime}-\mathbf{v}_{n}\rVert^{2}\end{pmatrix}.$

Since this holds for any two points $\mathbf{w}$ and $\mathbf{w}^{\prime}$,
the equation Equation 10 follows. ∎

##  4\. A Reconstruction Algorithm for the Vehicle Path and Source Position

In this section we present an algorithm that is run each time a loudspeaker
emits a sound signal as the vehicle moves along a path. The vehicle, on which
the data is acquired and the computations are performed, is assumed to know
when the signal is emitted. For example, the vehicle and the loudspeaker might
share a common clock and follow a predetermined signal firing schedule, or
they might be connected so that the vehicle can tell the loudspeaker when to
emit a signal. However, the vehicle does not need to know the loudspeaker
position.

When possible, the algorithm computes the position of the vehicle at the time
where the sound is emitted by the loudspeaker. It also computes the position
of the sound sources (mirror points or loudspeaker) that were heard by the
four microphones. Over time, the list of reconstructed sources grows to
include more and more sources as they are being discovered.

When for the first time at least four noncoplanar sound sources have been
detected, their positions are stored relative to a coordinate system that is
defined by the current location of the vehicle. This coordinate system will be
frozen and used at all times. In each subsequent call, the algorithm seeks to
match at least four noncoplanar detected sound sources with sound sources that
have previously been detected. This enables the algorithm to determine the
vehicle position, and express the positions of the newly detected sound
sources in terms of the coordinate system that has been frozen before. If
desired, the frozen coordinate system can later be recalibrated to some other
coordinate system.

######  Algorithm 8 (Self-location and detecting environment geometry).

Input (optional):

A list of points $\mathbf{s}_{1},\ldots,\mathbf{s}_{n}\in{\mathbb{R}}^{3}$,
which are known positions of sound sources. The $\mathbf{s}_{i}$ may not be
coplanar, so in particular $n\geq 4$. The list of $\mathbf{s}_{i}$ is either
taken from previous runs of the algorithm or passed to it after preparing the
room in the room-coordinates scenario (see above).

In both scenarios it is assumed that the algorithm knows the coordinate
vectors $\mathbf{m}_{1},\ldots,\mathbf{m}_{4}\in{\mathbb{R}}^{3}$ of the
positions of the microphones with respect to the coordinate system given by
the principal axes (roll, pitch and yaw) of the vehicle.

Output:

In case of success, the output consists of:

  1. (a):

an updated list of known positions of sound sources $\mathbf{s}_{i}$, which
can be used as input for the next call, and,

  2. (b):

if input was provided: the present location of the vehicle, given by the
position $\mathbf{v}\in{\mathbb{R}}^{3}$ of its center of mass and by a matrix
in $A\in\operatorname{O}_{3}({\mathbb{R}})$ whose columns give the present
directions of the principal axes. (If no input was provided, the output
consists only of what is described in (a).)

If unsuccessful, the algorithm returns “FAIL.” In this case, the list of known
sound sources from the last successful call remains unchanged and should be
used for the next call.

  1. (1)

Data collection: After a sound has been emitted by the loudspeaker, for each
$i=1,\ldots,4$ record the signals from this sound and its first-order echoes
as received by the $i$-th microphone. From the times of reception, calculate
the distances travelled by the signals from emission to reception, and for
each microphone collect the squares of these distances in a set
$\mathcal{D}_{i}$.

  2. (2)

Echo matching: With $f_{D}(x_{1},x_{2},x_{3},x_{4})$ given by Equation
Equation 11 below, form the matrix $\Delta\in{\mathbb{R}}^{4\times m}$ whose
columns are the $(d_{1},d_{2},d_{3},d_{4})^{T}$ such that
$f_{D}(d_{1},d_{2},d_{3},d_{4})=0$, where $(d_{1},\ldots,d_{4})$ ranges
through the cartesian product
$\mathcal{D}_{1}\times\cdots\times\mathcal{D}_{4}$. Then the columns of
$\Delta$ correspond to the detected sound sources, and in each column the
$i$-th entry is the squared distance between the $i$-th microphone and the
sound source.

  3. (3)

Compute the distance matrix: With $\Delta_{i,j}$ the entries of $\Delta$, form
the matrix

$\overline{\Delta}:=\left(\begin{array}[]{ccc}1&\cdots&1\\\
\Delta_{1,1}&\cdots&\Delta_{1,m}\\\ \vdots&&\vdots\\\
\Delta_{4,1}&\cdots&\Delta_{4,m}\end{array}\right)\in{\mathbb{R}}^{5\times
m}.$

With $C\in{\mathbb{R}}^{5\times 5}$ the Cayley-Menger matrix of the
$\mathbf{m}_{i}$ given in Equation Equation 5, compute the matrix

$D^{\operatorname{detected}}:=\overline{\Delta}^{T}C^{-1}\overline{\Delta}\in{\mathbb{R}}^{m\times
m}.$

Then $D^{\operatorname{detected}}$ stores the squared distances between the
detected sound sources.

  4. (4)

Case distinctions: If $\operatorname{b-rank}(D^{\operatorname{detected}})<3$
(see Equation 6 for the definition of the bordered rank), return “FAIL” and
skip the remaining steps. The condition on the bordered rank means that the
detected sound sources are coplanar.

If no points $\mathbf{s}_{i}$ have been passed as input to the algorithm, set
$\mathbf{b}_{i}:=\mathbf{m}_{i}$ ($i=1,\ldots,4$) and go to step (7).

  5. (5)

Submatrix Matching: Form the matrix
$D^{\operatorname{known}}\in{\mathbb{R}}^{n\times n}$ with entries
$\lVert\mathbf{s}_{i}-\mathbf{s}_{j}\rVert^{2}$.

If possible, find indices $i_{1},\ldots,i_{4}\in\\{1,\ldots,m\\}$ and
$j_{1},\ldots,j_{4}\in\\{1,\ldots,n\\}$ such that, with notation explained
below,

$D^{\operatorname{detected}}_{i_{1},\ldots,i_{4}}=D^{\operatorname{known}}_{j_{1},\ldots,j_{4}}$

and such that
$\operatorname{b-rank}(D^{\operatorname{detected}}_{i_{1},\ldots,i_{4}})=3$.
See 10 below for an efficient way to find the $i$’s and $j$’s.

If no such $i_{1},\ldots,i_{4}$ and $j_{1},\ldots,j_{4}$ exist, return “FAIL”
and skip the remaining steps of the algorithm.

If they do exist, the mutual distances between the known points
$\mathbf{s}_{j_{1}},\ldots,\mathbf{s}_{j_{4}}$ are the same as the mutual
distances between the detected points corresponding to the columns of $\Delta$
with numbers $i_{1},\ldots,i_{4}$. The remaining steps work with the
assumption that these detected points are
$\mathbf{s}_{j_{1}},\ldots,\mathbf{s}_{j_{4}}$. Set
$\mathbf{b}_{i}:=\mathbf{s}_{j_{i}}$ ($i=1,\ldots,4$).

  6. (6)

Self-locating: Set

$M:=\left(\begin{array}[]{cccc}\mathbf{m}_{1}&\mathbf{m}_{2}&\mathbf{m}_{3}&\mathbf{m}_{4}\\\
\hline\cr 1&1&1&1\end{array}\right)\in{\mathbb{R}}^{4\times 4}.$

and let $B\in{\mathbb{R}}^{3\times 4}$ be the upper $3\times 4$-part of the
transpose-inverse

$\left(\begin{array}[]{cccc}\mathbf{b}_{1}&\mathbf{b}_{2}&\mathbf{b}_{3}&\mathbf{b}_{4}\\\
\hline\cr 1&1&1&1\end{array}\right)^{-T}\in{\mathbb{R}}^{4\times 4}.$

Compute

$\bigl{(}A\mid\mathbf{v}\bigr{)}:=\frac{1}{2}B\cdot\left(\lVert\mathbf{b}_{j}\rVert^{2}-\Delta_{k,i_{j}}\right)_{j,k=1,\ldots,4}\cdot
M^{-1}$

with $A\in{\mathbb{R}}^{3\times 3}$ and $\mathbf{v}\in{\mathbb{R}}^{3}$. Then,
as we will see in the proof of Theorem 9, $\mathbf{v}$ is the present position
of the vehicle’s center of mass, $A\in\operatorname{O}_{3}({\mathbb{R}})$, and
the columns of $A$ give the present directions of its principal axes.

To prepare for step (7), set
$\Delta_{j,k}:=D^{\operatorname{detected}}_{i_{j},k}$, the $(i_{j},k)$-entry
of $D^{\operatorname{detected}}$ ($j=1,\ldots,4$, $k=1,\ldots,m$). This is the
squared distance between $\mathbf{b}_{j}$ and the $k$-th detected point.

Return $\mathbf{v}$ and $A$ (as the output described in (b)), and continue
with step (7).

  7. (7)

Knowledge update: With $B$ defined as in step (6), compute the points

$\mathbf{t}_{k}:=\frac{1}{2}B\cdot\begin{pmatrix}\lVert\mathbf{b}_{1}\rVert^{2}-\Delta_{1,k}\\\
\vdots\\\ \lVert\mathbf{b}_{4}\rVert^{2}-\Delta_{4,k}\end{pmatrix}$

($k=1,\ldots,m$). As shown in the proof of Theorem 9, these are the detected
sound sources. Update the list $\mathbf{s}_{1},\ldots,\mathbf{s}_{n}$ by
adding those $\mathbf{t}_{k}$ that are not equal to one of the
$\mathbf{s}_{i}$.

Return the updated list of $\mathbf{s}_{i}$ as the output described in (a).

In the following we explain some notation used in the algorithm and make some
remarks.

Step (2):

From the coordinate vectors $\mathbf{m}_{i}$ of the microphone positions, the
algorithm can compute their squared mutual distances
$D_{i,j}=\lVert\mathbf{m}_{i}-\mathbf{m}_{j}\rVert^{2}$. From these, it can
form the Cayley-Menger matrix $C\in{\mathbb{R}}^{5\times 5}$ according to
Equation 5 and the Cayley-Menger polynomial

$f_{D}(x_{1},x_{2},x_{3},x_{4})=\det\left(\begin{array}[]{ccccc|cc}&&&&&1\\\
&&&&&x_{1}\\\ &&C&&&x_{2}&\\\ &&&&&x_{3}\\\ &&&&&x_{4}\\\ \hline\cr
1&x_{1}&x_{2}&x_{3}&x_{4}&0\end{array}\right).$ (11)

Step (5):

If $i_{1},\ldots,i_{r}\in\\{1,\ldots,m\\}$, we write
$D_{i_{1},\ldots,i_{r}}\in{\mathbb{R}}^{r\times r}$ is the submatrix obtained
by selecting the rows and columns with indices $i_{1},\ldots,i_{r}$, or more
formally
$D_{i_{1},\ldots,i_{r}}:=\bigl{(}d_{i_{j},i_{k}}\bigr{)}_{j,k=1,\ldots,r}$.

Step (6):

From the matrix $A=\left(\begin{smallmatrix}a_{1,1}&a_{1,2}&a_{1,3}\\\
a_{2,1}&a_{2,2}&a_{2,3}\\\ a_{3,1}&a_{3,2}&a_{3,3}\end{smallmatrix}\right)$,
the present yaw, pitch and roll angles $\alpha$, $\beta$ and $\gamma$,
respectively, can be easily determined by the well-known formulas

$\alpha=\operatorname{atan2}(a_{2,1},a_{1,1}),\quad\beta=-\arcsin(a_{3,1})\quad\text{and}\quad\gamma=\operatorname{atan2}(a_{3,2},a_{3,3})$

(if $|a_{3,1}|\neq 1$; otherwise $\beta=-a_{3,1}\cdot\pi/2$, $\gamma=0$ and
$\alpha=\operatorname{atan2}(-a_{1,2},a_{2,2})$ is a non-unique solution).
There is a small caveat: for these formulas to give the expected values, the
coordinate system used by the algorithm needs to be oriented as the vehicle-
coordinate system (right- or left-handed), and its $z$-axis needs to point up
or down in accordance with the vehicle’s yaw axis.

Step (7):

Some heuristics may be applied to only add such $\mathbf{t}_{k}$ into the list
that are “sufficiently far away” from points already in the list. Moreover, if
the list grows so long that it renders step (5) inefficient, points may be
deleted from the list, as long as the points still in the list do not become
coplanar. But since 10 is generically only quadratic in $n$, this should be
unlikely to happen.

######  Theorem 9.

8 is correct under the following assumptions:

  1. (a)

No ghost walls are detected.

  2. (b)

For sound sources
$\mathbf{s}_{1},\ldots,\mathbf{s}_{4},\mathbf{s}^{\prime}_{1},\ldots,\mathbf{s}^{\prime}_{4}$
such that the $\mathbf{s}_{i}$ are not coplanar, the condition that
$\lVert\mathbf{s}_{i}-\mathbf{s}_{j}\rVert=\lVert\mathbf{s}^{\prime}_{i}-\mathbf{s}^{\prime}_{j}\rVert$
for $1\leq i<j\leq 4$ implies that $\mathbf{s}_{i}=\mathbf{s}^{\prime}_{i}$
for all $i$.

So due to [?Boutin:Kemper:2019,?Boutin:Kemper:2022], the hypothesis (a) is
satisfied for almost all vehicle positions, and due to Theorem 1, the
hypothesis (b) is satisfied for almost all loudspeaker positions.

###### Proof.

The correctness of step (2) is the very definition of “no ghost walls.” Step
(3) is correct because of 7, but there is one subtlety to observe:
$\Delta_{i,j}$ is the squared distance between the $j$-th detected source and
the (unknown) position $\widetilde{\mathbf{m}}_{i}$ of the $i$-th microphone
at the time when the algorithm was called, so 7 has to be used with the
$\widetilde{\mathbf{m}}_{i}$ instead of the time-independent (and known)
coordinate vectors $\mathbf{m}_{i}$. But since the $\mathbf{m}_{i}$ are
coordinate vectors with respect to a cartesian coordinate system, we always
have
$\lVert\widetilde{\mathbf{m}}_{i}-\widetilde{\mathbf{m}}_{j}\rVert=\lVert\mathbf{m}_{i}-\mathbf{m}_{j}\rVert$,
so setting up the matrix $C$ with the $\mathbf{m}_{i}$ instead of the
$\widetilde{\mathbf{m}}_{i}$ does yield the correct result.

In step (4), the first condition guarantees that the algorithm only proceeds
if the detected sound sources are not coplanar (this follows from 5(a)), and
in particular there are at least four of them. The second “If”-statement
applies if the algorithm was called without input, which can only happen in
the first call in which non-coplanar sources were detected. The correctness of
the assumption made in step (5) is guaranteed by assumption (b) of the
theorem.

The main part of the proof concerns steps (6) and (7). Both use “reference
points” $\mathbf{b}_{1},\ldots,\mathbf{b}_{4}$. For any vector
$\mathbf{w}\in{\mathbb{R}}^{3}$ we have

$\left(\begin{array}[]{cccc}\mathbf{b}_{1}&\mathbf{b}_{2}&\mathbf{b}_{3}&\mathbf{b}_{4}\\\
\hline\cr 1&1&1&1\end{array}\right)^{T}\left(\begin{array}[]{c}\\\
2\mathbf{w}\\\ \\\
\hline\cr-\lVert\mathbf{w}\rVert^{2}\end{array}\right)=\begin{pmatrix}2\langle\mathbf{b}_{1},\mathbf{w}\rangle-\lVert\mathbf{w}\rVert^{2}\\\
\vdots\\\
2\langle\mathbf{b}_{4},\mathbf{w}\rangle-\lVert\mathbf{w}\rVert^{2}\end{pmatrix}=\begin{pmatrix}\lVert\mathbf{b}_{1}\rVert^{2}-\lVert\mathbf{b}_{1}-\mathbf{w}\rVert^{2}\\\
\vdots\\\
\lVert\mathbf{b}_{4}\rVert^{2}-\lVert\mathbf{b}_{4}-\mathbf{w}\rVert^{2}\end{pmatrix}.$

The $\mathbf{b}_{j}$ used in the algorithm are not coplanar, which means that
the matrix on the left is invertible. So if $B\in{\mathbb{R}}^{3\times 4}$ is
as in steps (6) and (7) and if
$\Delta_{l}:=\lVert\mathbf{b}_{l}-\mathbf{w}\rVert^{2}$, then

$\mathbf{w}=\frac{1}{2}B\cdot\begin{pmatrix}\lVert\mathbf{b}_{1}\rVert^{2}-\Delta_{1}\\\
\vdots\\\ \lVert\mathbf{b}_{4}\rVert^{2}-\Delta_{4}\end{pmatrix}.$ (12)

Let us write $\mathbf{t}_{1},\ldots,\mathbf{t}_{m}$ for the positions of the
detected sound sources (which step (7) seeks to work out). So
$\mathbf{t}_{i_{l}}=\mathbf{s}_{j_{l}}$ for $l=1,\ldots,4$ by the assumption
made in step (5).

Now step (7) can be reached directly from step (4), or from step (6). In the
first case we have $\mathbf{b}_{l}=\mathbf{m}_{l}$ and
$\Delta_{l,k}=\lVert\mathbf{m}_{l}-\mathbf{t}_{k}\rVert^{2}=\lVert\mathbf{b}_{l}-\mathbf{t}_{k}\rVert^{2}$
(from step (2)), and in the second case
$\mathbf{b}_{l}=\mathbf{s}_{j_{l}}=\mathbf{t}_{i_{l}}$ (from step (5)) and
$\Delta_{l,k}=D^{\operatorname{detected}}_{i_{l},k}=\lVert\mathbf{t}_{i_{l}}-\mathbf{t}_{k}\rVert^{2}=\lVert\mathbf{b}_{l}-\mathbf{t}_{k}\rVert^{2}$.
So in both cases the formula for $\mathbf{t}_{k}$ in step (7) is correct by
Equation 12. Notice that in the first case (which happens in the case of zero
input, and only in the first successful call of the algorithm), the points
$\mathbf{b}_{l}=\mathbf{m}_{l}$ are represented according to the coordinate
system given by the principal axes of the vehicle at the time when the
algorithm was called. Therefore the $\mathbf{t}_{k}$ are also represented
according to this coordinate system. These are fed back into the algorithm in
subsequent calls and serve, together with sound sources detected later, as
reference points. It follows that all detected sound sources will be given
according to this coordinate system. Being virtual sound sources, they remain
fixed even as the vehicle moves on, so the coordinate system is also fixed
once and for all. If, on the other hand, some input is given to the initial
call of the algorithm, then the coordinate system according to which the input
is given remains unchanged throughout.

Step (6) is always called with reference points
$\mathbf{b}_{l}=\mathbf{s}_{j_{l}}=t_{i_{l}}$, which is given according to the
permanently chosen coordinate system. The $\Delta_{k,i_{l}}$ come from step
(2), so they are the squared distance between
$\mathbf{t}_{i_{l}}=\mathbf{b}_{l}$ and the $k$-th microphone at the time when
the algorithm was called, which we write as $\widetilde{\mathbf{m}}_{k}$ as
before. So
$\Delta_{k,i_{l}}=\lVert\mathbf{b}_{l}-\widetilde{\mathbf{m}}_{k}\rVert^{2}$,
and Equation 12 shows that

$\frac{1}{2}B\cdot\left(\lVert\mathbf{b}_{l}\rVert^{2}-\Delta_{k,i_{l}}\right)_{l,k=1,\ldots,4}=\bigl{(}\widetilde{\mathbf{m}}_{1}\mid\cdots\mid\widetilde{\mathbf{m}}_{4}\bigr{)}.$
(13)

Now in contrast to the $\widetilde{\mathbf{m}}_{k}$, the $\mathbf{m}_{k}$ are
the coordinate vectors of the microphone positions with respect to the
principal axes of the vehicle. Since the microphones are mounted on the
vehicle, these coordinate vectors remain constant, so in particular they apply
to the present position of the microphones. Since the origin of the vehicle-
coordinate system is $\mathbf{v}$, the center of mass, this means that
$\widetilde{\mathbf{m}}_{k}-\mathbf{v}$ is a linear combination of the unit
vectors $\mathbf{x}$, $\mathbf{y}$ and $\mathbf{z}$ defining the present
directions of the principal axis, with the coefficients of the linear
combination given by the components of $\mathbf{m}_{k}$. With
$A:=\bigl{(}\mathbf{x}\mid\mathbf{y}\mid\mathbf{z}\bigr{)}$, we can write this
as $\widetilde{\mathbf{m}}_{k}=A\cdot\mathbf{m}_{k}+\mathbf{v}$, or in matrix
form
$\bigl{(}\widetilde{\mathbf{m}}_{1}\mid\cdots\mid\widetilde{\mathbf{m}}_{4}\bigr{)}=\bigl{(}A\mid\mathbf{v}\bigr{)}\cdot
M$ with $M$ as defined in step (6). Combining this with Equation 13 shows that
the formula for $\bigl{(}A\mid\mathbf{v}\bigr{)}$ in step (6) is correct.
Since $\mathbf{x}$, $\mathbf{y}$ and $\mathbf{z}$ are perpendicular unit
vectors, $A\in\operatorname{O}_{3}({\mathbb{R}})$ follows. ∎

The following algorithm is a “subroutine” of 8. We formulate it in a slightly
more general form.

######  Algorithm 10 (Find matching submatrices).

Input:

Two symmetric matrices $A=(a_{i,j})\in{\mathbb{R}}^{m\times m}$ and
$B=(b_{i,j})\in{\mathbb{R}}^{n\times n}$, and an integer $r$ with $1\leq
r\leq\min\\{m,n\\}$.

Output:

Integers $i_{1},\ldots,i_{r}\in\\{1,\ldots,m\\}$ and
$j_{1},\ldots,j_{r}\in\\{1,\ldots,n\\}$ with the $i_{\nu}<i_{\mu}$ and the
$j_{\nu}\neq j_{\mu}$ for $\nu<\mu$, such that
$A_{i_{1},\ldots,i_{r}}=B_{j_{1},\ldots,j_{r}}$ and
$\operatorname{b-rank}\bigl{(}A_{i_{1},\ldots,i_{r}}\bigr{)}=r-1$, or “FAIL”
if no such $i_{\nu}$ and $j_{\nu}$ exist.

  1. (1)

Set $k:=1$ and $i_{1}:=j_{1}:=1$.

  2. (2)

WHILE $k\leq r$ DO

    1. (3)

IF $j_{k}\notin\\{n+1,j_{1},\ldots,j_{k-1}\\}$,
$a_{i_{k},i_{\nu}}=b_{j_{k},j_{\nu}}$ for $1\leq\nu\leq k$, and
$\operatorname{b-rank}\bigl{(}A_{i_{1},\ldots,i_{k}}\bigr{)}=k-1$, THEN set
$i_{k+1}:=i_{k}+1$, $j_{k+1}:=1$ and $k:=k+1$.

    2. (4)

ELSE IF $j_{k}<n$, THEN set $j_{k}:=j_{k}+1$.

    3. (5)

ELSE IF $i_{k}<m-r+k$, THEN set $i_{k}:=i_{k}+1$ and $j_{k}:=1$.

    4. (6)

ELSE IF $k>1$, THEN set $j_{k-1}:=j_{k-1}+1$ and $k:=k-1$.

    5. (7)

ELSE Return “FAIL”.

    6. (8)

END IF

  3. (3)

END WHILE

  4. (4)

Return $i_{1},\ldots,i_{r}$ and $j_{1},\ldots,j_{r}$.

The condition on the bordered rank is not an essential part of the algorithm.
For other possible applications of the algorithm, this condition can be
replaced by any other condition of interest, or omitted altogether.

######  Theorem 11.

10 terminates after finitely many steps and is correct. Moreover, if the
$b_{i,j}$ for $1\leq i<j\leq n$ are pairwise distinct, then the algorithm
requires $\mathcal{O}(m^{r}n+m^{2}n^{2})$ operations of real numbers (almost
all of them comparisons) for fixed $r$.

###### Proof.

We compare tuples $(i_{1},j_{1},i_{2},j_{2},\ldots,i_{k},j_{k})$ of different
lengths lexicographically with the additional rule that appending entries to a
tuple makes it bigger, as in a real lexicon. So in all steps (2)(3)–(2)(6),
the tuple is replaced by a strictly bigger one (which is made longer in step
(2)(3) and shorter in step (2)(6)). Since the total length is bounded by $r$
and the entries are bounded by $\max\\{m,n+1\\}$, this guarantees termination.

To prove correctness, we claim that throughout the algorithm we have
$a_{i_{\nu},i_{\mu}}=b_{j_{\nu},j_{\mu}}$ for $1\leq\nu,\mu<k$. In fact, this
is true for $k=1$, and step (2)(3) affords a proof by induction on $k$. So if
the algorithm terminates with returning integers $i_{\nu}$ and $j_{\nu}$, then
$k=r+1$ was reached, so indeed
$A_{i_{1},\ldots,i_{r}}=B_{j_{1},\ldots,j_{r}}$. Moreover, the tuple
$(i_{1},\ldots,i_{k})$ is increasing throughout the algorithm, and step (2)(3)
makes sure that the $j_{\nu}$ are pairwise distinct. The rank condition in
that step provides the condition on the $\mathbf{s}_{i_{\nu}}$.

Conversely, assume there exist integers
$i_{1}^{\prime},\ldots,i_{r}^{\prime},j_{1}^{\prime},\ldots,j_{r}^{\prime}$
meeting the specifications of the algorithm. We claim that throughout the
algorithm

$(i_{1}^{\prime},j_{1}^{\prime},\ldots,i_{k}^{\prime},j_{k}^{\prime})\geq(i_{1},j_{1},\ldots,i_{k},j_{k})$
(14)

(comparing lexicographically). This is true after step (1) since
$(i_{1}^{\prime},j_{1}^{\prime})\geq(1,1)$. Moreover, if the conditions in
step (2)(3) are satisfied, then also
$(i_{1}^{\prime},j_{1}^{\prime},\ldots,i_{k+1}^{\prime},j_{k+1}^{\prime})\geq(i_{1},j_{1},\ldots,i_{k},j_{k},i_{k}+1,1)$,
so Equation 14 continues to hold. On the other hand, if at least one of the
conditions in step (2)(3) does not hold, this implies
$(i_{1}^{\prime},j_{1}^{\prime},\ldots,i_{k}^{\prime},j_{k}^{\prime})\neq(i_{1},j_{1},\ldots,i_{k},j_{k})$,
so we have ”$>$” in Equation 14. Therefore
$(i_{1}^{\prime},j_{1}^{\prime},\ldots,i_{k}^{\prime},j_{k}^{\prime})\geq(i_{1},j_{1},\ldots,i_{k},j_{k}+1)$.
By the specifications of the algorithm, we have $j_{k}^{\prime}\leq n$ and
$i_{k}^{\prime}\leq m-r+k$. So if $j_{k}\geq n$, then
$(i_{1}^{\prime},j_{1}^{\prime},\ldots,i_{k}^{\prime},j_{k}^{\prime})\geq(i_{1},j_{1},\ldots,i_{k}+1,1)$,
and if in addition $i_{k}\geq m-r+k$, then even
$(i_{1}^{\prime},j_{1}^{\prime},\ldots,i_{k-1}^{\prime},j_{k-1}^{\prime})\geq(i_{1},j_{1},\ldots,i_{k-1},j_{k-1}+1)$.
This shows that if the condition of any of the steps (2)(4)–(2)(6) is
satisfied, then Equation 14 continues to hold, so indeed it holds throughout.
The argument also shows that if step (2)(6) were reached with $k=1$, then
$(i_{1}^{\prime},j_{1}^{\prime})>(i_{1},j_{1})$ but $i_{1}\geq m-r+1\geq
i_{1}^{\prime}$, and $j_{1}\geq n\geq j_{1}^{\prime}$, a contradiction. So if
the specifications of the algorithm are satisfiable, the algorithm will not
return “FAIL.”

Finally, let us consider the running time. For each $k=1,\ldots,r$ we give an
upper bound for the number of comparisons (i.e., checks whether
$a_{i_{k},i_{\nu}}=b_{j_{k},j_{\nu}}$ in step (2)(3)) that occur during the
entire run of the algorithm for this particular $k$. For $k=1$, there are at
most $m\cdot n$ comparisons, as $i_{1}$ and $j_{1}$ range. For $k=2$, the
upper bound is $\binom{m}{2}\cdot n(n-1)\cdot k\leq m^{2}n^{2}$. Now $k\geq 3$
is only reached if $b_{j_{1},j_{2}}=a_{i_{1},i_{2}}$, and by the hypothesis on
the distinctness of the entries of $B$, this condition determines the set
$\\{j_{1},j_{2}\\}$, so there are only two possibilities for the ordered pair
$(j_{1},j_{2})$. Thus for $k=3$ only $j_{3}$ ranges freely, and we get
$2\cdot(n-2)\cdot\binom{m}{3}\cdot k\leq m^{3}n$ as an upper bound. Finally,
for $k>3$ we have $b_{j_{1},j_{\nu}}=a_{i_{1},i_{\mu}}$ for $\nu<k$, in
particular for $\nu=2,3$. This determines the sets $\\{j_{1},j_{2}\\}$ and
$\\{j_{1},j_{3}\\}$ uniquely. Because of the distinctness of the $j_{\nu}$,
$j_{1}$ is uniquely determined as the sole element in the intersection, and
this means that every $j_{\nu}$ with $\nu<k$ is also uniquely determined.
Therefore we obtain $(n-k+1)\cdot\binom{m}{k}\cdot k\leq(n-k+1)\cdot m^{r}$ as
an upper bound. Summing over $k$ shows that the total number of comparisons is
in $\mathcal{O}(m^{r}n+m^{2}n^{2})$.

Further operations of real numbers are required for the rank determination in
step (2)(3). For a given $k$, the matrix depends only on $i_{1},\ldots,i_{k}$,
so there are at most $\binom{m}{k}$ rank determinations, each requiring at
most $\mathcal{O}(k^{3})$ operations. Since $\binom{m}{k}k^{3}\leq
m^{r}r^{3}$, the cost for all $k=1,\ldots,r$ lies in
$\mathcal{O}(m^{r}r^{4})$, which, since $r$ is considered as a constant, is
subsumed in $\mathcal{O}(m^{r}n)$. ∎

######  Remark 12.

A simpler method for the same purpose as 10 would be to just try all tuples of
integers $(i_{1},\ldots,i_{r},j_{1},\ldots,j_{r})$ in the admissible range.
This requires $\mathcal{O}(m^{r}n^{r})$ operations in ${\mathbb{R}}$. In our
application we have $r=4$, so as a function of $l=\max\\{m,n\\}$, our
algorithm has running time $\mathcal{O}(l^{5})$, compared to the simpler one
with $\mathcal{O}(l^{8})$. Moreover, the asymmetry in $m$ and $n$ of the
running time is fortunate since we apply the algorithm in a situation where
$m$ is the number of detected sound sources and thus has no intrinsic growth
as the vehicle travels, and where $n$ is the number of known virtual sound
sources, which can be expected to grow ever larger. $\triangleleft$

## Acknowledgements

The authors thank the Simons Laufer Mathematical Sciences Institute (formerly
the Mathematical Sciences Research Institute (MSRI)), the Banff International
Research Station for Mathematical Innovation and Discovery (BIRS) and the
Centro Internazionale per la Ricerca Matematica (CIRM) in Trento for
supporting their work.

## References

  * [1]
  * [2] cite.Boutin:Kemper:2019 Mireille Boutin, Gregor Kemper, _A Drone Can Hear the Shape of a Room_ , SIAM J. Appl. Algebra Geometry 4 (2020), 123–140.
  * [3]
  * [4] cite.Boutin:Kemper:2022 Mireille Boutin, Gregor Kemper, _Can a ground-based vehicle hear the shape of a room?_ , Studies in Applied Mathematics 151 (2023), 352–368.
  * [5]
  * [6] cite.cao2020effective Shuai Cao, Xiang Chen, Xu Zhang, Xun Chen, _Effective audio signal arrival time detection algorithm for realization of robust acoustic indoor positioning_ , IEEE Transactions on Instrumentation and Measurement 69(10) (2020), 7341–7352.
  * [7]
  * [8] cite.Cayley:1841 Arthur Cayley, _On a theorem in the geometry of position_ , Cambridge Mathematical Journal II (1841), 267––271.
  * [9]
  * [10] cite.DPWLV1 Ivan Dokmanić, Reza Parhizkar, Andreas Walther, Yue M. Lu, Martin Vetterli, _Acoustic echoes reveal room shape_ , Proceedings of the National Academy of Sciences 110 (2013).
  * [11]
  * [12] cite.dumbgen2022blind Frederike Dümbgen, Adrien Hoffet, Mihailo Kolundžija, Adam Scholefield, Martin Vetterli, _Blind as a bat: Audible echolocation on small robots_ , IEEE Robotics and Automation Letters 8(3) (2022), 1271–1278.
  * [13]
  * [14] cite.durrant2006simultaneous Hugh Durrant-Whyte, Tim Bailey, _Simultaneous localization and mapping: part I_ , IEEE robotics & automation magazine 13(2) (2006), 99–110.
  * [15]
  * [16] cite.grisetti2010tutorial Giorgio Grisetti, Rainer Kümmerle, Cyrill Stachniss, Wolfram Burgard, _A tutorial on graph-based SLAM_ , IEEE Intelligent Transportation Systems Magazine 2(4) (2010), 31–43.
  * [17]
  * [18] cite.krekovic2016echoslam Miranda Kreković, Ivan Dokmanić, Martin Vetterli, _EchoSLAM: Simultaneous localization and mapping with acoustic echoes_ , in: _2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 11–15, Ieee, 2016.
  * [19]
  * [20] cite.krekovic2016look Miranda Krekovic, Ivan Dokmanic, Martin Vetterli, _Look, no beacons! optimal all-in-one echoslam_ , arXiv preprint arXiv:1608.08753 (2016).
  * [21]
  * [22] cite.krekovic2020shapes Miranda Kreković, Ivan Dokmanić, Martin Vetterli, _Shapes from echoes: uniqueness from point-to-plane distance matrices_ , IEEE Transactions on Signal Processing 68 (2020), 2480–2498.
  * [23]
  * [24] cite.macwilliam2023simultaneous Kathleen MacWilliam, Filip Elvander, Toon van Waterschoot, _Simultaneous Acoustic Echo Sorting and 3-D Room Geometry Inference_ , in: _ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 1–5, IEEE, 2023.
  * [25]
  * [26] cite.saqib2020model Usama Saqib, Jesper Rindom Jensen, _A model-based approach to acoustic reflector localization with a robotic platform_ , in: _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 4499–4504, IEEE, 2020.
  * [27]
  * [28] cite.shih2019can Oliver Shih, Anthony Rowe, _Can a phone hear the shape of a room?_ , in: _2019 18th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN)_ , pp. 277–288, IEEE, 2019.
  * [29]
  * [30] cite.zhou2017batmapper Bing Zhou, Mohammed Elbadry, Ruipeng Gao, Fan Ye, _BatMapper: Acoustic sensing based indoor floor plan construction using smartphones_ , in: _Proceedings of the 15th Annual International Conference on Mobile Systems, Applications, and Services_ , pp. 42–55, 2017.
  * [31]