방데르몽드 행렬

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

1. 개요

방데르몽드 행렬은 각 행이 첫 번째 항이 1인 등비수열로 구성된 정사각 행렬이다. 이 행렬의 행렬식을 방데르몽드 행렬식이라고 부르며, 그 값은 다항식 형태로 표현된다. 방데르몽드 행렬식은 모든 x_i가 서로 다를 때 0이 아니며, 다항식 보간법, 통계학의 다항식 회귀, 수치 해석, 대칭군의 표현론 등 다양한 분야에 응용된다. 특히, 다항식 보간법 문제에서 선형대수학적 재구성을 가능하게 하며, 역 반데르몽드 행렬을 통해 해를 구할 수 있다. 또한, 중복된 점에서의 도함수 값을 지정하는 에르미트 보간법과 관련된 합류 반데르몽드 행렬도 존재한다.

방데르몽드 행렬

개요

이름	방데르몽드 행렬
다른 이름	방데르몽드 행렬식 방데르몽드 다항식
로마자 표기	Bangdeureumondeu haengnyeol

정의

형태	각 행이 등비수열을 이루는 정사각 행렬
구성 요소	x1, x2, ..., xn (스칼라 값)

성질

행렬식	곱셈 형태로 표현 가능 (자세한 내용은 본문 참조)

활용

응용 분야	곡선 피팅 다항식 보간

관련 항목	선형대수학

2. 정의

각 행이 첫째 항이 1인 등비수열인 정사각 행렬
: $V:=\begin{bmatrix}1 &x_1 &{x_1}^2 &\cdots &{x_1}^{n-1} \\1 &x_2 &{x_2}^2 &\cdots &{x_2}^{n-1} \\\vdots &\vdots &\vdots &\ddots &\vdots \\1 &x_n &{x_n}^2 &\cdots &{x_n}^{n-1}\end{bmatrix}$
를 방데르몽드 행렬(Vandermonde matrix^영어)이라고 하며, 그 행렬식을 반데르몽드 행렬식이라고 한다. 위의 전치 행렬
: $\begin{bmatrix}1 &1 &\cdots &1 \\x_1 &x_2 &\cdots &x_n \\{x_1}^2 &{x_2}^2 &\cdots &{x_n}^2 \\\vdots & \vdots &\ddots &\vdots \\{x_1}^{n-1} &{x_2}^{n-1} &\cdots &{x_n}^{n-1}\end{bmatrix}$
로 정의하는 경우도 있지만, 행렬식은 전치를 해도 바뀌지 않으므로 행렬식으로서는 완전히 동일하다.

3. 공식

정사각 방데르몽드 행렬의 행렬식은 '방데르몽드 다항식' 또는 '방데르몽드 행렬식'이라고 불린다. 그 값은 다음과 같은 다항식이다.
: $\det(V) = \prod_{0 \le i < j \le n} (x_j - x_i)$
이것은 모든 $x_i$ 가 서로 다를 때에만 0이 아니다.

방데르몽드 행렬식은 각 행의 공비의 차적과 같다. 구체적으로, 위의 행렬 $V$ 에 대해 다음이 성립한다.
: $\det V= \textstyle\prod\limits_{1 \leq i$
$n = 2, 3$ 인 경우를 풀어 쓰면 다음과 같다.
: $\begin{vmatrix}1 &x_1 \\1 &x_2\end{vmatrix} = x_2-x_1,$
: $\begin{vmatrix}1 &x_1 &{x_1}^2 \\1 &x_2 &{x_2}^2 \\1 &x_3 &{x_3}^2\end{vmatrix} = (x_3-x_1)(x_3-x_2)(x_2-x_1)$
공식에서 $x_1, \dots, x_n$ 가 모두 다를 때, 그리고 그 때에만 방데르몽드 행렬식은 0이 됨을 바로 알 수 있다.

3.1. 공식의 증명

라이프니츠 공식에 따르면, $\det(V)$ 는 정수 계수를 갖는 $x_i$ 에 관한 다항식이다. $(i-1)$ 번째 열의 모든 항목은 총 차수가 $i$ 이다. 따라서, 다시 라이프니츠 공식에 의해, 행렬식의 모든 항은 총 차수가
: $0 + 1 + 2 + \cdots + n = \frac{n(n+1)}2;$
이다. (즉, 행렬식은 이 차수의 동차 다항식이다).

만약, $i \neq j$ 에 대해, $x_i$ 를 $x_j$ 로 대체하면, 두 개의 동일한 행을 가진 행렬을 얻게 되며, 따라서 행렬식은 0이 된다. 따라서, 행렬식을 $x_i,$ 에 관한 일변수 다항식으로 고려하면, 인수 정리는 $x_j-x_i$ 가 $\det(V)$ 의 약수임을 의미한다. 따라서 모든 $i$ 와 $j$ 에 대해, $x_j-x_i$ 는 $\det(V)$ 의 약수이다.

$\det(V)$ 는 $i 인 모든 x_i-x_j 의 곱으로 나누어진다. 즉,$
: $\det(V)=Q\prod_{0\le i$
여기서 $Q$ 는 다항식이다. 모든 $x_j-x_i$ 의 곱과 $\det(V)$ 는 동일한 차수 $n(n + 1)/2$ 를 가지므로, 다항식 $Q$ 는 실제로 상수이다. 이 상수는 1인데, 그 이유는 $V$ 의 대각선 항목의 곱이 $x_1 x_2^2\cdots x_n^n$ 이고, 이는 또한 $\textstyle \prod_{0\le i 의 모든 인수의 첫 번째 항을 취하여 얻는 단항식 이기 때문이다. 이것은 Q=1, 임을 증명하고, 증명을 마무리한다.$
: $\det(V)=\prod_{0\le i$

수학적 귀납법으로 증명할 수도 있고, 행렬식의 성질을 이용할 수도 있다. 행렬식의 교대성(행을 바꾸면 행렬식은 -1배가 된다)과 인수 정리에 의해, $\det V$ 는 $x_j - x_i$ 들을 인수로 가짐을 알 수 있으므로, 나머지는 차수와 계수를 비교하면 공식이 성립함을 알 수 있다.

어떤 정방 행렬의 어떤 열(행)의 각 성분에 같은 계수를 곱하고, 다른 어떤 열(행)에 벡터적으로 더하는 조작(행렬의 기본 변형 중 하나)을 해도, 행렬식의 값은 변하지 않는다. 이 성질과 인수 정리, 각 항의 차수와 계수를 비교하는 방법을 통해 증명할 수도 있다.

4. 성질

행렬의 한 열에 다른 열의 스칼라 곱을 더해도 행렬식은 변하지 않는다.

이 성질을 이용해 방데르몽드 행렬의 행렬식을 구할 수 있다. 첫 번째 열을 제외한 각 열에서 $x_0$ 을 곱한 이전 열을 빼면 행렬식이 변경되지 않는다. 이 연산을 마지막 열부터 시작해 아직 변경되지 않은 열을 빼는 방식으로 진행하면 다음 행렬을 얻는다.

: $V = \begin{bmatrix}1&0&0&0&\cdots&0\\1&x_1-x_0&x_1(x_1-x_0)&x_1^2(x_1-x_0)&\cdots&x_1^{n-1}(x_1-x_0)\\1&x_2-x_0&x_2(x_2-x_0)&x_2^2(x_2-x_0)&\cdots&x_2^{n-1}(x_2-x_0)\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n-x_0&x_n(x_n-x_0)&x_n^2(x_n-x_0)&\cdots&x_n^{n-1}(x_n-x_0)\\\end{bmatrix}$

라플라스 전개를 첫 번째 행에 적용하면 $\det(V)=\det(B)$ 가 되며, 여기서 $B$ 는 다음과 같다.

: $B = \begin{bmatrix}x_1-x_0&x_1(x_1-x_0)&x_1^2(x_1-x_0)&\cdots&x_1^{n-1}(x_1-x_0)\\x_2-x_0&x_2(x_2-x_0)&x_2^2(x_2-x_0)&\cdots&x_2^{n-1}(x_2-x_0)\\\vdots&\vdots&\vdots&\ddots&\vdots\\x_n-x_0&x_n(x_n-x_0)&x_n^2(x_n-x_0)&\cdots&x_n^{n-1}(x_n-x_0)\\\end{bmatrix}$

$B$ 의 $i$ 번째 행의 모든 항목은 $x_{i+1}-x_0$ 의 인수를 가지므로, 이 인수를 빼내면 다음과 같이 된다.

: $\det(V)=(x_1-x_0)(x_2-x_0)\cdots(x_n-x_0)\begin{vmatrix}1&x_1&x_1^2&\cdots&x_1^{n-1}\\1&x_2&x_2^2&\cdots&x_2^{n-1}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&\cdots&x_n^{n-1}\\\end{vmatrix}=\prod_{1$

여기서 $V'$ 는 $x_1,\ldots, x_n$ 에서의 방데르몽드 행렬이다. 이 작은 방데르몽드 행렬에 이 과정을 반복하면, $i 인 모든 x_j-x_i 의 곱으로 표현되는 방데르몽드 행렬식을 얻을 수 있다.$

방데르몽드 행렬의 계수는 다음과 같다.
* $m \le n$ 인 직사각형 방데르몽드 행렬에서 모든 $x_i$ 가 서로 다르면 계수는 $m$ 이다.
* $m \ge n$ 인 직사각형 방데르몽드 행렬에서 $n$ 개의 $x_i$ 가 서로 다르면 계수는 $n$ 이다.
* 정사각 방데르몽드 행렬은 모든 $x_i$ 가 서로 다를 경우 가역적이다.

4.1. 행렬식

정사각 방데르몽드 행렬의 행렬식은 방데르몽드 다항식 또는 방데르몽드 행렬식이라고 불린다. 그 값은 다음과 같은 다항식이다.
: $\det(V) = \prod_{0 \le i < j \le n} (x_j - x_i)$
이것은 모든 $x_i$ 가 서로 다를 때에만 0이 아니다.

방데르몽드 행렬식은 $x_i$ 에서 교대 형식이며, 이는 두 개의 $x_i$ 를 교환하면 부호가 바뀐다는 것을 의미한다.

행렬식 공식은 다음 세 가지 방법으로 증명할 수 있다.
# 다항식의 성질, 특히 다변수 다항식의 유일 인수 분해 영역 속성을 사용한다. 개념적으로는 간단하지만 추상대수학의 비-기본적인 개념을 포함한다.
# 벡터 공간에서 기저 변환과 선형 사상의 행렬식이라는 선형대수학 개념에 기초한다. 이 과정에서 방데르몽드 행렬의 LU 분해를 계산한다.
# 더 초등적이지만 더 복잡하며, 기본 행과 열 연산만 사용한다.

첫 번째 증명 (다항식 성질 이용):

라이프니츠 공식에 따르면, $\det(V)$ 는 정수 계수를 갖는 $x_i$ 에 관한 다항식이다. $(i-1)$ 번째 열의 모든 항목은 총 차수가 $i$ 이다. 따라서, 다시 라이프니츠 공식에 의해, 행렬식의 모든 항은 총 차수가
: $0 + 1 + 2 + \cdots + n = \frac{n(n+1)}2;$
이다. (즉, 행렬식은 이 차수의 동차 다항식이다).

만약, $i \neq j$ 에 대해, $x_i$ 를 $x_j$ 로 대체하면, 두 개의 동일한 행을 가진 행렬을 얻게 되며, 따라서 행렬식은 0이 된다. 따라서, 행렬식을 $x_i,$ 에 관한 일변수 다항식으로 고려하면, 인수 정리는 $x_j-x_i$ 가 $\det(V)$ 의 약수임을 의미한다. 따라서 모든 $i$ 와 $j$ 에 대해, $x_j-x_i$ 는 $\det(V)$ 의 약수이다.

$\det(V)$ 는 $i 인 모든 x_i-x_j 의 곱으로 나누어지며 다음과 같이 표현된다.$
: $\det(V)=Q\prod_{0\le i$
여기서 $Q$ 는 다항식이다. 모든 $x_j-x_i$ 의 곱과 $\det(V)$ 는 동일한 차수 $n(n + 1)/2$ 를 가지므로, 다항식 $Q$ 는 실제로 상수이다. 이 상수는 1인데, 그 이유는 $V$ 의 대각선 항목의 곱이 $x_1 x_2^2\cdots x_n^n$ 이고, 이는 또한 $\textstyle \prod_{0\le i 의 모든 인수의 첫 번째 항을 취하여 얻는 단항식 이기 때문이다. 이것은 Q=1, 임을 증명하고, 증명을 마무리한다.$
: $\det(V)=\prod_{0\le i$

각 행이 첫째항이 1인 등비수열인 정사각 행렬
: $V:=\begin{bmatrix}1 &x_1 &{x_1}^2 &\cdots &{x_1}^{n-1} \\1 &x_2 &{x_2}^2 &\cdots &{x_2}^{n-1} \\\vdots &\vdots &\vdots &\ddots &\vdots \\1 &x_n &{x_n}^2 &\cdots &{x_n}^{n-1}\end{bmatrix}$
의 행렬식을 반데르몽드 행렬식이라고 한다.

반데르몽드 행렬식은 각 행의 공비의 차적과 같다. 구체적으로, 위의 행렬 $V$ 에 대해
: $\det V= \textstyle\prod\limits_{1 \leq i$
이 성립한다.

$n = 2, 3$ 의 경우를 풀어 쓰면,
: $\begin{vmatrix}1 &x_1 \\1 &x_2\end{vmatrix} = x_2-x_1,$
: $\begin{vmatrix}1 &x_1 &{x_1}^2 \\1 &x_2 &{x_2}^2 \\1 &x_3 &{x_3}^2\end{vmatrix} = (x_3-x_1)(x_3-x_2)(x_2-x_1)$
이다. 공식에서 바로 알 수 있는 것은, $x_1, \dots, x_n$ 가 모두 다를 때, 그리고 그 때에만 반데르몽드 행렬식은 0이 아니다.

4.2. 계수

* 직사각형 반데르몽드 행렬은 이고, 모든 가 서로 다를 경우 계수 을 가진다.
* 직사각형 반데르몽드 행렬은 이고, 개의 가 서로 다를 경우 계수 을 가진다.
* 정사각 반데르몽드 행렬은 가 서로 다를 경우 가역적이다.

5. 응용

방데르몽드 행렬은 다항식 보간법, 통계학, 수치 해석, 대칭군의 표현론, 유한체, 이산 푸리에 변환, 양자 홀 효과, 다면체 기하학 등 다양한 분야에서 응용된다.

* 다항식 보간법: 주어진 점들을 지나는 다항식을 찾는 문제에 사용되며, 방데르몽드 행렬을 이용해 선형대수학 문제로 변환하여 해를 구할 수 있다.
* 통계학: 다항식 회귀의 설계 행렬로 사용된다.
* 수치 해석: 선형 방정식을 푸는 효율적인 알고리즘 개발에 활용된다.
* 대칭군의 표현론: 대칭군의 표현론 연구에 사용된다.
* 유한체: BCH 코드 및 리드-솔로몬 오류 정정 코드와 같은 오류 정정 코드 이론에서 중요한 역할을 한다.
* 이산 푸리에 변환: DFT 행렬을 정의하는 데 사용되며, 고속 푸리에 변환 알고리즘의 기반이 된다.
* 양자 홀 효과: 라플린 파동 함수와 슬레이터 행렬식 간의 관계를 설명하는 데 사용된다.
* 다면체 기하학: 사이클릭 다면체의 부피 계산에 활용된다.

에르미트 보간에서처럼, 방데르몽드 행렬은 서로 다른 점 $x_1, \cdots, x_n$ 에서 $p(x_1), \cdots, p(x_n)$ 의 값을 기반으로 $n - 1$ 차 다항식 $p(x)$ 의 계수를 찾는 보간법 문제를 설명한다. 만약 $x_i$ 가 서로 다르면 문제는 고유한 해를 가지지만, $x_i$ 가 서로 같으면, 이 문제는 고유한 해를 갖지 않으며(이에 해당하는 반데르몬드 행렬은 특이 행렬이다) 중복되는 점에서의 도함수 값을 지정하면 문제는 고유한 해를 가질 수 있다.

5.1. 다항식 보간법

다항식 보간법 문제는 주어진 데이터 점 $(x_0,y_0),\ldots,(x_m,y_m)$ 에 대해 $p(x_0)=y_0, \ldots,p(x_m)=y_m$ 을 만족하는 다항식 $p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$ 을 찾는 것이다. 이 문제는 다음과 같이 반데르몬드 행렬을 사용하여 선형대수학의 관점에서 재구성할 수 있다.

: $\begin{bmatrix}1 & x_0 & x_0^2 & \dots & x_0^n\\1 & x_1 & x_1^2 & \dots & x_1^n\\1 & x_2 & x_2^2 & \dots & x_2^n\\\vdots & \vdots & \vdots & \ddots &\vdots \\1 & x_m & x_m^2 & \dots & x_m^n\end{bmatrix}\cdot\begin{bmatrix}a_0\\a_1\\\vdots\\a_n\end{bmatrix}=\begin{bmatrix}p(x_0)\\p(x_1)\\\vdots\\p(x_m)\end{bmatrix}.$

만약 $n = m$ 이고 $x_0,\dots,\ x_n$ 이 서로 다르다면, V는 0이 아닌 행렬식을 갖는 정사각 행렬, 즉 가역 행렬이다. 따라서 V와 y가 주어지면, 방정식 $Va = y$ 에서 계수 $a$ 를 구하여 필요한 $p(x)$ 를 찾을 수 있다. 즉, 계수에서 다항식 값으로의 맵은 행렬 V를 갖는 전단사 선형 맵이며, 보간 문제에는 고유한 해가 있다. 이 결과는 유일해 정리라고 하며, 다항식에 대한 중국인의 나머지 정리의 특수한 경우이다.

반데르몬드 행렬식은 수학의 여러 분야에서 나타난다. 가장 고전적인 것은 다항식 결정에 관한 것이다. $x_1, x_2, \cdots, x_n$ 가 모두 다르다면,
: $f(x_1)=y_1,\,f(x_2)=y_2,\cdots,f(x_n)=y_n$
을 만족하는 $n-1$ 차 이하의 다항식 $f(x)$ 는 유일하게 결정된다.

5.2. 통계학

통계학에서 방데르몽드 행렬은 다항식 회귀의 설계 행렬로 사용된다.

5.3. 수치 해석

수치 해석에서, $Va = y$ 방정식을 가우스 소거법으로 풀면 시간 복잡도 O(n³)인 알고리즘이 생성된다. 그러나 반데르몬드 행렬의 구조를 활용하여, 뉴턴 다항식(또는 라그랑주 보간 공식)을 사용하면 O(n²) 시간에 방정식을 풀 수 있다. 이는 또한 $V^{-1}$ 의 UL 인수분해를 제공한다. 결과 알고리즘은 $V$ 가 조건이 나쁜 경우에도 매우 정확한 해를 제공한다.

5.4. 대칭군의 표현론

반데르몬드 행렬식은 대칭군의 표현론에 사용된다.

5.5. 유한체

x_i^영어가 유한체에 속하는 경우, 반데르몬드 행렬식은 무어 행렬식이라고도 하며, BCH 코드 및 리드-솔로몬 오류 정정 코드 이론에서 중요한 속성을 갖는다.

5.6. 이산 푸리에 변환

이산 푸리에 변환(DFT)은 특정 반데르몬드 행렬, 즉 $x_i$ 가 단위근으로 선택되는 DFT 행렬에 의해 정의된다. 고속 푸리에 변환은 이 행렬과 벡터의 곱을 $O(n\log^2n)$ 시간에 계산한다.

5.7. 양자 홀 효과

물리학에서 양자 홀 효과 이론의 라플린 파동 함수는 채움비 1을 가질 때 슬레이터 행렬식과 같다는 것을 보여주기 위해 방데르몽드 행렬식이 사용된다. 분수 양자 홀 효과에서는 채움비가 1과 다를 경우 더 이상 성립하지 않는다.

5.8. 다면체 기하학

반데르몽드 행렬은 다면체 기하학에서 사이클릭 다면체의 임의의 $k$ -면의 정규화된 부피를 제공한다. 구체적으로, $T = \{t_{1}< \cdots < t_{N}\} \subset \mathbb{R}$ 에 해당하는 사이클릭 다면체 $C_d(T) \subset \mathbb{R}^{d}$ 의 $k$ -면 $F = C_{d}(t_{i_{1}}, \dots, t_{i_{k + 1}})$ 의 정규화된 부피는 다음과 같이 계산된다.

$\mathrm{nvol}(F) = \frac{1}{k!}\prod_{1 \leq m < n \leq k + 1}{(t_{i_{n}} - t_{i_{m}})}.$

6. 역 반데르몬드 행렬

라그랑주 보간법을 통해 역행렬의 명시적 공식을 유도할 수 있다. 방데르몽드 행렬의 역행렬은 다음과 같이 나타낼 수 있다.

$V^{-1}=\begin{bmatrix}1 & x_0 & \dots & x_0^n\\\vdots & \vdots & &\vdots \\[.5em]1 & x_n & \dots & x_n^n\end{bmatrix}^{-1}= L =\begin{bmatrix}L_{00} & \!\!\!\!\cdots\!\!\!\! & L_{0n}\\\vdots & & \vdots\\L_{n0} & \!\!\!\!\cdots\!\!\!\! & L_{nn}\end{bmatrix}$

여기서 각 원소 $L_{ij}$ 는 라그랑주 다항식의 계수이다. 라그랑주 다항식은 다음과 같이 정의된다.

$L_j(x)=L_{0j}+L_{1j}x+\cdots+L_{nj}x^{n}= \prod_{0\leq i\leq n \atop i\neq j}\frac{x-x_i}{x_j-x_i}= \frac{f(x)}{(x-x_j)\,f'(x_j)}\,,$

여기서 $f(x)=(x-x_0)\cdots(x-x_n)$ 이다. 이 다항식은 $i\neq j$ 일 때 $L_{j}(x_i)=0$ 을 만족하고, $L_{j}(x_j)=1$ 을 만족한다. 따라서, 행렬 $VL = [L_j(x_i)]_{i,j=0}^n = I$ (항등 행렬)이 된다.