Talk:Cayley–Menger determinant

Draft:Cayley-Menger relations

Should Draft:Cayley-Menger relations be merged here? That was suggested (not by me) on Wikipedia:Miscellany for deletion/Draft:Cayley-Menger relations. -- Beland (talk) 06:53, 29 July 2022 (UTC)

Definitions from Draft:Cayley-Menger relations

The following definitions appear in the draft page and they duplicate the ones in the current article. Maybe they should be used to replace or improve the current ones. -- Taku (talk) 10:42, 1 August 2022 (UTC)

Classify a Euclidean distance matrix (EDM) for $\mathbb {R} ^{d}$ as an n x n square matrix of all pairwise squared distances between n points in $\mathbb {R} ^{d}$. Let $\Delta _{n}$ denote the distance entries $\Delta _{i,j}$ for $1\leq i,j\leq n$. For all S $\subseteq$ [n], a submatrix Δ_[S] has entries $\Delta$_{i, j} for i, j $\in$ S. Let the volume matrix det(${\hat {\Delta }}$_s) be the $|S|+1$ x $|S|+1$ matrix obtained from Δ_[S] by bordering Δ_[S] with a top row $(0,1,...,1)$ and a left column $(0,1,...,1)$^T. Finally, det(${\hat {\Delta }}$_s) will find the volume of the simplex with points in $S$. This is the Cayley-Menger determinant. The theorem below states the volume of any simplex formed by $d+2$ points in $\mathbb {R}$^d is 0: A real symmetric matrix Δ_[n] with 0 diagonal and positive entries is a Euclidean distance matrix for ℝ^d only if det(${\hat {\Delta }}$_s) = 0 for all S $\subseteq$ [n] with |S| ≥ d + 2 where the volume matrix is expressed as

${\hat {\Delta }}={\begin{bmatrix}0&1&...&1\\1&\delta _{1}1&...&\delta _{1}n\\\vdots &\vdots &\ddots &\vdots \\1&\delta _{n}1&...&\delta _{n}n\\\end{bmatrix}}$

This determinant's purpose is to find the volume of any simplex in the $j^{th}$ dimension. Suppose $S$ is a j-simplex in $\mathbb {R}$ⁿ with a set of vertices v₁, ..., v_{j + 1} and $B=(\beta$_ik$)$ denotes the $|J|+1$ x $|J|+1$ matrix given by $\beta$_ik$={|V_{i}-V_{k}|}_{2}^{2}$. Therefore, the content, the higher-dimensional volume of a $j$^th dimensional simplex, $V_{j}$, is given as an Automated Geometry Thoerem by:

$V_{j}^{2}(S)={\frac {(-1)^{j+1}}{2^{j}(j!)^{2}}}\det({\hat {B}})$

where ${\hat {B}}$ is the $(j+2)x(j+2)$ matrix obtained from $B$ by bordering $B$ with a top row $(0,1,...,1)$ and a left column $(0,1,...,1)$^T. The edge lengths here are the vector $L2-norms{|V_{i}-V_{k}|}_{2}$ and the Cayley-Menger determinant is none other than $\det({\hat {B}})$. The following links contains an in-depth explanation and proof of simplices and how to derive their content (volume) via the Cayley-Menger Determinant.

References

Comments

The following comments appear in the draft page and look very helpful for improving the article. -- Taku (talk) 10:44, 1 August 2022 (UTC)

My personal comments on the page and your help: I have read your feedback and read the notes you attached in the link below in your 2nd review of my page. I have linked this topic to a couple more pages and did the best I could without adding ambiguity to the page by bringing in new topics like Hilda-Laman graphs and such. I believe it is concise and does not deviate from Cayley-Menger at all and I have linked realizing the EDM algorithm to Cayley-Menger. One formula and one matrix below do not render but I linked a latex compiler below here in the raw text in which they appear. Thank you for all your help!

Instructor 2nd: The sphere intersection algorithm and theorem are out of place. It is overkill because it works when d is not given. In your problem, d is given. Also, you haven't mentioned how that algorithm has anything to do with Cayley Menger determinants. You need to look at the lecture notes 1-6 of https://www.cise.ufl.edu/~sitharam/COURSES/GC/GCgood/gc.html where a connection is drawn between Cayley menger determinants and a simpler sphere intersection algorithm. It also shows how a much smaller subset of entries of a distance matrix and their Cayley menger determinants being zero and nonnegative automatically determine what the remaining entries will be, by using this algorithm to determine all the point coordinates and then computing the remaining distance entries of the matrix. The full generality of the algorithm you currently have is more appropriate for the Schoenberg section, both for determining if a matrix is a distance matrix and also for completing a partial distance matrix - when the rank or dimension d is not given.

Michael Rothstein Critique 2 This page is very well constructed and organized. From what I can tell it is just about done and most requirements are met. You seem to have collected a good set of references, some of which I used myself. A good job is done explaining every section. The "Cayley Menger Determinient" section is quite long and might be better broken into 2-3 sections. Overall, the technical information seems accurate and knowledgeable and the page looks clean.

Instructor: There is a Cayley-Menger section in the existing distance geometry page that you can merge with your page. This requires work, but also gives you some content, so it compensates. Otherwise, the progress on the page is good. What is missing is how this yields an algorithm to decide whether a given matrix is a distance matrix corresponding to a Euclidean point set living in d-dimensions, via a geometric constraint solving algorithm (reference that page) based on ruler and compass construction (refer to the quadratic solvability page) that actually finds the point set. We discussed this algorithm in the first week. In fact, the algorithm only uses limited number of entries of the matrix to find the point set and simply compares the remaining entries to the distances measured from the point set. So it can be used to complete a partially specified matrix, into a distance matrix, i.e. in fact any negative semi-definite real symmetric matrix of a given rank (refer to matrix completion problems) -->