Given three points in the plane, the distances
between them have to be non-negative and obey the triangle inequalities
but are otherwise unconstrained. But if one has four points in the plane, then there is an additional constraint connecting the six distances
between them, coming from the Cayley-Menger determinant:
Proposition 1 (Cayley-Menger determinant) If
are four points in the plane, then the Cayley-Menger determinant
vanishes.
Proof: If we view as vectors in
, then we have the usual cosine rule
, and similarly for all the other distances. The
matrix appearing in (1) can then be written as
, where
is the matrix
and is the (augmented) Gram matrix
The matrix is a rank one matrix, and so
is also. The Gram matrix
factorises as
, where
is the
matrix with rows
, and thus has rank at most
. Therefore the matrix
in (1) has rank at most
, and hence has determinant zero as claimed.
For instance, if we know that and
, then in order for
to be coplanar, the remaining distance
has to obey the equation
After some calculation the left-hand side simplifies to , so the non-negative quantity is constrained to equal either
or
. The former happens when
form a unit right-angled triangle with right angle at
and
; the latter happens when
form the vertices of a unit square traversed in that order. Any other value for
is not compatible with the hypothesis for
lying on a plane; hence the Cayley-Menger determinant can be used as a test for planarity.
Now suppose that we have four points on a sphere
of radius
, with six distances
now measured as lengths of arcs on the sphere. There is a spherical analogue of the Cayley-Menger determinant:
Proposition 2 (Spherical Cayley-Menger determinant) If
are four points on a sphere
of radius
in
, then the spherical Cayley-Menger determinant
vanishes.
Proof: We can assume that the sphere is centred at the origin of
, and view
as vectors in
of magnitude
. The angle subtended by
from the origin is
, so by the cosine rule we have
Similarly for all the other inner products. Thus the matrix in (2) can be written as , where
is the Gram matrix
We can factor where
is the
matrix with rows
. Thus
has rank at most
and thus the determinant vanishes as required.
Just as the Cayley-Menger determinant can be used to test for coplanarity, the spherical Cayley-Menger determinant can be used to test for lying on a sphere of radius . For instance, if we know that
lie on
and
are all equal to
, then the above proposition gives
The left-hand side evaluates to ; as
lies between
and
, the only choices for this distance are then
and
. The former happens for instance when
lies on the north pole
,
are points on the equator with longitudes differing by 90 degrees, and
is also equal to the north pole; the latter occurs when
is instead placed on the south pole.
The Cayley-Menger and spherical Cayley-Menger determinants look slightly different from each other, but one can transform the latter into something resembling the former by row and column operations. Indeed, the determinant (2) can be rewritten as
and by further row and column operations, this determinant vanishes if and only if the determinant
vanishes, where . In the limit
(so that the curvature of the sphere
tends to zero),
tends to
, and by Taylor expansion
tends to
; similarly for the other distances. Now we see that the planar Cayley-Menger determinant emerges as the limit of (3) as
, as would be expected from the intuition that a plane is essentially a sphere of infinite radius.
In principle, one can now estimate the radius of the Earth (assuming that it is either a sphere
or a flat plane
) if one is given the six distances
between four points
on the Earth. Of course, if one wishes to do so, one should have
rather far apart from each other, since otherwise it would be difficult to for instance distinguish the round Earth from a flat one. As an experiment, and just for fun, I wanted to see how accurate this would be with some real world data. I decided to take
,
,
,
be the cities of London, Los Angeles, Tokyo, and Dubai respectively. As an initial test, I used distances from this online flight calculator, measured in kilometers:
Given that the true radius of the earth was about kilometers, I chose the change of variables
(so that
corresponds to the round Earth model with the commonly accepted value for the Earth’s radius, and
corresponds to the flat Earth), and obtained the following plot for (3):
In particular, the determinant does indeed come very close to vanishing when , which is unsurprising since, as explained on the web site, the online flight calculator uses a model in which the Earth is an ellipsoid of radii close to
km. There is another radius that would also be compatible with this data at
(corresponding to an Earth of radius about
km), but presumably one could rule out this as a spurious coincidence by experimenting with other quadruples of cities than the ones I selected. On the other hand, these distances are highly incompatible with the flat Earth model
; one could also see this with a piece of paper and a ruler by trying to lay down four points
on the paper with (an appropriately rescaled) version of the above distances (e.g., with
,
, etc.).
If instead one goes to the flight time calculator and uses flight travel times instead of distances, one now gets the following data (measured in hours):
Assuming that planes travel at about kilometers per hour, the true radius of the Earth should be about
of flight time. If one then uses the normalisation
, one obtains the following plot:
Not too surprisingly, this is basically a rescaled version of the previous plot, with vanishing near and at
. (The website for the flight calculator does say it calculates short and long haul flight times slightly differently, which may be the cause of the slight discrepancies between this figure and the previous one.)
Of course, these two data sets are “cheating” since they come from a model which already presupposes what the radius of the Earth is. But one can input real world flight times between these four cities instead of the above idealised data. Here one runs into the issue that the flight time from to
is not necessarily the same as that from
to
due to such factors as windspeed. For instance, I looked up the online flight time from Tokyo to Dubai to be 11 hours and 10 minutes, whereas the online flight time from Dubai to Tokyo was 9 hours and 50 minutes. The simplest thing to do here is take an arithmetic mean of the two times as a preliminary estimate for the flight time without windspeed factors, thus for instance the Tokyo-Dubai flight time would now be 10 hours and 30 minutes, and more generally
This data is not too far off from the online calculator data, but it does distort the graph slightly (taking as before):
Now one gets estimates for the radius of the Earth that are off by about a factor of from the truth, although the
round Earth model still is twice as accurate as the flat Earth model
.
Given that windspeed should additively affect flight velocity rather than flight time, and the two are inversely proportional to each other, it is more natural to take a harmonic mean rather than an arithmetic mean. This gives the slightly different values
but one still gets essentially the same plot:
So the inaccuracies are presumably coming from some other source. (Note for instance that the true flight time from Tokyo to Dubai is about greater than the calculator predicts, while the flight time from LA to Dubai is about
less; these sorts of errors seem to pile up in this calculation.) Nevertheless, it does seem that flight time data is (barely) enough to establish the roundness of the Earth and obtain a somewhat ballpark estimate for its radius. (I assume that the fit would be better if one could include some Southern Hemisphere cities such as Sydney or Santiago, but I was not able to find a good quadruple of widely spaced cities on both hemispheres for which there were direct flights between all six pairs.)
27 comments
Comments feed for this article
25 May, 2019 at 3:22 pm
Mircea
Maybe the Cayley-Menger determinant calculations here are related to Schoenberg’s theorem on embeddability of metric spaces in Euclidean spaces, or to some special case of it?
25 May, 2019 at 6:14 pm
amsmath
I am actually quite full right now, but I am kinda sure that „but one can transform the latter into something resembling the latter“ was not meant to be said. Good night.
[Corrected, thanks – T.]
25 May, 2019 at 10:37 pm
domotorp
I think that real travel data can have too many factors: there’s an additive constant of take off and landing; planes might not fly on the shortest path; between different cities there might be different planes flying with different speeds. Because of this, the distance based model sounds more reliable. I wonder what it would give for 4 nearby cities, e.g., like all in the US.
26 May, 2019 at 2:56 am
Anonymous
It would be interesting to generalize (if possible) this determinant to
points in
and to n-spheres.
26 May, 2019 at 5:38 am
Terence Tao
Propositions 1 and 2 extend to higher dimensions (taking
throughout), with basically the same proof. There is also a variant of these propositions, due to Menger and Schoenberg, describing exactly when a set of putative distances
between
points can be realised in
or
in terms of the positive semi-definiteness and rank properties of matrices similar to those appearing in those propositions: see Theorem 2.1, 2.3 of https://arxiv.org/abs/1812.05482 .
26 May, 2019 at 3:45 am
ravenclawprefect
I assume these flight times include factors like taxiing and the process of obtaining cruising speed and altitude, which should be reasonably similar across long-haul flights.
If we subtract an hour uniformly from the times in the last graph (really I should subtract first and then take the harmonic mean, but I don’t have the original times and suspect it doesn’t make much difference), we get the graph at https://imgur.com/rdkfrqU, where the tally marks are at k=0.8, 1, and 1.2. Clearly, this gives far better agreement with the true radius of the Earth. (Apologies for the low quality, I’m rendering it pixel-by-pixel in a simple Python script.)
Of course, an hour happens to work remarkably well here, and I’m not sure this is the actual time to reach cruising altitude in most long-haul flights, but it suggests that taking this sort of thing into consideration would give much closer estimates.
(By comparing multiple 4-tuples of cities, one might be able to work out what this constant should be by trying to maximize consistency, even without knowing any details of real-life plane flights.)
26 May, 2019 at 1:02 pm
Gabe
I agree that flight times aren’t ideal here. I assume the idea is to use a metric that everyone agrees on. Are latitude and longitude undisputable enough?
29 May, 2019 at 9:54 pm
postmortes
It’s reasonably well-known (see for example, https://www.theguardian.com/world/2018/aug/27/flight-times-extended-by-major-airlines-to-avoid-payouts-report-claims ) that flight times are padded — not just to avoid payouts, but to anticipate problems and delays. So using flight times is unfortunately a poor choice as you’ll struggle to compensate for the unknown padding added by each airline.
26 May, 2019 at 4:35 am
Anonymous
Does a similar determinant (with hyperbolic cosines and curvature instead of the radius) exist in hyperbolic plane (e.g. by means of the analytic continuation)?
26 May, 2019 at 5:41 am
Terence Tao
Yes; one simply works with the unit hyperboloid in Minkowski space instead of the unit sphere in Euclidean space (with the Minkowski inner product replacing the Euclidean dot product, and hyperbolic angle replacing Euclidean angle). Analytic continuation would also work (in the spirit of Osborn’s rule). I haven’t plotted the graphs, but would suspect that the hyperbolic Earth model (replacing all the cosines by hyperbolic cosines) would fare worse than the flat or round Earth models for all the data sets given above.
29 May, 2019 at 11:43 pm
Anonymous
It seems that in the context of special relativity, the distances correspond to Minkowski metric (i.e. “proper times” between spacetime events.)
Is it possible to replace your example of the time of flight data by a similar example of measured proper times of propagation of signals from several GPS satellites to a GPS rceiver ?
27 May, 2019 at 12:40 am
njwildberger: tangential thoughts
This entire subject is much simplified, and logically improved, if you make the transition to Rational Trigonometry. We dispense with angles and lengths, and rely rather on the purely algebraic analogs coming ultimately from the quadratic form or symmetric bilinear form which generates the geometry. There is then no mention of circular functions and their inverses. For a (very) elementary introduction, see my Wild Trig YouTube series, or for something more advanced which explains the spherical versions, see the lectures in Part II of the Universal Hyperbolic Geometry series starting with https://www.youtube.com/watch?v=Sop6KXIX014&list=PLIljB45xT85DZby7Ju-SupKHxErzdRvgI
29 May, 2019 at 1:29 am
df
Rational Trigonometry is great.
31 May, 2019 at 3:48 am
no
No it’s not.
27 May, 2019 at 7:33 am
L
This does not prove anything or close to prove anything or increase evidence of anything or shows anything close to what Occam’s razor would need. You are looking at two biased hypothesis and making a conclusion from that.
27 May, 2019 at 10:12 am
Gosha F
It seems that $\Sigma$ in the first proof is $5\times 1$, so that $\mathrm{rank}(M + M^T – 2\widetilde{G}) = 1 + 1 + 1$
27 May, 2019 at 10:32 am
Gosha F
No, it isn’t. Sorry, mixed it up.
27 May, 2019 at 1:01 pm
Joseph Malkevitch
A tetrahedron is a collection of 4 points in 3-space that don’t lie in a plane or have three points on a line. One can think of a “degenerate” tetrahedron as 4 points in the plane, no three on a line, which will determine 6 distances. The existence of a tetrahedron can be determined using the Cayley-Menger determinant (together with having the triangle inequality hold properly for each of the 4 faces). The space of ordered sextuples (corresponding to some canonical labeling of the edges) it seems to me deserves to be better explored in the context of edge lengths of tetrahedra. In particular, such a sextuple (reordered) can be realized by anywhere from 0 to 30 tetrahedra, but, for example, what sextuples correspond to having exactly 23 tetrahedra is poorly explored and understood. Furthermore, there is a not widely known 3×3 determinant due to William McCrae, Analytical Geometry of Three Dimensions, 2nd. ed., pg. 30 (There is a Dover Press edition.) that can be used to determine when a candidate sextuple for a tetrahedron has positive or zero volume.
2 June, 2019 at 3:11 am
YG
“In particular, such a sextuple (reordered) can be realized by anywhere from 0 to 30 tetrahedra, but, for example, what sextuples correspond to having exactly 23 tetrahedra is poorly explored and understood” – Do you have any reference for that?
2 June, 2019 at 7:26 am
Joseph Malkevitch
Look at this paper and the references given there:
Click to access Hildebrand-Calculus-Spring2015-report.pdf
29 May, 2019 at 8:27 am
GeneralAi
Terence tao why don’t you work in the area of motion planning and specific humanoid motion palnning?
30 May, 2019 at 8:27 am
Ehud
A heuristic for why I would expect one constraint (realized by the Cayley-Menger determinant) for this problem: There are 2*4 = 8 degrees of freedom in the coordinates of the four points in the plane, but translations (2 d.o.f) and rotations (1 d.o.f) leave the distances invariant. Hence there are 8 – 2 – 1 = 5 degrees of freedom for the 6 distances, leaving them indeed with 1 constraint.
30 May, 2019 at 9:58 pm
Anonymous
Maybe the error is because you didn’t take into account that the Earth is flat. Or maybe this is what you’re trying to prove!
31 May, 2019 at 1:14 pm
Jean
Hello ,maybe im totally wrong, but why can G be not factorized into simply 5×1 (0,A,B,C,D)^t . Then (0,A,B,C,D)^t * (0,A,B,C,D) i would get G. Same case in the spherical case just without the 0.
1 June, 2019 at 3:19 am
Jean
Hello, i totally forgot that A, B , C, D are vectors, my mistake
3 July, 2019 at 1:26 pm
Maths student
Projective geometry is very interesting. For instance, coplanarity in projective 3-space is invariant under projective transformations. Yet, the Cayley‒Menger determinant is not invariant under projective transformations.
After all, this determinant describes the volume of a simplex
, so that the formula
holds, where
is a linear transformation.
Unfortunately, projective transformations seem to create chaos. Suppose that
is embedded in
via the embedding
. Obviously, the volume of any simplex in
remains invariant under any shifts along
, and we may extract the volume by passing to a four-dimensional simplex by adjoining a suitable fifth point. Yet dependent on where the simplex is, once the (4D) linear transformation behind the (3D) projective transformation is applied, the volume of the augmented simplex will have a different relation to the volume of the original simplex.
16 August, 2019 at 4:14 am
Sam
I don’t think it’s the greatest assumption to say that the Earth should be approximated by a sphere, although the difference in error for GPS is usually miniscule for most applications. Using the wgs 84 framework with an ellipsoid revolute is what most technology companies appear to be using today, even if egm 96 is replacing it, most calculations are intensive with a topographic map of Earth’s geoid. Still, this is a cool tidbit. This blog is neat, I certainly can’t remember anything about measure theory and differential geometry but Terry’s theorems definitely look amazing.