Cayley–Menger determinant

Inom linjär algebra , geometri och trigonometri är Cayley -Menger-determinanten en formel för innehållet, dvs den högre dimensionella volymen , av en ${\textstyle n}$ -dimensionell simplex i termer av kvadraterna på alla avstånden mellan par av dess hörn. Determinanten är uppkallad efter Arthur Cayley och Karl Menger .

( ${n \choose 2}$ parvisa avståndspolynom mellan n punkter i ett verkligt euklidiskt utrymme är euklidiska invarianter som är associerade via -Menger-relationerna . Dessa relationer tjänade flera syften som att generalisera Herons formel, beräkna innehållet i en n -dimensionell simplex och slutligen bestämma om någon verklig symmetrisk matris är en euklidisk avståndsmatris inom området för avståndsgeometri .

Historia

Karl Menger var en ung geometriprofessor vid universitetet i Wien och Arthur Cayley var en brittisk matematiker som specialiserade sig på algebraisk geometri. Menger utökade Cayleys algebraiska förträfflighet för att föreslå ett nytt axiom för metriska utrymmen med hjälp av begreppen avståndsgeometri och kongruensrelation, känd som Cayley-Menger-determinanten. Detta slutade med att generalisera en av de första upptäckterna inom avståndsgeometri , Herons formel , som beräknar arean av en triangel givet dess sidolängder.

Definition

Låt ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ vara $n+1$ punkter i $k$ -dimensionellt euklidiskt utrymme , med $k\geq n$ . Dessa punkter är hörn av en n -dimensionell simplex: en triangel när $n=2$ ; en tetraeder när $n=3$ , och så vidare. Låt ${\textstyle d_{ij}}$ vara de euklidiska avstånden mellan hörn $A_{i}$ och ${\textstyle A_{j}}$ . Innehållet, dvs den n -dimensionella volymen av denna simplex, betecknad med $v_{n}$ , kan uttryckas som en funktion av determinanter för vissa matriser, enligt följande:

$${\begin{aligned}v_{n}^{2}&={\frac {1}{(n!)^{2}2^{n}}}{\begin{vmatrix}2d_{01 }^{2}&d_{01}^{2}+d_{02}^{2}-d_{12}^{2}&\cdots &d_{01}^{2}+d_{0n}^{2 }-d_{1n}^{2}\\d_{01}^{2}+d_{02}^{2}-d_{12}^{2}&2d_{02}^{2}&\cdots &d_ {02}^{2}+d_{0n}^{2}-d_{2n}^{2}\\\vdots &\vdots &\ddots &\vdots \\d_{01}^{2}+d_ {0n}^{2}-d_{1n}^{2}&d_{02}^{2}+d_{0n}^{2}-d_{2n}^{2}&\cdots &2d_{0n}^ {2}\end{vmatrix}}\\[10pt]&={\frac {(-1)^{n+1}}{(n!)^{2}2^{n}}}{\begin {vmatrix}0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{0n}^{2}&1\\d_{01}^{2}&0&d_{12}^{2}& \cdots &d_{1n}^{2}&1\\d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\ vdots &\ddots &\vdots &\vdots \\d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&\cdots &1&0\end{vmatrix }}.\end{aligned}}$$

Detta är Cayley-Menger determinant . För $n=2$ är det ett symmetriskt polynom i $d_{ij}$ och är således invariant under permutation av dessa storheter. Detta misslyckas för $n>2,$ men det är alltid invariant under permutation av hörnen.

Förutom den sista raden och kolumnen med 1:or är matrisen i den andra formen av denna ekvation en euklidisk avståndsmatris .

Speciella fall

2-Simplex

För att upprepa, en simplex är en n -dimensionell polytop och det konvexa skrovet av $n+1$ punkter som inte ligger i något $(n-1)$ dimensionsplan. Därför uppstår en 2-simplex när $n=2$ och simplexet resulterar i en triangel. Därför tillhandahålls formeln för att bestämma ${\displaystyle V_{j}^{2}} i en triangel nedan:$

$-16\Delta ^{2}={\begin{vmatrix}0&1&1&1\\1&0&c^{2}&b^{2}\\1&c^{2}&0&a^{2}\\1&b^{2} &a^{2}&0\\\end{vmatrix}}$

Som ett resultat presenterar ekvationen ovan innehållet i en 2-simplex (arean av en plan triangel med sidolängderna $a$ , $b$ och $c$ ) och det är en generaliserad form av Herons formel.

3-Simplex

På liknande sätt uppstår en 3-simplex när $n=2$ och simplexet resulterar i en tetraeder. Därför tillhandahålls formeln för att bestämma ${\displaystyle V_{j}^{2}} för en tetraeder nedan:$

$288V^{2}={\begin{vmatrix}0&1&1&1&1\\1&0&d_{12}^{2}&d_{13}^{2}&d_{14}^{2}\\1&d_{21}^{ 2}&0&d_{23}^{2}&d_{24}^{2}\\1&d_{31}^{2}&d_{32}^{2}&0&d_{34}^{2}\\1&d_{41} ^{2}&d_{42}^{2}&d_{43}^{2}&0\\\end{vmatrix}}$

Som ett resultat presenterar ekvationen ovan innehållet i en 3-simplex, vilket är volymen av en tetraeder där kanten mellan hörn i {\displaystyle i} $j {$ \ $j}$ har längden $d_ {ij}$ .

Bevis

Låt kolumnvektorerna ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ vara $n+1$ punkter i ${\ displaystyle n}$ -dimensionellt euklidiskt utrymme. Börjar med volymformeln

$v_{n}={\frac {1}{n!}}\left|\det {\begin{pmatrix}A_{0}&A_{1}&\cdots &A_{n}\\1&1&\ cdots &1\end{pmatrix}}\right|\,,$

vi noterar att determinanten är oförändrad när vi lägger till en extra rad och kolumn för att göra en $(n+2)\ gånger (n+2)$ matris,

$P={\begin{pmatrix}A_{0}&A_{1} &\cdots &A_{n}&0\\1&1&\cdots &1&0\\\|A_{0}\|^{2}&\|A_{1}\|^{2}&\cdots &\|A_{n }\|^{2}&1\end{pmatrix}}\,,$

där $\|A_{j}\|^{2}$ är kvadraten på längden på vektorn $A_{j}$ . Dessutom noterar vi att matrisen $(n+2)\ gånger (n+2)$

$Q={\begin{pmatrix}-2&0&\cdots &\cdots &\cdots &\0&0-2&0 vdots &\vdots &\ddots &\vdots &\vdots &\vdots \\0&0&\cdots &-2&0&0\\0&0&\cdots &0&0&1\\0&0&\cdots &0&1&0\end{pmatrix}}$

har en determinant av $(-2)^{n}(-1)=(-1)^{n+1}2 ^{n}$ . Således,

$\det {\begin{pmatrix}0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{0n}^{2}&1\\d_{01}^{2}&0&d_ {12}^{2}&\cdots &d_{1n}^{2}&1\\d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\ \\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\ 1&1&1&\cdots &1&0\end{pmatrix}}=\det(P^{T}QP)=\det(Q)\det(P)^{2}=(-1)^{n+1}2^{ n}(n!)^{2}v_{n}^{2}\,.$

Generalisering till hyperbolisk och sfärisk geometri

Det finns sfäriska och hyperboliska generaliseringar. Ett bevis finns här.

I ett sfäriskt utrymme med dimension $(n-1)$ och konstant krökning $1/R^{2}$ , alla $(n +1)$ poäng uppfyller

${\begin{vmatrix}0&f(d_{01})&f(d_{02})&\cdots &f(d_{0n})&1\\f(d_{01})&0&f(d_{12} )&\cdots &f(d_{1n})&1\\f(d_{02})&f(d_{12})&0&\cdots &f(d_{2n})&1\\\vdots &\vdots &\vdots & \ddots &\vdots &\vdots \\f(d_{0n})&f(d_{1n})&f(d_{2n})&\cdots &0&1\\1&1&1&\cdots &1&{\frac {1}{2R^ {2}}}\end{vmatrix}}=0$

där $f(d)=2R^{2}\left(1-\cos {\frac {d}{R}}\right)$ , och $d_{ij}$ är det sfäriska avståndet mellan punkterna $i,j$ .

I ett hyperboliskt utrymme med dimension $(n-1)$ och konstant krökning $-1/R^{2}$ , vilken som helst $(n+1)$ poäng uppfyller

${\begin{vmatrix}0&f(d_{01})&f(d_{02})&\cdots &f(d_{0n})&1\\f(d_{01})&0&f(d_{12} )&\cdots &f(d_{1n})&1\\f(d_{02})&f(d_{12})&0&\cdots &f(d_{2n})&1\\\vdots &\vdots &\vdots & \ddots &\vdots &\vdots \\f(d_{0n})&f(d_{1n})&f(d_{2n})&\cdots &0&1\\1&1&1&\cdots &1&-{\frac {1}{2R ^{2}}}\end{vmatrix}}=0$

där $f(d)=2R^{2}\left(\cosh {\frac {d}{R}}-1\right)$ , och $d_{ij}$ är det hyperboliska avståndet mellan punkterna $i,j$ .

Exempel

I fallet med $n=2$ har vi att $v_{2}$ är arean av en triangel och därför kommer vi att beteckna detta med $A$ . Med Cayley–Menger-determinanten, där triangeln har sidolängderna $a$ , $b$ och $c$ ,

${\begin{aligned}16A^{2}&={\begin{vmatrix}2a^{2}&a ^{2}+b^{2}-c^{2}\\a^{2}+b^{2}-c^{2}&2b^{2}\end{vmatrix}}\\[8pt ]&=4a^{2}b^{2}-(a^{2}+b^{2}-c^{2})^{2}\\[6pt]&=(a^{2} +b^{2}+c^{2})^{2}-2(a^{4}+b^{4}+c^{4})\\[6pt]&=(a+b+ c)(a+bc)(a-b+c)(-a+b+c)\end{aligned}}$

Resultatet på den tredje raden beror på Fibonacci-identiteten . Den sista raden kan skrivas om för att få Herons formel för arean av en triangel med tre sidor, vilket var känt för Arkimedes tidigare.

I fallet med $n=3$ , ger kvantiteten $v_{3}$ volymen av en tetraeder , som vi kommer att beteckna med $V$ . För avstånd mellan $A_{i}$ och $A_{j}$ som ges av $d_{ij}$ ger Cayley–Menger-determinanten

${\begin{aligned}144V^{2}={}&{\frac {1}{2}}{\begin{vmatrix}2d_{01}^{2}&d_{01}^{2} +d_{02}^{2}-d_{12}^{2}&d_{01}^{2}+d_{03}^{2}-d_{13}^{2}\\d_{01} ^{2}+d_{02}^{2}-d_{12}^{2}&2d_{02}^{2}&d_{02}^{2}+d_{03}^{2}-d_{ 23}^{2}\\d_{01}^{2}+d_{03}^{2}-d_{13}^{2}&d_{02}^{2}+d_{03}^{2 }-d_{23}^{2}&2d_{03}^{2}\end{vmatrix}}\\[8pt]={}&4d_{01}^{2}d_{02}^{2}d_{ 03}^{2}+(d_{01}^{2}+d_{02}^{2}-d_{12}^{2})(d_{01}^{2}+d_{03}^ {2}-d_{13}^{2})(d_{02}^{2}+d_{03}^{2}-d_{23}^{2})\\[6pt]&{}- d_{01}^{2}(d_{02}^{2}+d_{03}^{2}-d_{23}^{2})^{2}-d_{02}^{2}( d_{01}^{2}+d_{03}^{2}-d_{13}^{2})^{2}-d_{03}^{2}(d_{01}^{2}+ d_{02}^{2}-d_{12}^{2})^{2}.\end{aligned}}$

Hitta omkretsradien av en simplex

Givet en icke degenererad n -simplex, har den en omskriven n -sfär, med radien $r$ . Då degenereras ( n + 1)-simplexet av n -simplexens hörn och n - sfärens centrum . Det har vi alltså

${\begin{vmatrix}0&r^{2}&r^{2}&r^{2}&\cdots &r^{2}&1\\r^{2}&0&d_{01}^{2}&d_ {02}^{2}&\cdots &d_{0n}^{2}&1\\r^{2}&d_{01}^{2}&0&d_{12}^{2}&\cdots &d_{1n}^ {2}&1\\r^{2}&d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\vdots & \vdots &\ddots &\vdots &\vdots \\r^{2}&d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&1&\ cdots &1&0\end{vmatrix}}=0$

I synnerhet när $n=2$ ger detta omkretsradien av en triangel i termer av dess kantlängder.

Ställ in klassificeringar

Från dessa bestämningsfaktorer har vi även följande klassificeringar:

Hetero

En mängd Λ (med minst tre distinkta element) kallas rak om och endast om , för alla tre element A , B och C i Λ,

$\ det {\begin{bmatrix}0&d(AB)^{2}&d(AC)^{2}&1\\d(AB)^{2}&0&d(BC)^{2}&1\\d(AC)^ {2}&d(BC)^{2}&0&1\\1&1&1&0\end{bmatrix}}=0$

Plan

En mängd Π (med minst fyra distinkta element) kallas plan om och endast om, för alla fyra element A , B , C och D i Π,

$\det {\begin{bmatrix}0&d(AB)^ {2}&d(AC)^{2}&d(AD)^{2}&1\\d(AB)^{2}&0&d(BC)^{2}&d(BD)^{2}&1\\d (AC)^{2}&d(BC)^{2}&0&d(CD)^{2}&1\\d(AD)^{2}&d(BD)^{2}&d(CD)^{2} &0&1\\1&1&1&1&0\end{bmatrix}}=0$

men inte alla trippel av element i Π är raka till varandra;

Platt

En mängd Φ (med minst fem distinkta element) kallas platt om och endast om, för fem element A , B , C , D och E i Φ,

$\det {\begin{bmatrix}0&d(AB)^ {2}&d(AC)^{2}&d(AD)^{2}&d(AE)^{2}&1\\d(AB)^{2}&0&d(BC)^{2}&d(BD) ^{2}&d(BE)^{2}&1\\d(AC)^{2}&d(BC)^{2}&0&d(CD)^{2}&d(CE)^{2}&1\\ d(AD)^{2}&d(BD)^{2}&d(CD)^{2}&0&d(DE)^{2}&1\\d(AE)^{2}&d(BE)^{2 }&d(CE)^{2}&d(DE)^{2}&0&1\\1&1&1&1&1&0\end{bmatrix}}=0$

men inte alla fyrdubblar av element i Φ är plana till varandra; och så vidare.

Mengers sats

Karl Menger gjorde ytterligare en upptäckt efter utvecklingen av Cayley-Menger-determinanten, som blev känd som Mengers sats . Teoremet säger:

En semimetrisk $\rho :A\times A\rightarrow \mathbb {R} _{\geq 0}$ är euklidisk av dimensionen n om och endast om alla Cayley-Menger-determinanter på $n+1$ punkter är strikt positivt, alla determinanter på $n+2$ punkter försvinner, och en Cayley-Menger determinant på minst en uppsättning av $n+ 3$ poäng är icke-negativa (i vilket fall är det nödvändigtvis noll) .

I enklare termer, om varje delmängd av $n+2$ punkter kan vara isometriskt inbäddade i en $n-$ men inte generellt $(n-1) -$ dimensionellt euklidiskt utrymme, då är den semimetriska euklidiska av dimensionen $n$ om inte $A$ består av exakt $n+3$ punkter och Cayley-Menger-determinanten på dessa $n+3$ poäng är strikt negativt. Denna typ av semimetrisk skulle klassificeras som pseudo-euklidisk .

Realisering av en euklidisk distansmatris

Givet Cayley-Menger-relationerna som förklarats ovan, kommer följande avsnitt att ta fram två algoritmer för att avgöra om en given matris är en avståndsmatris som motsvarar en euklidisk punktuppsättning. Den första algoritmen kommer att göra det när den ges en matris OCH dimensionen, $d$ , via en geometrisk begränsningslösningsalgoritm . Den andra algoritmen gör det när dimensionen $d$ inte tillhandahålls. Denna algoritm finner teoretiskt sett en realisering av hela $n\times n$ euklidiska avståndsmatrisen i minsta möjliga inbäddningsdimension i kvadratisk tid.

Sats (d ges)

För skull och sammanhang för följande sats, algoritm och exempel, kommer något annorlunda notation att användas än tidigare vilket resulterar i en ändrad formel för volymen av det $n-1$ dimensionella simplexet nedan än ovan.

Sats. En $n\times n$ matris $\Delta$ är en euklidisk distansmatris om och endast om för alla $k\times k$ submatriser $S$ av $\Delta$ , där $k\leq n$ , $\det({\hat {\delta _{S}}})\geq 0$ . För att $\Delta$ ska ha en realisering i dimension $d$ , om $|S|=k\geq d+2$ , sedan $\det({\hat {\delta _{S}}})=0$ .

Som nämnts tidigare kommer syftet med denna sats från följande algoritm för att realisera en euklidisk avståndsmatris eller en grammatris.

Algoritm

Mata in

euklidisk avståndsmatris $\Delta$ eller Gramian Matrix $\Gamma$ .

Output

Pointset $P$

Procedur

• Om dimensionen $d$ är fixerad kan vi lösa ett system av polynomekvationer, en för varje inre produktpost av $\Gamma$ , där variablerna är koordinaterna för varje punkt $p_{1},...,p_{n}$ i önskad dimension $d$ .
• Annars kan vi lösa för en punkt i taget.
  • Lös koordinaterna för $p_{k}$ med hjälp av dess avstånd till alla tidigare placerade punkter $p_{1},...,p_{k-1}$ . Således $p_{k}$ av högst $k-1$ -koordinatvärden, vilket säkerställer minsta dimension och komplexitet.

Exempel

Låt varje punkt $p_{k}$ ha koordinater ${p_{k}^{1},p_{k}^{2},...}$ . För att placera de tre första poängen:

1. Sätt $p_{1}$ vid origo, så $p_{1}={0,0,...}$ .
2. Sätt $p_{2}$ på första axeln, så $p_{2}={(\delta _{12})^{2},0,...}$ .
3. För att placera $p_{3}$ :

${\begin{cases}(p_{1}^{1}-p_{3}^{1})^{2}+(p_{1}^{2}-p_{ 3}^{2})^{2}=(\delta _{13})^{2}\\(p_{2}^{1}-p_{3}^{1})^{2}+ (p_{2}^{2}-p_{3}^{2})^{2}=(\delta _{23})^{2}\end{cases}}$$\rightarrow {\begin{cases}p_{3}^{1}={\frac {(\delta _{12})^ {2}+(\delta _{13})^{2}-(\delta _{23})^{2}}{2\delta _{12}}}\\p_{3}^{2} ={\frac {\sqrt {(\delta _{31}+\delta _{32}+\delta _{12})(\delta _{31}+\delta _{32}-\delta _{12 })(\delta _{31}-\delta _{32}+\delta _{12})(-\delta _{31}+\delta _{32}+\delta _{12})}}{ 2\delta _{01}}}\end{cases}}$

För att hitta en realisering med användning av ovanstående algoritm måste diskriminanten för det kvadratiska avståndssystemet vara positiv, vilket är ekvivalent med $\Delta p_{1}p_{2}p_{3}$ har positiv volym. I allmänhet ges volymen av det $n-1$ dimensionella simplexet som bildas av de $n$ hörnen av

$V_{n-1}^{2}={\frac {(-1)^ {n}}{2^{n-1}(n-1!)^{2}}}\det({\hat {\Delta }})$ .

I den här formeln ovan är $\det({\hat {\Delta }})$ Cayley-Menger-determinanten. Denna volym är positiv är ekvivalent med att determinanten för volymmatrisen är positiv.

Sats (d ej givet)

Låt K vara ett positivt heltal och D vara en × n symmetrisk ihålig matris med icke-negativa element, med n ≥ 2. D är en euklidisk avståndsmatris med dim(D) = K om och endast om det finns ${\displaystyle \{x_{i}\}_{i=1}^{n}\subseteq \mathbb {R} ^{K}} och$ en indexuppsättning I = $\{i_{1},...,i_{K+1}\}\subseteq I_{n}$ så att

${\begin {fall}x_{i}=0\\x_{i_{j}}(j-1)\neq 0,&{\mbox{ }}j\in I_{2,K+1}\\x_{i_ {j}}(i)=0,&{\mbox{ }}j\in I_{2,K},i\in I_{j,K},\end{cases}}$

där $\{x_{i}\}_{i=1}^{n}$ realiserar D, där $x_{h}(l)$ betecknar ${\displaystyle l^{th}}-$ komponenten i vektorn ${\displaystyle h^{th}} .$

Det omfattande beviset för denna sats kan hittas i följande referens.

Algoritm - K = edmsph( D, x )

$I=\{1,2\}$$K=1$$(x_{1 },x_{2})=(0,{\sqrt {D_{12}}})$${\text{för i}}\in \{3,...,n\}{\text{do}}$

Γ $=\bigcap _{j\in I}S^{K}(x_{j},D_{ij})$

om Γ ${ \displaystyle =}$ ∅;

returnera ∞

sedan

annars om Γ ${\displaystyle =\{p_{i}\}{\text{ }}då} x$

$\displaystyle x_{i}=p_{ i}}$

annars om Γ $=\{p_{i}^{+},p_{i}^{-}\}{\text{ } }då$

$x_{i}=p_{i}^{+}$

$x$ ← expand( $x$ )

I ← I ∪ { i }

K ← K + 1

annat

fel : dim aff(span( $x_{j}$ )) < K - 1

slut om

slut för retur K

Se även

• Avståndsgeometri
  
• Euklidiska rymden
  
• Euklidisk distansmatris
  
• Simplex
  
• Herons formel