도그슨 응축

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2019년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

수학에서 Dodgson 응축 또는 계약자의 방법은 제곱 행렬의 결정 인자를 계산하는 방법이다. 발명가인 찰스 러트위지 도드슨(더 잘 알려진 그의 가명으로 유명한 작가 루이스 캐롤)의 이름을 따서 지은 것이다. n × n 매트릭스의 경우 방법은 (n - 1) × (n - 1) 매트릭스, a (n - 2) × (n - 2) × (n - 2) × (n - 2) 매트릭스 등을 구성하여 하나의 항목인 원래 매트릭스의 결정 인자를 갖는 1 × 1 매트릭스로 마무리하는 것이다.

일반법

이 알고리즘은 다음 4단계로 설명할 수 있다.

1. A를 주어진 n × n 행렬이 되게 하라. A의 내부에 0이 발생하지 않도록 배열한다. 내부의 명시적인 정의는 $모두$_i,j a ,${\displaystyle j}$ ${\displaystyle \ne }$ ${\displaystyle 1}$,${\displaystyle n}$ ${\displaystyle$ i$,j\neq$1,$n}$일 것이다$.$ 한 행의 배수를 다른 행에 추가하는 등 결정요인의 값을 변경하지 않고 정상적으로 수행할 수 있는 모든 연산을 사용하여 이를 수행할 수 있다.
2. A의 매 2 × 2 하위 거주자의 결정 인자로 구성된 (n - 1) × (n - 1) 매트릭스 B를 생성한다. Explicitly, we write ${\displaystyle b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1}\end{vmatrix}}.$$}$
3. 이 (n - 1) × (n - 1) 행렬을 사용하여 2단계를 수행하여 (n - 2) × (n - 2) 행렬 C를 얻으십시오. Divide each term in C by the corresponding term in the interior of A so ${\displaystyle c_{i,j}={\begin{vmatrix}b_{i,j}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j+1}\end{vmatrix}}/a_{i+1,j+1}}$.
4. A = B, B = C. 1 x 1 행렬이 발견될 때까지 필요에 따라 3단계를 반복하십시오. 유일한 입력은 결정 요인이다.

예

0 제외

찾기를 바란다.

${\displaystyle {\bmatrix}-2&-1&-1&-4\\-1&-1&-1&-6\\-1&1&2&4\2&1&3&-8end{vmatrix}}.}$

내부 요소가 모두 0이 아니므로 매트릭스를 다시 정렬할 필요가 없다.

우리는 그것의 2 × 2 하위 행렬의 행렬을 만든다.

${\displaystyle{\begin{bmatrix}{\begin{vmatrix}-2&, -1\\-1&, -2\end{vmatrix}}&{\begin{vmatrix}-1&, -1\\-2&, -1\end{vmatrix}}&{\begin{vmatrix}-1&, -4\\-1&, -6\end{vmatrix}}\\\\{\begin{vmatrix}-1&, -2\\-1&, -1\end{vmatrix}}&{\begin{vmatrix}-2&, -1\\-1&, 2\end{vmatrix}}&{\begin{vmatrix}-1&, -6\\2&, 4\end{vmatrix}}\\\\{\begin{vmatrix}-1&, -1\\2&, 1\end{vmatrix}}&{\begin{vmatrix}-1&2\\\1&-3\end{vmatrix}&#{vmatrix}2&4\\\3&-8\end{vmatrix}\end{bmatrix}}={\nd{bmatrix}3&-1&2\&#1&8\1&#1&#4}end{bmatrix}}}.}$

그리고 나서 우리는 또 다른 결정요인의 행렬을 찾아낸다.

${\displaystyle {\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}\\\\{\begin{vmatrix}-1&-5\\1&1\end{vmatrix}}&{\begin{vmatrix}-5&8\\1&-4\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}-16&2\\4&12\end{bmatrix}}.}$

그런 다음 우리는 각각의 원소를 원래의 매트릭스의 해당 원소로 나누어야 한다. 원래 매트릭스의 내부는[- - - 1 ${\$이(가) 있으므로, 분할 후[ - 4 ${\begin{bmatrix}8&#4&6\nd{bmatrix$ 이 과정은 1 × 1 행렬에 도달하기 위해 반복되어야 한다. $]$$}$ 3 × 3 행렬의 내부로 나누면, -5에 불과하며$,{\displaystyle }$ [${\displaystyle \begin{array}{c}\end{array}}$- ${\displaystyle \begin{array}{c}8\end{array}}$ ${\displaystyle \begin{array}{}]\end{array}}$ $[\$이(가) 주어지며, -8은 실제로 원래의 행렬의 결정인자다.

0 포함

매트릭스를 작성하는 것:

${\displaystyle{\begin{bmatrix}2&, -1&, 2&, 1&, -3\\1&, 2&, 1&, -1&, 2\\1&, -1&, -2&, -1&, -1\\2&, 1&, -1&, -2&, -1\\1&, -2&, -1&, -1&, 2\end{bmatrix}}\to{\begin{bmatrix}5&, -5&, -3&, -1\\-3&, -3&, -3&, 3\\3&, 3&, 3&, -1\\-5&, -3&, -1&, -5\end{bmatrix}}\to{\begin{bmatrix}-15&, 6&/&12\\0&, 0&, 6\\6&, -6&, 8\end{bmatrix}}.}$

여기서 우리는 문제에 부딪친다. 이 과정을 계속하면 결국 0으로 나뉘게 된다. 초기 매트릭스에서 4행 교환을 수행하여 결정 인자를 보존하고 프로세스를 반복할 수 있으며, 대부분의 결정 인자는 다음과 같이 사전 계산된다.

${\displaystyle{\begin{bmatrix}1&, 2&, 1&, -1&, 2\\1&, -1&, -2&, -1&, -1\\2&, 1&, -1&, -2&, -1\\1&, -2&, -1&, -1&, 2\\2&, -1&, 2&, 1&, -3\end{bmatrix}}\to{\begin{bmatrix}-3&, -3&, -3&, 3\\3&, 3&, 3&, -1\\-5&, -3&, -1&, -5\\3&, -5&, 1&, 1\end{bmatrix}}\to{\begin{bmatrix}0&, 0&, 6\\6&, -6&, 8\\-17&, 8&, -4\end{bmatrix}}\to{\begin{bmatrix}0&, 12\\18&, 40\end{bmatrix}}\to{\begin{bmatrix}36\end{bmatrix}}.}$

그래서 우리는 36의 결정요인에 도달한다.

데스나노-자코비 정체성과 응축 알고리즘의 정확성 증명

0에 의한 구분이 없는 경우 응축 방법이 행렬의 결정 인자를 계산한다는 증거는 데스나노트-자코비 아이덴티티(1841) 또는 더 일반적으로 실베스터 결정 인자(1851)로 알려진 아이덴티티에 기초한다.^[1]

Let ${\displaystyle M=(m_{i,j})_{i,j=1}^{k}}$ be a square matrix, and for each ${\displaystyle 1\leq i,j\leq k}$, denote by ${\displaystyle M_{i}^{j}}$ the matrix that results from ${\displaystyle M}$ by deleting the ${\displaystyle i}$-th row and the ${\displaystyle j}$ $[\displaystyle j}$ -th$$ 열. Similarly, for ${\displaystyle 1\leq i,j,p,q\leq k}$, denote by ${\displaystyle M_{i,j}^{p,q}}$ the matrix that results from ${\displaystyle M}$ by deleting the ${\displaystyle i}$-th and ${\displaystyle j}$-th rows and the ${\displaystyle p}$-th and ${\di$$splaystyle q}$ -th$$ 열.

데스나노-야코비 정체성

${\displaystyle \det(M_{1,k}^{1,k}^{1}=\det(M_{1}^{1}^{k})\det(M_{1}^{k}-\det(M_{1}^{k}^{1})\det(M_{k}^}^{1}){1}.}$

Dodgson 응축의 정확성 증명

ID를 다음으로 다시 쓰십시오.

${\displaystyle \det(M)={\frac(M_{1}^{1}^{1})\det(M_{k}^{k}-\det(M_{1}^{k}^{1})}{\det(M_{1,k}^{k}}}}}}}}}}}}}}}.}$

이제 유도에 의해 Dodgson 응축 절차를 $순서$가 n$${\$displaystyle$n}인$$ 정사각형 $행렬{\displaystyle }$ A$${\$displaystyle$ $A$$}$에 적용할$$때 $계산$의 k ${\displa$} -th$$ 단계(여기서 첫 번째 ${\displaystyle \mathrm{단계}}$ k${\displaystyle }$= 1 ${\displa$ 스타일 $k=1})$의 $행렬$이 행렬 A ${\\displa$에 해당한다는$$ 점에 유의하십시오.$ystyle A}$ 자체$$)는 $A{\displaystyle }$ ${\displaystyle A}$의 순서 $k{\displaystyle }$ ${\displaystyle k}$의 연결된 모든 미성년자로 구성되며$,$ 여기서 연결된 부차는 $연결$된 k ${\displaystyle \times }$ ${\displaystyle k}$ ${\displaystyle k$$}$의 인접 항목인 A ${\displaystystyle A$$}$의 결정 요인이다$.$ 특히 마지막 $단계$에서는 ${\displaystyle k}$= n ${\displaystystystystyk=n}$$$, $순서$가 n$${\$displaystyle$n$\}$인 고유한 연결 부분, 즉 $A{\displaystyle }$ ${\displaystyle A}$의 결정 인자와 동일한 단일 요소를 포함하는 행렬을 얻는다$.$

데스나노-야코비 정체성의 증거

우리는 브레수드의 책에 나오는 치료법을 따른다. 다른 결합 증거를 보려면 제일버거의 논문을 참조하라. Denote ${\displaystyle a_{i,j}=(-1)^{i+j}\det(M_{i}^{j})}$ (up to sign, the ${\displaystyle (i,j)}$-th minor of ${\displaystyle M}$), and define a ${\displaystyle k\times k}$ matrix ${\displaystyle M'}$ by

${\displaystyle M'={\begin{pmatrix}a_{1,1}&, 0&, 0&, 0&, \ldots, 0& &, a_{k,1}\\a_{1,2}&, 1&, 0&, 0&, \ldots &, 0&, a_{k,2}\\a_{1,3}&, 0&, 1&, 0&, \ldots &, 0&, a_{k,3}\\a_{140}&, 0&, 0&, 1&, \ldots, 0&, a_{k,4}\\\vdots &, \vdots &, \vdots &, \vdots &,&\vdots, \vdots \\a_{1,k-1}& & &amp을 말한다.0&, 0&, 0&, \ldots &, 1&, a_{k,k-1}\\a_{1,k}&, 0&, 0&, 0&, \ldots &, 0&, a_{k,k}\end{pmatrix}}.}$

($M{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 첫 번째 및 마지막 열은 A ${\displaystyle A}$의 $$애드주게이트 행렬의 열과 동일하다는 점에$$ 유의하십시오. 이제 ID는 두 가지 방법으로$$ ${\displaystyle det(M}$ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ $){\displaystyle \det(MM')$을 계산하여 얻는다. 먼저 매트릭스 제품 ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$애드주게이트 매트릭스의 단순한 속성을 사용하거나 또는 행이나 열의 관점에서 매트릭스 결정인자의 확장에 대한 공식을 사용함)을 직접 계산하여 에 도달할 수 있다.

${\displaystyle MM'={\begin{pmatrix}(M)&, m_{1,2}&, m_{1,3}&, \ldots &, m_{1,k-1}&, 0\\0&, m_{2,2}&, m_{하루에 2,3}&, \ldots &, m_{2,k-1}&, 0\\0&, m_{3,2}&, m_{3,3}&, \ldots &, m_{3,k-1}&, 0\\\vdots, \vdots, \vdots & & &,&\vdots &, \vdots &, \vdots \\0&, m_{k-1,2}&, m_{k-1,3}&, \ldots &, m_{k-1,k-1}&.앰프, 0\\0&, m_{k,2}&, m_{k,3}&, \ldots &, m_{k,k-1}&, \det(M)\end{pmatrix}}}$

where we use ${\displaystyle m_{i,j}}$ to denote the ${\displaystyle (i,j)}$-th entry of ${\displaystyle M}$. The determinant of this matrix is ${\displaystyle \det(M)^{2}\cdot \det(M_{1,k}^{1,k})}$.
둘째$,$ 이것은 결정인자 ${\displaystyle det}$(${\displaystyle M}$) ${\displaystyle \cdot }$ ${\displaystyle det}$(${\displaystyle {}^{}}$ )${\displaystyle {}^{})}$ det (M ) $\displaystyle \det (M)\cdot \det (M')$의 산물과 동일하지만 분명히
${\displaystyle \det(M')=a_{1,1}a_{k,k}-a_{k,1}a_{k,1}a_{k}=\det(M_{1}^{1}^{1})-\det(M_{k}^{k}^{1}),\det(M_{k}^{1}{1}),}}}}}}}}}}}}}{1},},},},},},},},},},},},},},},},},},},$
따라서 ID는 det${\displaystyle (M}$ M${\displaystyle {}^{}}$ ) ${\displaystyle \det(MM')}$에 대해 얻은 두 개의 표현식을 동일시하고$$ ${\displaystyle det(M}$ )$${\$displaystyle \det(M)}($${\displaystyle {k\mathrm{}}^{}}$ 2$${\$displaysty k^{2$}}개의$$ 미확정 v}에 있는 다항식 링 위에 다항식 ID로 생각하면 허용된다.아리블${\displaystyle }$(${\displaystyle m_{}}$ ${\displaystyle i_{}}$, j${\displaystyle {}_{}{}_{}^{}}$) ${\displaystyle i_{}^{}}$, ${\displaystyle j_{}^{}}$= ${\displaystyle 1_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$

메모들

참조 및 추가 판독

• 브레수드, 데이비드 M, 증명서 및 확인서: The Story of the 교류 부호 매트릭스 추측, MAA Spectrum, Mathical Associations of America, Washington, D.C., 1999.
• 브레수드, 데이비드 M. 그리고 프로프, 제임스, 교대 부호 행렬 추측이 어떻게 해결되었는가, 미국 수학 학회의 통지서, 46 (1999), 637-646.
• Dodgson, C. L. (1866–1867). "Condensation of Determinants, Being a New and Brief Method for Computing their Arithmetical Values" (PDF). Proceedings of the Royal Society of London. 15: 150–155.
• Knuth, Donald, Overlaping Paffians, Electronic Journal of Combinatorics, 3 no. 2 (1996년)
• Lotkin, Mark (1959). "Note on the Method of Contractants". The American Mathematical Monthly. 66 (6): 476–479. doi:10.2307/2310629. JSTOR 2310629.
• 밀스, 윌리엄 H, 로빈스, 데이비드 P, 럼지, 하워드 주니어, 맥도날드 추측의 증명, 발명품 수학자 66 (1982), 73-87.
• 밀스, 윌리엄 H, 로빈스, 데이비드 P, 럼지, 하워드, 주니어, 교대 부호 행렬과 하강 평면 칸막이, 시리즈 A, 34 (1983), 340-359.
• 로빈스, 데이비드 P, 1,${\displaystyle 2}$,${\displaystyle }$7, ${\displaystyle 42,}$ ${\displaystyle 429,}$ ${\displaystyle 7436,}$ ${\displaystyle \cdots }$ ${\displaystyle$1$,2,7,42,429,7436,\cdots$ The Mathemical Intelligentencer, 13 (1991), 12-19.
• 제일버거, 도론, 도든, 도든의 결정적 평가규칙은 남녀 양다리 걸치는 일렉트로닉 저널, 콤비네이터ics, 4번 2번(1997)에 의해 증명되었다.

외부 링크

• Weisstein, Eric W. "Dodgson condensation". MathWorld.