Определитель Кэли–Менгера

Формула для «объема» n-симплекса

В линейной алгебре , геометрии и тригонометрии определитель Кэли–Менгера — это формула для содержимого, т. е. многомерного объема , -мерного симплекса в терминах квадратов всех расстояний между парами его вершин. Определитель назван в честь Артура Кэли и Карла Менгера . ${\textstyle n}$

Парные полиномы расстояний между n точками в реальном евклидовом пространстве являются евклидовыми инвариантами, связанными с помощью соотношений Кэли-Менгера . ^[1] Эти соотношения служили нескольким целям, таким как обобщение формулы Герона, вычисление содержимого n -мерного симплекса и, в конечном счете, определение того, является ли любая вещественная симметричная матрица евклидовой матрицей расстояний в области геометрии расстояний . ^[2] ${\displaystyle {n \choose 2}}$

История

Карл Менгер был молодым профессором геометрии в Венском университете, а Артур Кейли был британским математиком, который специализировался на алгебраической геометрии. Менгер расширил алгебраическое превосходство Кейли, чтобы предложить новую аксиому метрических пространств, используя концепции геометрии расстояний и отношения конгруэнтности, известные как определитель Кейли–Менгера. Это привело к обобщению одного из первых открытий в геометрии расстояний , формулы Герона , которая вычисляет площадь треугольника, зная длины его сторон. ^[3]

Определение

Пусть будут точками в -мерном евклидовом пространстве , причем . ^[a] Эти точки являются вершинами n -мерного симплекса: треугольника при ; тетраэдра при , и так далее. Пусть будут евклидовыми расстояниями между вершинами и . Содержание, т.е. n -мерный объем этого симплекса, обозначаемый как , может быть выражено как функция определителей некоторых матриц следующим образом: ^{[4] [5]} ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ ${\displaystyle n+1}$ ${\displaystyle k}$ ${\displaystyle k\geq n}$ ${\displaystyle n=2}$ ${\displaystyle n=3}$ ${\textstyle d_{ij}}$ ${\displaystyle A_{i}}$ ${\textstyle A_{j}}$ ${\displaystyle v_{n}}$

$${\displaystyle {\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}}}$$

Это определитель Кэли–Менгера . Так как это симметричный многочлен от 's и, таким образом, он инвариантен относительно перестановки этих величин. Это неверно для , но он всегда инвариантен относительно перестановки вершин. ^[b] ${\displaystyle n=2}$ ${\displaystyle d_{ij}}$ ${\displaystyle n>2,}$

За исключением последней строки и столбца, состоящих из единиц, матрица во второй форме этого уравнения представляет собой матрицу евклидовых расстояний .

Особые случаи

2-Симплекс

Повторим, симплекс — это n- мерный многогранник и выпуклая оболочка точек , которые не лежат ни в одной размерной плоскости. ^[6] Поэтому 2-симплекс возникает, когда и симплекс приводит к треугольнику. Поэтому формула для определения треугольника приведена ниже: ^[5] ${\displaystyle n+1}$ ${\displaystyle (n-1)}$ ${\displaystyle n=2}$ ${\displaystyle V_{j}^{2}}$

${\displaystyle -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}}}$

В результате приведенное выше уравнение представляет собой содержимое 2-симплекса (площадь плоского треугольника со сторонами длиной , , и ) и является обобщенной формой формулы Герона. ^[5] ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

3-Симплекс

Аналогично, 3-симплекс возникает, когда и симплекс приводит к тетраэдру. ^[6] Поэтому формула для определения тетраэдра приведена ниже: ^[5] ${\displaystyle n=3}$ ${\displaystyle V_{j}^{2}}$

${\displaystyle 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}}}$

В результате уравнение выше представляет содержимое 3-симплекса, который является объемом тетраэдра, где ребро между вершинами и имеет длину . ^[5] ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle d_{ij}}$

Доказательство

Пусть векторы-столбцы будут точками в -мерном евклидовом пространстве. Начиная с формулы объема ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ ${\displaystyle n+1}$ ${\displaystyle n}$

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

мы замечаем, что определитель не меняется, когда мы добавляем дополнительную строку и столбец, чтобы создать матрицу, ${\displaystyle (n+2)\times (n+2)}$

${\displaystyle 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}}\,,}$

где - квадрат длины вектора . Кроме того, отметим, что матрица ${\displaystyle \|A_{j}\|^{2}}$ ${\displaystyle A_{j}}$ ${\displaystyle (n+2)\times (n+2)}$

${\displaystyle Q={\begin{pmatrix}-2&0&\cdots &0&0&0\\0&-2&\cdots &0&0&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}}}$

имеет определитель . Таким образом, ^[7] ${\displaystyle (-2)^{n}(-1)=(-1)^{n+1}2^{n}}$

${\displaystyle \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}\,.}$

Пример

В случае , имеем, что является площадью треугольника и , таким образом, мы обозначим это как . По определителю Кэли–Менгера, где треугольник имеет длины сторон , и , ${\displaystyle n=2}$ ${\displaystyle v_{2}}$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

${\displaystyle {\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+b-c)(a-b+c)(-a+b+c)\end{aligned}}}$

Результат в третьей строке обусловлен тождеством Фибоначчи . Последнюю строку можно переписать, чтобы получить формулу Герона для площади треугольника по трем сторонам, которая была известна еще Архимеду. ^[8]

В случае величина дает объем тетраэдра , который мы обозначим через . Для расстояний между и , заданных как , определитель Кэли–Менгера дает ^{[9] [10]} ${\displaystyle n=3}$ ${\displaystyle v_{3}}$ ${\displaystyle V}$ ${\displaystyle A_{i}}$ ${\displaystyle A_{j}}$ ${\displaystyle d_{ij}}$

${\displaystyle {\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}}}$

Нахождение радиуса описанной окружности симплекса

Если задан невырожденный n -симплекс, то он имеет описанную n -сферу с радиусом . Тогда ( n  + 1)-симплекс, составленный из вершин n -симплекса и центра n -сферы, вырожден. Таким образом, имеем ${\displaystyle r}$

${\displaystyle {\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}$

В частности, когда , это дает радиус описанной окружности треугольника через длины его сторон. ${\displaystyle n=2}$

Установить классификации

Из этих детерминант мы также имеем следующие классификации:

Прямой

Множество Λ (содержащее по крайней мере три различных элемента) называется прямым тогда и только тогда , когда для любых трех элементов A , B и C из Λ, ^[11]

${\displaystyle \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}$

Самолет

Множество Π (содержащее по крайней мере четыре различных элемента) называется плоским тогда и только тогда, когда для любых четырех элементов A , B , C и D множества Π, ^[11]

${\displaystyle \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}$

но не все тройки элементов Π прямолинейны друг к другу;

Плоский

Множество Φ (содержащее по крайней мере пять различных элементов) называется плоским тогда и только тогда, когда для любых пяти элементов A , B , C , D и E множества Φ ^[11]

${\displaystyle \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}$

но не все четверки элементов Φ лежат в одной плоскости друг с другом; и так далее.

Теорема Менгера

Карл Менгер сделал еще одно открытие после разработки определителя Кэли–Менгера, которое стало известно как теорема Менгера . Теорема гласит:

Полуметрика является евклидовой размерности n тогда и только тогда, когда все определители Кэли-Менгера в точках строго положительны, все определители в точках равны нулю, а определитель Кэли-Менгера хотя бы в одном наборе точек неотрицателен (в этом случае он обязательно равен нулю) ^[1] . ${\displaystyle \rho :A\times A\rightarrow \mathbb {R} _{\geq 0}}$ ${\displaystyle n+1}$ ${\displaystyle n+2}$ ${\displaystyle n+3}$

Проще говоря, если каждое подмножество точек может быть изометрически вложено в, но не в общем случае, размерное евклидово пространство, то полуметрика является евклидовой размерности, если только она не состоит ровно из точек, а определитель Кэли–Менгера в этих точках строго отрицателен. Этот тип полуметрики будет классифицирован как псевдоевклидова . ^[1] ${\displaystyle n+2}$ ${\displaystyle n-}$ ${\displaystyle (n-1)-}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle n+3}$ ${\displaystyle n+3}$

Реализация матрицы евклидовых расстояний

Учитывая соотношения Кэли-Менгера, как объяснено выше, в следующем разделе будут представлены два алгоритма для определения того, является ли заданная матрица матрицей расстояний, соответствующей евклидову множеству точек. Первый алгоритм сделает это, когда дана матрица И размерность, , с помощью алгоритма решения геометрических ограничений. Второй алгоритм делает это, когда размерность, , не указана. Этот алгоритм теоретически находит реализацию полной евклидовой матрицы расстояний в наименьшей возможной размерности вложения за квадратичное время. ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle n\times n}$

Теорема (d дано)

Для целей и контекста следующей теоремы, алгоритма и примера будут использоваться несколько иные обозначения, чем прежде, что приведет к изменению формулы для объема размерного симплекса ниже, чем выше. ${\displaystyle n-1}$

Теорема. Матрица является евклидовой матрицей расстояний тогда и только тогда, когда для всех подматриц , где , . Для того чтобы иметь реализацию в размерности , если , то . ^[12] ${\displaystyle n\times n}$ ${\displaystyle \Delta }$ ${\displaystyle k\times k}$ ${\displaystyle S}$ ${\displaystyle \Delta }$ ${\displaystyle k\leq n}$ ${\displaystyle \det({\hat {\delta _{S}}})\geq 0}$ ${\displaystyle \Delta }$ ${\displaystyle d}$ ${\displaystyle |S|=k\geq d+2}$ ${\displaystyle \det({\hat {\delta _{S}}})=0}$

Как уже говорилось, цель этой теоремы вытекает из следующего алгоритма реализации матрицы евклидовых расстояний или матрицы Грама.

Алгоритм

Вход

Матрица евклидовых расстояний или матрица Грама . ${\displaystyle \Delta }$ ${\displaystyle \Gamma }$

Выход

Pointset ${\displaystyle P}$

Процедура

• Если размерность фиксирована, мы можем решить систему полиномиальных уравнений, по одному для каждого элемента внутреннего произведения , где переменные являются координатами каждой точки в требуемой размерности . ${\displaystyle d}$ ${\displaystyle \Gamma }$ ${\displaystyle p_{1},...,p_{n}}$ ${\displaystyle d}$
• В противном случае мы можем решать задачу по одной точке за раз.
  • Решить для координат, используя его расстояния до всех ранее размещенных точек . Таким образом, представлено не более чем значениями координат, что обеспечивает минимальную размерность и сложность. ${\displaystyle p_{k}}$ ${\displaystyle p_{1},...,p_{k-1}}$ ${\displaystyle p_{k}}$ ${\displaystyle k-1}$

Пример

Пусть каждая точка имеет координаты . Чтобы разместить первые три точки: ${\displaystyle p_{k}}$ ${\displaystyle {p_{k}^{1},p_{k}^{2},...}}$

1. Положим в начало координат, так что . ${\displaystyle p_{1}}$ ${\displaystyle p_{1}={0,0,...}}$
2. Поставьте на первую ось, так . ${\displaystyle p_{2}}$ ${\displaystyle p_{2}={(\delta _{12})^{2},0,...}}$
3. Разместить : ${\displaystyle p_{3}}$

${\displaystyle {\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}}}$ ${\displaystyle \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}}}$

Для того, чтобы найти реализацию с помощью вышеприведенного алгоритма, дискриминант квадратичной системы расстояний должен быть положительным, что эквивалентно наличию положительного объема. В общем случае объем размерного симплекса, образованного вершинами, определяется как ^[12] ${\displaystyle \Delta p_{1}p_{2}p_{3}}$ ${\displaystyle n-1}$ ${\displaystyle n}$

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

В этой формуле выше — определитель Кэли–Менгера. Положительный знак этого объема эквивалентен положительному знаку определителя матрицы объема. ${\displaystyle \det({\hat {\Delta }})}$

Теорема (d не дано)

Пусть K — положительное целое число, а D — симметричная полая матрица размера × n с неотрицательными элементами, где n ≥ 2. D является евклидовой матрицей расстояний с dim(D) = K тогда и только тогда, когда существуют и индексный набор I = такой, что ${\displaystyle \{x_{i}\}_{i=1}^{n}\subseteq \mathbb {R} ^{K}}$ ${\displaystyle \{i_{1},...,i_{K+1}\}\subseteq I_{n}}$

${\displaystyle {\begin{cases}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, где обозначает компонент вектора . ${\displaystyle \{x_{i}\}_{i=1}^{n}}$ ${\displaystyle x_{h}(l)}$ ${\displaystyle l^{th}}$ ${\displaystyle h^{th}}$

Подробное доказательство этой теоремы можно найти по следующей ссылке. ^[13]

Алгоритм - K = edmsph(Д, х)

Источник: ^[13]

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

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

если Γ ∅; тогда ${\displaystyle =}$

возврат ∞

иначе если Γ ${\displaystyle =\{p_{i}\}{\text{ }}then}$

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

иначе если Γ ${\displaystyle =\{p_{i}^{+},p_{i}^{-}\}{\text{ }}then}$

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

${\displaystyle x}$← развернуть( ) ${\displaystyle x}$

Я ← Я ∪ { я }

К ← К + 1

еще

ошибка : dim aff(span( )) < K - 1 ${\displaystyle x_{j}}$

конец, если

конец для возврата К

Смотрите также

• Дистанционная геометрия
  
• Евклидово пространство
  
• Матрица евклидовых расстояний
  
• Симплекс
  
• Формула Герона

Примечания

1. N -мерное тело не может быть погружено в k -мерное пространство, если ${\displaystyle k<n.}$
2. (Гипер)объем фигуры не зависит от порядка нумерации ее вершин.

Ссылки

1. Sitharam, Meera; St. John, Audrey; Sidman, Jessica. Справочник по принципам геометрических систем ограничений . Boca Raton, FL: CRC Press. ISBN  978-1-4987-3891-0
2. http://ufo2.cise.ufl.edu/index.php/Distance_Geometry Геометрия расстояний
3. Шесть математических жемчужин из истории дистанционной геометрии
4. Sommerville, DMY (1958). Введение в геометрию n измерений . Нью-Йорк: Dover Publications.
5. Определитель Кэли-Менгера
6. Симплексная энциклопедия математики
7. "Simplex Volumes and the Cayley–Menger Determinant". www.mathpages.com . Архивировано из оригинала 16 мая 2019 . Получено 2019-06-08 .
8. Хит, Томас Л. (1921). История греческой математики (т. II) . Oxford University Press. стр. 321–323.
9. Одет, Дэниел. «Сферические и гиперболические определители Кэли – Менгера» (PDF) . Бюллетень AMQ . ЛИ : 45–52.
10. Дёрри, Генрих (1965). 100 великих проблем элементарной математики . Нью-Йорк: Dover Publications. С. 285–9.
11. Вики-страница геометрии расстояний
12. Sitharam, Meera. "Lecture 1 through 6"." Геометрическая сложность CIS6930, Университет Флориды. Получено 28 марта 2020 г.
13. Реализация евклидовых матриц расстояний путем пересечения сфер