결정 인자에 대한 라이프니즈 공식

대수학에서는 고트프리트 라이프니즈를 기리기 위해 명명된 라이프니즈 공식은 행렬 원소의 순열 측면에서 사각 행렬의 결정 인자를 표현한다.${\displaystyle A}$이(가) $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times$ n$}$ 행렬인$$$$ 경우 여기서 ${\displaystyle i_{}}$ j ${\$$displaystyle a_$${ij}}$은(는) $A{\displaystyle }$ ${\displaystystyle A}$의 $i{\displaystyle }$ ${\displaystyle j}$ $-th$ 열에서 입력된 공식은 다음과$$ 같다$.$

${\displaystyle \det(A)=\sum _{\tau \in S_{n}}\operatorname {sgn}(\tau )\prod _{i=1}^{n}a_{i,\,\tau (i)}=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}a_{\sigma (i),\,i}}$

여기서 ${\displaystyle \mathrm{sgn}}$ ${\displaystyle \operatorname {sgn} }$은(는) 순열 그룹 $S{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$에서 순열의 부호 함수로, 짝수 순열 및 홀수 순열에 대해 각각$$${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle +1}$과$-1을 반환한다.$

이 공식에 사용되는 또 다른 일반적인 표기법은 레비-시비타 기호의 용어로, 아인슈타인 합계 표기법을 사용하는데, 여기서 이 표기법은 다음과 같다.

${\displaystyle \det(A)=\epsilon _{i_{1}\cdots i_{n}}{a}_{1}{1}}\cdots {a}_{ni_{n},}$

물리학자들에게는 더 친숙할 수 있다.

정의에서 라이프니즈 공식을 직접 평가하려면 일반적으로 $\Omega {\displaystyle \mathrm{}(n}$! ${\displaystyle \cdot n}$) ${\displaystyle \Oomega(n!\cdot n)}$ 연산$$, 즉 $n{\displaystyle !}$ ${\displaystyle$ $n$$!}$이(가$)$ 순서의 $$이기 때문에 $무증상적$으로 n {\$displaystystyle n}$ perutio$$} 연산 수가 필요하다.ns. 이것은 비교적 $작은{\displaystyle }$ n ${\displaystyle n}$에도 비실용적으로 어렵다$.$ 대신, 결정 요소는 LU $분해{\displaystyle }$ A${\displaystyle }$= ${\displaystyle L}$ ${\displaystyle U}$ ${\displaystyle$A$=LU}($일반적으로 가우스 제거 또는 유사한 방법을 통해)을 형성하여 $O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaysty$ O$($$n^{3})$ 연산에서$$ 평가할 수 있다.$$ 이 ${\displaystyle \mathrm{경우}}$ A${\displaystyle }$= ${\displaystyle de}$.${\displaystyle T}$ ${\displaystyle L}$ ${\displaystyle \cdot }$ ${\displaystyle det}$ ${\displaystyle U}$ ${\displaystyle \det$ A$=\det L\cdot \det U}$ 및$$ 삼각 행렬 $L{\displaystyle }$ ${\displaystyle L}$ $및$ U ${\displaystyle U}$의 결정 요인은 단순히 대각선 입력의 제품일 뿐이다$$.(단, 수치 선형대수의 실제 적용에서는 결정요소의 명시적 연산이 거의 필요하지 않다.)예를 들어 Trefethen & Bau(1997)를 참조하십시오.또한 Matrix 곱셈으로 문제를 줄임으로써 $O{\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n$^{$3})$ 미만의 연산에서$$ 결정인자를 평가할 수 있지만 대부분의 그러한 알고리즘은 실용적이지 않다.

형식적 진술 및 증거

정리.${\displaystyle 기능\mathbb{}}$F : ${\displaystyle M_{}}$n (${\displaystyle K\mathbb{}}$) → K ${\$$M_{n}(\mathb {K} )\우측arrow \mathb${K$$$}}$은(는) 다중 선 w.r.t. 열을 $교대$하고 F${\displaystyle (I}$) = ${\displaystyle 1}${\$displaystyle$ F$(I)=1$}인 경우$.$

증명하다.

고유성:$F{\displaystyle }$ ${\displaystyle F}$을(를) 그런 함수가 되게$$ $하고{\displaystyle }$,${\displaystyle }$A${\displaystyle }$= (${\displaystyle {}_{}^{}{}_{}^{}}$j )${\displaystyle i_{}^{}}$ =${\displaystyle 1_{}^{}}$,${\displaystyle n_{}^{}}$ =${\displaystyle 1_{}^{}}$, n ${\$은(를${\displaystyle )}$ n$$ ×$$ {\$displaystytimes$n} $행렬$로 한다$$$.$$A{\displaystyle }$ ${\displaystyle A^{$$j}$ A의$$ j ${\displaystyle j}$ -th$$ 열에 전화하십시오$.$${\displaystyle A^{}}$ ${\displaystyle j^{}}$=${\displaystyle }$( ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}{}_{}}$) ${\displaystyle i_{}}$= ${\displaystyle 1_{}}$,${\displaystyle {\dots ,}_{}}$ ${\displaystyle n_{}}${\$displaystyle$A^{$j}=(a_{i}^{j})_{i=1,\dots,n$ 이렇게 $해서{\displaystyle }$ A${\displaystyle }$=${\displaystyle }$( ${\displaystyle A{}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$,${\displaystyle }$… , ${\displaystyle A^{}}$) $.\displaysty$ A$=\좌($$A^{1}, 도트,A^{n}\$n}\$rigs$.$}$

또한 E ${\displaystyle k^{}}$ ${\$는 ID 행렬의 $k{\displaystyle }$ ${\displaystyle k}$ -th번째$$ 열 벡터를 나타내도록$$ 한다.

이제 각 A ${\displaystyle j^{}}$ ${\$를$$E ${\displaystyle k^{}}$ ${\$ E$^{k$ 다시 말해 A $j{\displaystyle {}^{}}$ {\displaystyle E^{k}}의 관점에서 쓴다.

${\displaystyle a^{}}$ j${\displaystyle {}^{}}$= ${\displaystyle \underset{k}{\overset{}{}}}$= ${\displaystyle {1n}_{}^{}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}^{}}$ ${\displaystyle {}_{}^{}}$ E ${\displaystyle k^{}}$ ${\$

$F{\displaystyle }$ ${\displaystyle F}$이(가) 다중 선이기 때문에

${\displaystyle {\begin{aligned}F(A)&=F\left(\sum _{k_{1}=1}^{n}a_{k_{1}}^{1}E^{k_{1}},\dots ,\sum _{k_{n}=1}^{n}a_{k_{n}}^{n}E^{k_{n}}\right)=\sum _{k_{1},\dots ,k_{n}=1}^{n}\left(\prod _{i=1}^{n}a_{k_{i}}^{i}\right)F\왼쪽(E^{k_{1},\dots, E^{k_{n}}\오른쪽).\end{정렬}}}$

교대로부터 지수를 반복하는 모든 항은 0이다.따라서 합계는 반복되지 않는 지수(예: 순열):

${\displaystyle F(A)=\sum \in S_{n}}\왼쪽(\prod _{i=1}^{n}a_{\sigma(i)^{i}\오른쪽)F(E^{\sigma(1)},\dots,E^{\sigma (n)})}$

F가 교대하기 때문에 E ${\displaystyle$ E$} 열$은 $ID$가 될 때까지 교환할 수 있다$$.${\displaystyle \mathrm{부호}}$ 함수 sgn${\displaystyle \sigma }$ ( ${\displaystyle )}$) {\$displaystyle \operatorname$ {sgn$}(\sigma )}$은 필요한 스왑 수를 카운트하고 그에 따른 부호 변경을 설명하기 위해 정의된다$$.마침내 다음과 같은 결과를 얻는다.

${\displaystyle {\begin{aligned}F(A)&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\left(\prod _{i=1}^{n}a_{\sigma (i)}^{i}\right)F(I)\\&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}a_{\sigma (i)}^{i}\end{aligned}}}$

as $F{\displaystyle }$( ${\displaystyle I}$) ${\displaystyle F(I)}$은(는) $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$과(와) 같아야 한다$.$

따라서 라이프니즈 공식에 의해 정의된 기능 외에 그 어떤 $기능$도 F${\displaystyle }$(${\displaystyle I}$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle F\left(I\right)=1}$와 다중선 교대함수가 될 수 없다$.$

존재:우리는 이제 라이프니즈 공식에 의해 정의된 함수인 F가 이 세 가지 성질을 가지고 있다는 것을 보여준다.

다중 선:

${\displaystyle{\begin{정렬}(A^{1}},cA^{j,\dots ,\dots)&, =\sum _{\sigma \in S_{n}}\operatorname{sgn}(\sigma)ca_{\sigma(j)}^{j}\prod _{ji=1,i\neq}^{n}a_{\sigma(나는)}^{나는}\\&, =c\sum _{\sigma \in S_{n}}\operatorname{sgn}(\sigma)a_{\sigma(j)}^{j}\prod _{ji=1,i\neq}^{n}a_{\sigma(나는)}^{나는}\\&, =cF(A^{1},\dots,A^{j},\dots)\\\\F(A^{1},\.보시는 ,b+A^{j},\dots)&=\sum _{\sigma \in S_{n}}\operatorname{sgn}(\sigma)\left(b_{\sigma(j)}+a_{\sigma(j)}^{j}\right)\prod _{ji=1,i\neq}^{n}a_{\sigma(나는)}^{나는}\\&, =\sum _{\sigma \in S_{n}}\operatorname{sgn}(\sigma)\left(\left(b_{\sigma(j)}\prod _{ji=1,i\neq}^{n}a_{\sigma(나는)}^{나는}\right)+\left(a_{\sigma(j)}^{j}\prod _{ji=1,i\neq}^{n}a_{\sigma(.i)}^{나는}\오른쪽)\오른쪽)\\&=\left(\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )b_{\sigma (j)}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\right)+\left(\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}a_{\sigma (i)}^{i}\right)\\&=F(A^{1},\dots,b,\dots )+F(A^{1},\dots,A^{j},\dots}\\\ended{aigned}}}}}}$

교대:

${\displaystyle {\begin{aligned}F(\dots ,A^{j_{1}},\dots ,A^{j_{2}},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}\\\end{aligned}}}$

$\sigma {\displaystyle }$S ${\displaystyle n_{}}$ ${\$의 경우, ${\$$displaystyle \sigma$ '}을$($를) ${\displaystyle {j\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$} $및$ ${\displaystyle {j\mathrm{}}_{}}$ 2$${\$displaystyj_{2$} 인덱스가$$ 전환된$$ {$${\displaystyplaystygma styptionstygma}에 해당하는 튜플랫폼 \s}이 되도록$$ 한다$$.

${\displaystyle{\begin{정렬}(A)&,=\sum _{\sigma \in S_{n},\sigma(j_{1})<, \sigma(j_{2})}\left-LSB- \operatorname{sgn}(\sigma)\left(\prod_{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma(나는)}^{나는}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}+\operatorname{sgn}(\sigma의)\left(\prod_{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma'(나는)}^{나는}.\right)a_{\chma '(j_{1}}^{j_{1}:{1}a_{\\\probma '(j_{2})^{j_{2}}\오른쪽]\\&,=\sum _{\sigma \in S_{n},\sigma(j_{1})<, \sigma(j_{2})}\left-LSB- \operatorname{sgn}(\sigma)\left(\prod_{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma(나는)}^{나는}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}-\operatorname{sgn}(\sigma)\left(\prod_{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma(나는)}^{나는}\right)a_{\sigma(j_{2})}^{j_{1}}a_{.\sigma(j_{1}}^{j_{2}}\오른쪽]\\&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)\underbrace {\left(a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}-a_{\sigma (j_{1})}^{j_{2}}a_{\sigma (j_{2})}^{j_{_{1}}}\right)} _{=0{\text{, if }}j_{1}=j_{2}}\\\\\end{aligned}}}$

Thus if ${\displaystyle A^{j_{1}}=A^{j_{2}}}$ then ${\displaystyle F(\dots ,A^{j_{1}},\dots ,A^{j_{2}},\dots )=0}$.

마지막으로, $F{\displaystyle }$(${\displaystyle I}$ )${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle F(I)=1$

${\displaystyle {\begin}F(I)&=\sum _{n}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}I_{\sigma (i)}^{i}=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}\operatorname {\delta } _{i,\sigma (i)}\\&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\operatorname {\delta } _{\sigma ,\operatorname {id} _{\{1\ldots n\}}}=\operatorname {sgn}(\operatorname {id} _{\{1\ldots n\}})=1\end{aligned}}}$

따라서 $F{\displaystyle (I}$)${\displaystyle }$= 1 ${\displaystyle F(I)=1}$과(와) 교대하는 유일한 다중선 함수는 라이프니즈 공식에 의해 정의된 함수로 제한되며$$, 사실 이 세 가지 속성도 있다.따라서 결정 인자는 이 세 가지 속성을 가진$$ 유일한 함수 ${\displaystyle det}$: ${\displaystyle M_{}}$ ${\displaystyle n\mathbb{}{}_{}}$( K${\displaystyle }$)${\displaystyle }$→ ${\displaystyle K\mathbb{}}$ ${\$로 정의할 수 있다.

참고 항목

• 매트릭스
• 라플라스 확장
• 크레이머의 법칙

참조

• "Determinant", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Trefethen, Lloyd N.; Bau, David (June 1, 1997). Numerical Linear Algebra. SIAM. ISBN 978-0898713619.