케일리-멩거 행렬식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

케일리-멩거 행렬식은 음이 아닌 정수 n에 대해 정의되는 (n+2) x (n+2) 행렬식으로, n(n+1)/2개의 변수를 갖는 다항식이다. 이 행렬식은 n+1개의 점으로 이루어진 단순체의 n차원 부피를 유클리드 거리로 표현하는 데 사용되며, 특히 삼각형의 넓이와 사면체의 부피를 계산하는 데 활용된다. 케일리-멩거 행렬식은 변수의 순열에 불변이며, 표수가 2가 아닌 체 위에서는 2n차 동차 다항식이다. 또한, 케일리-멩거 행렬식을 통해 주어진 행렬이 유클리드 거리 행렬인지 여부를 판단하고, 유클리드 공간에서 점 집합을 찾는 알고리즘을 제시할 수 있다.

더 읽어볼만한 페이지

계량기하학 - 거리
거리는 수학에서 두 점 사이를 측정하는 함수, 물리학에서 물체의 위치 변화량, 일상생활에서 두 지점 사이의 길이를 의미하며, 국제단위계에서는 길이로 표현된다.
계량기하학 - 코시 열
코시 열은 무한수열에서 항들이 뒤로 갈수록 서로 가까워지는 수열로, 수렴열은 항상 코시 열이지만 그 역은 성립하지 않을 수 있으며, 실수의 완비성 정의 및 무한급수 수렴성 판정에 중요한 역할을 하는 개념이다.
행렬 - 스핀 (물리학)
스핀은 양자역학적 각운동량으로, 양자화된 값을 가지며 자기 쌍극자 모멘트를 유발하여 다양한 분야에 응용되고 스핀트로닉스 기술 발전에 기여하지만, 전자의 스핀 기원은 아직 완전히 밝혀지지 않았다.
행렬 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.

케일리-멩거 행렬식
개요
유형	행렬식
분야	기하학
발명가	아서 케일리, 카를 멩거
용도	단순체의 부피 계산
정의
케일리-멩거 행렬	점들 사이의 거리를 포함하는 행렬
케일리-멩거 행렬식	케일리-멩거 행렬의 행렬식
활용
n-단순체의 부피	케일리-멩거 행렬식을 사용하여 계산
관련 개념
거리 공간	점들 사이의 거리가 정의된 공간
유클리드 공간	유클리드 거리가 정의된 공간
단순체	점, 선, 삼각형, 사면체 등의 일반화된 형태

2. 정의

음이 아닌 정수 $n$ 에 대하여, $n$ 번째 '''케일리-멩거 행렬식''' $M_n$ 은 다음과 같은 $(n+2)\times(n+2)$ 행렬식으로 나타낸 $\textstyle\frac{n(n+1)}2$ 변수 다항식이다.^[14]

: $M_n(x_{ij}\colon 0\le i$

$k$ 차원 유클리드 공간에 $n+1$ 개의 점 $A_0, A_1,\ldots, A_n$ 가 있고( $k \ge n$ ), 이 점들은 $n$ 차원 단순체의 꼭짓점이다. $n = 2$ 일 때는 삼각형, $n = 3$ 일 때는 사면체 등이다. $d_{ij}$ 를 꼭짓점 $A_i$ 와 $A_j$ 사이의 유클리드 거리라고 하면, 이 단순체의 $n$ 차원 부피 $v_n$ 은 다음과 같이 표현할 수 있다.^[4]^[5]

: $v_n^2 = \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}$

이것이 케일리-멩거 행렬식이다.

3. 성질

케일리-멩거 행렬식 $M_n$ 은 대칭 다항식으로, 변수의 순열에 대해 불변한다.

표수가 2가 아닌 체 위에서, 케일리-멩거 행렬식 $M_n$ 는 $2n$ 차 동차 다항식이다.^[15]

표수가 2가 아닌 체 위에서, $n\ne 2$ 일 때 케일리-멩거 행렬식 $M_n$ 은 기약 다항식이다.^[15]

꼭짓점 $v_0,\dots,v_n$ 를 갖는 $\mathbb R^n$ 속 $n$ 차원 단체 $S$ 의 $n$ 차원 초부피 $\operatorname{Vol}_n(S)$ 는 다음과 같이 나타낼 수 있다.

: $\operatorname{Vol}_n(S)^2=\frac{(-1)^{n+1}}{2^n(n!)^2}M_n(\Vert v_i-v_j\Vert\colon 0\le i$

우변의 계수의 $n=0,1,2,\dots$ 번째 값은 -1, 2, -16, 288, -9216, 460800, ...이다.

4. 역사

아서 케일리와 카를 멩거의 이름을 따서 지어졌다.^[3]

카를 멩거는 빈 대학교의 기하학 교수였고, 아서 케일리는 대수 기하학을 전공한 영국의 수학자였다. 멩거는 케일리의 대수적 결과를 확장하여, 케일리-멩거 행렬식으로 알려진 합동 동치까지의 거리 기하학 개념을 사용하여 거리 공간의 새로운 공리를 제안했다. 이는 거리 기하학의 첫 번째 발견 중 하나인 헤론의 공식을 일반화한 것으로, 헤론의 공식은 삼각형의 변의 길이를 알 때 삼각형의 면적을 계산한다.^[3]

5. 특수한 경우

n = 2인 경우, 2-단순체는 삼각형이 되며, 삼각형의 넓이를 결정하는 공식은 헤론의 공식과 관련이 있다.^[5] n = 3인 경우, 3-단순체는 사면체가 되며, 사면체의 부피를 결정하는 공식이 존재한다.^[5]^[6]

5. 1. 2-단순체 (삼각형)

2-심플렉스는 n = 2일 때 발생하며, 삼각형이 된다. 삼각형의 넓이(

\Delta

)를 결정하는 공식은 다음과 같다.^[5]

:

-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-심플렉스(변의 길이가

a

,

b

,

c

인 평면 삼각형의 넓이)의 내용을 나타내며, 이는 헤론의 공식의 일반화된 형태이다.^[5]

5. 2. 3-단순체 (사면체)

3-단순체는

n=3

일 때 발생하며, 단순체는 사면체를 생성한다.^[6] 따라서 사면체의 부피

V

를 결정하는 공식은 다음과 같다.^[5]

:

288 V^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-단순체의 내용을 나타내며, 이는 꼭짓점

i

와

j

사이의 변의 길이가

d_{ij}

인 사면체의 부피이다.^[5]

6. 증명

$k$ 차원 유클리드 공간에 $n+1$ 개의 점 $A_0, A_1,\ldots, A_n$ 가 있고, $k \ge n$ 이다. 이 점들은 $n$ 차원 단순체의 꼭짓점이다. $d_{ij}$ 를 꼭짓점 $A_i$ 와 $A_j$ 사이의 유클리드 거리라고 할 때, 이 단순체의 $n$ 차원 부피 $v_n$ 은 다음과 같이 표현할 수 있다.^[4]^[5]

: $v_n^2 = \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}.$

이것은 '''케일리-멩거 행렬식'''이다.

단순체의 부피 공식은 다음과 같다.

: $v_n = \frac{1}{n!} \left| \det \begin{pmatrix}A_0 & A_1 & \cdots & A_n \\1 & 1 & \cdots & 1\end{pmatrix} \right|\,.$

행렬식은 추가적인 행과 열을 더하여 $(n+2)\times(n+2)$ 행렬을 만들어도 변하지 않는다는 성질을 이용한다.

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

여기서 $\|A_j\|^2$ 는 벡터 $A_j$ 의 길이의 제곱이다. 또한, $(n+2)\times(n+2)$ 행렬

: $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}

의 행렬식은

(-2)^n(-1) = (-1)^{n+1} 2^n

이다.^[7]

따라서, 다음이 성립한다.

:

\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 Q P) = \det(Q) \det(P)^2 = (-1)^{n+1} 2^n (n!)^2 v_n^2\,.

7. 예시

$n = 2$ 인 경우, $v_2$ 는 삼각형의 면적이므로, 이를 $A$ 로 표기한다. 케일리-멩거 행렬식에 의해, 삼각형의 변의 길이가 $a$ , $b$ 및 $c$ 일 때 다음과 같다.

: $\begin{align}16A^2 &= \begin{vmatrix} 2a^2 & a^2+b^2-c^2 \\ a^2+b^2-c^2 & 2b^2 \end{vmatrix} \\[8pt]&= 4a^2b^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{align}$

위 식의 세 번째 줄은 피보나치 항등식에 의한 것이다. 마지막 줄은 세 변이 주어졌을 때 삼각형의 면적을 구하는 헤론의 공식으로 다시 쓸 수 있으며, 이는 이미 아르키메데스 시대에 알려져 있었다.^[8]

$n=3$ 인 경우, $v_3$ 는 사면체의 부피를 나타내며, 이를 $V$ 로 표기한다. $A_i$ 와 $A_j$ 사이의 거리가 $d_{ij}$ 로 주어질 때, 케일리-멩거 행렬식은 다음과 같다.^[9]^[10]

: $\begin{align}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{align}$

7. 1. 외접구의 반지름

n^영어-단체(simplex)의 외접 n^영어-구(sphere)의 반지름은 케일리-멩거 행렬식을 이용하여 계산할 수 있다. 비퇴화 n^영어-단체가 주어지면, 반지름

r

을 갖는 외접 n^영어-구를 갖는다. n^영어-단체의 꼭짓점과 n^영어-구의 중심을 이루는 -단체는 퇴화된다. 따라서 다음을 얻는다.^[15]

:

\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

특히,

n = 2

일 때, 이는 변의 길이를 사용하여 삼각형의 외접원의 반지름을 구하는 공식을 제공한다.

8. 집합 분류

케일리-멩거 행렬식을 통해 점 집합의 기하학적 성질을 분류할 수 있다. 예를 들어, 점 집합이 직선, 평면, 또는 평평한지 여부를 판별할 수 있다.^[11] 이러한 분류는 하위 섹션에서 더 자세히 설명된다.

직선 (하위 섹션 참고)
평면 (하위 섹션 참고)
평평함 (하위 섹션 참고)

8. 1. 직선 (Straight)

집합 (적어도 세 개의 서로 다른 원소를 가짐)는 임의의 세 원소 , , 에 대해 아래 조건을 만족할 때 '''직선'''이라고 한다.^[11]

:

\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

8. 2. 평면 (Plane)

집합 (최소한 4개의 서로 다른 원소를 가짐)은 다음 조건을 만족할 때 '''평면'''이라고 불린다. 임의의 네 원소 , , 및 가 에 속할 때,^[11]

::

\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

하지만 의 모든 세 원소 쌍이 서로 일직선상에 있지는 않다.

8. 3. 평평함 (Flat)

집합

\Phi

(5개 이상의 서로 다른 원소를 가짐)는 다음 조건을 만족할 경우 '''평평하다'''고 한다.^[11]

\Phi

의 임의의 원소

A

,

B

,

C

,

D

,

E

에 대해

:

\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

단,

\Phi

의 모든 네 원소들이 서로 평면에 있지 않다.

9. 멩거의 정리

칼 멩거는 케일리-멩거 행렬식 개발 이후 멩거의 정리(Menger's Theorem)를 발견했다.^[1] 이 정리는 다음과 같다.

유한한 점들의 집합 $A$ 에 대해, 반계량 $\rho: A \times A \rightarrow \mathbb{R}_{\geq0}$ 이 $n$ 차원 유클리드 거리에서 얻어지기 위한 필요충분조건은 $n+1$ 개의 모든 점에 대한 케일리-멩거 행렬식이 양수이고, $n+2$ 개의 모든 점에 대한 행렬식이 0이며, 적어도 하나의 $n+3$ 개 점 집합에 대한 케일리-멩거 행렬식이 음이 아닌 경우(이 경우 반드시 0)이다.^[1]

좀 더 간단히 말하면, $n+2$ 개의 모든 부분 집합이 $n$ 차원 유클리드 공간에 등거리적으로 임베딩될 수 있다면(일반적으로 $(n-1)$ 차원이 아님), 반계량은 $n$ 차원 유클리드 공간에 해당한다. 단, $A$ 가 정확히 $n+3$ 개의 점으로 구성되어 있고 해당 $n+3$ 개 점에 대한 케일리-멩거 행렬식이 음수인 경우는 예외이다. 이러한 유형의 반계량은 "유사 유클리드"로 분류된다.^[1]

10. 유클리드 거리 행렬의 실현

케일리-멩거 관계를 바탕으로, 주어진 행렬이 유클리드 점 집합에 해당하는 거리 행렬인지 판별하는 두 가지 알고리즘이 제시된다. 첫 번째 알고리즘은 행렬과 차원 $d$ 가 주어졌을 때 기하 제약 해결 알고리즘을 통해 이를 수행한다. 두 번째 알고리즘은 차원 $d$ 가 주어지지 않을 때 수행되며, 전체 $n \times n$ 유클리드 거리 행렬의 실현을 가능한 가장 작은 임베딩 차원에서 이차 시간 내에 찾는 방법이다.

10. 1. 정리 (d가 주어진 경우)

'''정리.'''

n \times n

행렬

\Delta

가 유클리드 거리 행렬이 될 필요충분조건은

\Delta

의 모든

k \times k

부분 행렬

S

에 대해,

k \leq n

일 때,

\det (\hat{\delta_S}) \geq 0

인 것이다.

\Delta

가

d

차원에서 실현되려면, 만약

|S| = k \geq d + 2

이면,

\det (\hat{\delta_S}) = 0

이다.^[12]

10. 1. 1. 알고리즘

주어진 유클리드 거리 행렬 또는 그람 행렬로부터 점 집합을 찾는 절차는 다음과 같다.

; 입력

: 유클리드 거리 행렬

\Delta

또는 그람 행렬

\Gamma

.

; 출력

: 점 집합

P

; 절차

차원 $d$ 가 고정되어 있는 경우, 변수가 원하는 차원 $d$ 에서 각 점 $p_1, ..., p_n$ 의 좌표인 그람 행렬 $\Gamma$ 의 각 내적 항목에 대해 다항 방정식 시스템을 하나씩 풀 수 있다.
그렇지 않은 경우, 한 번에 한 점씩 풀 수 있다.
* 이전에 배치된 모든 점 $p_1, ..., p_{k-1}$ 까지의 거리를 사용하여 $p_k$ 의 좌표를 푼다. 따라서 $p_k$ 는 최대 $k - 1$ 개의 좌표 값으로 표시되어 최소 차원과 복잡성을 보장한다.

각 점

p_k

는 좌표

\{p^1_k, p^2_k, ...\}

를 갖는다. 처음 세 점을 배치하는 방법은 다음과 같다.

#

p_1

을 원점에 놓으므로

p_1 = \{0,0,...\}

이다.

#

p_2

를 첫 번째 축에 놓으므로

p_2 = \{(\delta_{12})^2, 0, ...\}

이다.

#

p_3

를 배치하려면:

\begin{cases}(p^1_1 - p^1_3)^2 + (p^2_1 - p^2_3)^2 = (\delta_{13})^2\\(p^1_2 - p^1_3)^2 + (p^2_2 - p^2_3)^2 = (\delta_{23})^2\end{cases}

\rightarrow\begin{cases}p^1_3 = \frac{(\delta_{12})^2 + (\delta_{13})^2 - (\delta_{23})^2}{2 \delta_{12}}\\p^2_3 = \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}

위 알고리즘을 사용하여 실현을 찾으려면 거리 이차 시스템의 판별식이 양수여야 하며, 이는

\Delta p_1p_2p_3

가 양의 부피를 갖는 것과 동일하다. 일반적으로

n

개의 정점으로 형성된

n-1

차원 단순체의 부피는 다음 공식으로 주어진다.^[12]

V^{2}_{n-1} = \frac{(-1)^{n}}{2^{n-1} (n-1!)^{2}} \det (\hat{\Delta})

.

이 공식에서

\det (\hat{\Delta})

는 케일리-멩거 행렬식이다. 이 부피가 양수라는 것은 부피 행렬의 행렬식이 양수라는 것과 같다.

10. 1. 2. 예시

위에 설명된 케일리-멩거 관계를 바탕으로, 주어진 행렬이 유클리드 점 집합에 해당하는 거리 행렬인지 여부를 결정하는 두 가지 알고리즘이 제시된다.

첫 번째 알고리즘은 행렬과 차원

d

가 주어졌을 때 기하 제약 해결 알고리즘을 통해 이를 수행한다. 두 번째 알고리즘은 차원

d

가 제공되지 않을 때 수행된다. 이 알고리즘은 이론적으로 전체

n \times n

유클리드 거리 행렬의 실현을 가능한 가장 작은 임베딩 차원에서 이차 시간 내에 찾는다.

알고리즘의 절차는 다음과 같다.

차원 $d$ 가 고정되어 있는 경우, 변수가 원하는 차원 $d$ 에서 각 점 $p_1, ..., p_n$ 의 좌표인 그람 행렬 $\Gamma$ 의 각 내적 항목에 대해 다항 방정식 시스템을 하나씩 풀 수 있다.
그렇지 않은 경우, 한 번에 한 점씩 풀 수 있다.
이전에 배치된 모든 점 $p_1, ..., p_{k-1}$ 까지의 거리를 사용하여 $p_k$ 의 좌표를 푼다. 따라서 $p_k$ 는 최대 $k - 1$ 개의 좌표 값으로 표시되어 최소 차원과 복잡성을 보장한다.

각 점

p_k

는 좌표

{p^1_k, p^2_k, ...}

를 갖는다. 처음 세 점을 배치하는 방법은 다음과 같다.

1.

p_1

을 원점에 놓으므로

p_1 = {0,0,...}

이다.

2.

p_2

를 첫 번째 축에 놓으므로

p_2 = {(\delta_{12})^2, 0, ...}

이다.

3.

p_3

를 배치하려면:

:

\begin{cases}    (p^1_1 - p^1_3)^2 + (p^2_1 - p^2_3)^2 = (\delta_{13})^2\\    (p^1_2 - p^1_3)^2 + (p^2_2 - p^2_3)^2 = (\delta_{23})^2    \end{cases}

:

\rightarrow    \begin{cases}    p^1_3 = \frac{(\delta_{12})^2 + (\delta_{13})^2 - (\delta_{23})^2}{2 \delta_{12}}\\    p^2_3 = \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}

위 알고리즘을 사용하여 실현을 찾으려면 거리 이차 시스템의 판별식이 양수여야 하며, 이는

\Delta p_1p_2p_3

가 양의 부피를 갖는 것과 동일하다.^[12] 일반적으로

n

개의 정점으로 형성된

n-1

차원 단순체의 부피는 다음 공식으로 주어진다.

:

V^{2}_{n-1} = \frac{(-1)^{n}}{2^{n-1} (n-1!)^{2}} \det (\hat{\Delta})

.

이 공식에서

\det (\hat{\Delta})

는 케일리-멩거 행렬식이다. 이 부피가 양수라는 것은 부피 행렬의 행렬식이 양수라는 것과 동일하다.

10. 2. 정리 (d가 주어지지 않은 경우)

K^영어를 양의 정수, D^영어를 양의 요소를 갖는 대칭적 중공 행렬(symmetric hollow matrix)이라고 하자. 이때 이다. D^영어가 인 유클리드 거리 행렬일 필요충분조건은

\{x_i\}_{i=1}^n \subseteq \mathbb{R}^K

와

\{i_1,...,i_{K+1}\} \subseteq I_n

가 존재하여 다음을 만족시키는 것이다.^[13]

:

\begin{cases}x_i = 0 \\x_{i_j} (j -1) \ne 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}

여기서

\{x_i\}_{i=1}^n

은 D^영어를 실현하며,

x_h(l)

은

h^{th}

벡터의

l^{th}

성분을 나타낸다.^[13]

참조

_[1] 서적 Handbook of Geometric Constraint Systems Principles CRC Press
_[2] 웹사이트 Distance Geometry http://ufo2.cise.ufl[...]
_[3] 문서 Six Mathematical Gems from the History of Distance Geometry https://arxiv.org/pd[...]
_[4] 서적 An Introduction to the Geometry of {{mvar|n}} Dimensions Dover Publications
_[5] 웹사이트 Cayley-Menger Determinant http://mathworld.wol[...]
_[6] 웹사이트 Simplex Encyclopedia of Mathematics https://www.encyclop[...]
_[7] 웹사이트 Simplex Volumes and the Cayley–Menger Determinant https://www.mathpage[...] 2019-06-08
_[8] 서적 A History of Greek Mathematics (Vol II) Oxford University Press
_[9] 간행물 Déterminants sphérique et hyperbolique de Cayley–Menger https://archimede.ma[...]
_[10] 서적 100 Great Problems of Elementary Mathematics https://archive.org/[...] Dover Publications
_[11] 웹사이트 Distance Geometry Wiki Page http://ufo2.cise.ufl[...]
_[12] 강연 "Lecture 1 through 6"
_[13] 웹사이트 Realizing Euclidean Distance Matrices by Sphere Intersection https://www.scienced[...]
_[14] 저널 The Cayley-Menger determinant is irreducible for n ≥ 3 2005-01
_[15] 저널 Irreducibility of the Cayley–Menger determinant and of a class of related polynomials 2018-06

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com