数学 において、ドッジソン縮約法 または縮約法は、 正方行列 の行列式 を計算する方法です。この方法は、1866 年に発見した発明者チャールズ・ラトウィッジ・ドッジソン (ペンネームのルイス・キャロルとしてよく知られている人気作家) にちなんで名付けられました。[ 1 ] n × n 行列の場合、この方法は ( n − 1) × ( n − 1) 行列、( n − 2) × ( n − 2) 行列などを構築し、最終的に 1 × 1 行列を作成します。この行列には、元の行列の行列式という 1 つの要素があります。
一般的な方法 このアルゴリズムは、以下の4つのステップで説明できます。
A を与えられたn × n 行列とする。A の内部にゼロが出現しないように配置する。内部の明示的な定義は、すべての a i,j が次の条件を満たすことである。 私 、 j ≠ 1 、 n {\displaystyle i,j\neq 1,n} A の各 2 × 2 部分行列の行列式からなる( n − 1) × ( n − 1) 行列 B を作成します。具体的には、次のように記述します。 b 私 、 j = | 1 私 、 j 1 私 、 j + 1 1 私 + 1 、 j 1 私 + 1 、 j + 1 | 。 {\displaystyle b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1}\end{vmatrix}}.} この ( n − 1) × ( n − 1) 行列を使用して、ステップ 2 を実行して ( n − 2) × ( n − 2) 行列 C を取得します。C の各項を A の内部の対応する項で割って、 c 私 、 j = | b 私 、 j b 私 、 j + 1 b 私 + 1 、 j b 私 + 1 、 j + 1 | / 1 私 + 1 、 j + 1 {\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}} A = B、B = C とする。1 × 1 行列が見つかるまで、必要に応じて手順 3 を繰り返す。その行列の唯一の要素は行列式である。
例
ゼロなし 見つけたい
| − 2 − 1 − 1 − 4 − 1 − 2 − 1 − 6 − 1 − 1 2 4 2 1 − 3 − 8 | 。 {\displaystyle {\begin{vmatrix}-2&-1&-1&-4\\-1&-2&-1&-6\\-1&-1&2&4\\2&1&-3&-8\end{vmatrix}}.} 内部要素はすべてゼロではないため、行列を並べ替える必要はありません。
その2 × 2のサブ行列から行列を作成します 。
[ | − 2 − 1 − 1 − 2 | | − 1 − 1 − 2 − 1 | | − 1 − 4 − 1 − 6 | | − 1 − 2 − 1 − 1 | | − 2 − 1 − 1 2 | | − 1 − 6 2 4 | | − 1 − 1 2 1 | | − 1 2 1 − 3 | | 2 4 − 3 − 8 | ] = [ 3 − 1 2 − 1 − 5 8 1 1 − 4 ] 。 {\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}}&{\begin{vmatrix}2&4\\-3&-8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.} 次に、別の行列式行列を見つけます。
[ | 3 − 1 − 1 − 5 | | − 1 2 − 5 8 | | − 1 − 5 1 1 | | − 5 8 1 − 4 | ] = [ − 16 2 4 12 ] 。 {\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}}.} 次に、各要素を元の行列の対応する要素で割る必要があります。元の行列の内部は [ − 2 − 1 − 1 2 ] {\displaystyle {\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}} [ 8 − 2 − 4 6 ] {\displaystyle {\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}} 1 × 1行列 を得るには、このプロセスを繰り返す必要があります。[ | 8 − 2 − 4 6 | ] = [ 40 ] 。 {\displaystyle {\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.} 3 × 3 行列 の内部 、つまり −5 で割ると、[ − 8 ] {\displaystyle {\begin{bmatrix}-8\end{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 ] → [ 5 − 5 − 3 − 1 − 3 − 3 − 3 3 3 3 3 − 1 − 5 − 3 − 1 − 5 ] → [ − 15 6 12 0 0 6 6 − 6 8 ] 。 {\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}}.} ここで問題が発生します。この処理を続けると、最終的にはゼロ除算になってしまいます。行列式を保持し、ほとんどの行列式を事前に計算した状態で処理を繰り返すために、初期行列に対して4つの行交換を行うことができます。
[ 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 ] → [ − 3 − 3 − 3 3 3 3 3 − 1 − 5 − 3 − 1 − 5 3 − 5 1 1 ] → [ 0 0 6 6 − 6 8 − 17 8 − 4 ] → [ 0 12 18 40 ] → [ 36 ] 。 {\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となる。
縮約法がゼロ除算が発生しない場合に行列の行列式を計算するという証明は、デナノ・ヤコビ恒等式 （1841年）またはより一般的にはシルベスター行列式恒等式 （1851年）として知られる恒等式に基づいている。[ 2 ]
させてM = （ m 私 、 j ） 私 、 j = 1 k {\displaystyle M=(m_{i,j})_{i,j=1}^{k}} 1 ≤ 私 、 j ≤ k {\displaystyle 1\leq i,j\leq k} M 私 j {\displaystyle M_{i}^{j}} M {\displaystyle M} 私 {\displaystyle i} j {\displaystyle j} 1 ≤ 私 、 j 、 p 、 q ≤ k {\displaystyle 1\leq i,j,p,q\leq k} M 私 、 j p 、 q {\displaystyle M_{i,j}^{p,q}} M {\displaystyle M} 私 {\displaystyle i} j {\displaystyle j} p {\displaystyle p} q {\displaystyle q}
検出 （ M ） 検出 （ M 1 、 k 1 、 k ） = 検出 （ M 1 1 ） 検出 （ M k k ） − 検出 （ M 1 k ） 検出 （ M k 1 ） 。 {\displaystyle \det(M)\det(M_{1,k}^{1,k})=\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1}).}
私たちは、書籍『証明と確認：交代符号行列予想の物語』 [ 3 ] Doron Zeilberger の論文で与えられています。[ 4 ]
表記する1 私 、 j = （ − 1 ） 私 + j 検出 （ M 私 j ） {\displaystyle a_{i,j}=(-1)^{i+j}\det(M_{i}^{j})} （ 私 、 j ） {\displaystyle (i,j)} M {\displaystyle M} k × k {\displaystyle k\times k} M ′ {\displaystyle M'}
M ′ = （ 1 1 、 1 0 0 0 … 0 1 k 、 1 1 1 、 2 1 0 0 … 0 1 k 、 2 1 1 、 3 0 1 0 … 0 1 k 、 3 1 1 、 4 0 0 1 … 0 1 k 、 4 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 1 1 、 k − 1 0 0 0 … 1 1 k 、 k − 1 1 1 、 k 0 0 0 … 0 1 k 、 k ） 。 {\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_{1,4}&0&0&1&\ldots &0&a_{k,4}\\\vdots &\vdots &\vdots &\vdots &&\vdots &\vdots \\a_{1,k-1}&0&0&0&\ldots &1&a_{k,k-1}\\a_{1,k}&0&0&0&\ldots &0&a_{k,k}\end{pmatrix}}.} （最初の列と最後の列はM ′ {\displaystyle M'} 、 A {\displaystyle A} 検出 （ M M ′ ） {\displaystyle \det(MM')} M M ′ {\displaystyle MM'}
M M ′ = （ 検出 （ M ） m 1 、 2 m 1 、 3 … m 1 、 k − 1 0 0 m 2 、 2 m 2 、 3 … m 2 、 k − 1 0 0 m 3 、 2 m 3 、 3 … m 3 、 k − 1 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 m k − 1 、 2 m k − 1 、 3 … m k − 1 、 k − 1 0 0 m k 、 2 m k 、 3 … m k 、 k − 1 検出 （ M ） ） {\displaystyle MM'={\begin{pmatrix}\det(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}}} 私たちが使用する場所m 私 、 j {\displaystyle m_{i,j}} （ 私 、 j ） {\displaystyle (i,j)} M {\displaystyle M} 検出 （ M ） 2 ⋅ 検出 （ M 1 、 k 1 、 k ） {\displaystyle \det(M)^{2}\cdot \det(M_{1,k}^{1,k})} 検出 （ M ） ⋅ 検出 （ M ′ ） {\displaystyle \det(M)\cdot \det(M')} 検出 （ M ′ ） = 1 1 、 1 1 k 、 k − 1 k 、 1 1 1 、 k = 検出 （ M 1 1 ） 検出 （ M k k ） − 検出 （ M 1 k ） 検出 （ M k 1 ） 、 {\displaystyle \det(M')=a_{1,1}a_{k,k}-a_{k,1}a_{1,k}=\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1}),} 検出 （ M M ′ ） {\displaystyle \det(MM')} 検出 （ M ） {\displaystyle \det(M)} k 2 {\displaystyle k^{2}} （ m 私 、 j ） 私 、 j = 1 k {\displaystyle (m_{i,j})_{i,j=1}^{k}}
参考文献 ↑ Dodgson, CL (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. Bibcode : 1866RSPS...15..150D . ↑ シルベスター、ジェームズ・ジョセフ (1851)。「線形的に等価な二次関数の小行列式間の関係について」。 フィロソフィカル・ マガジン 。1 : 295–305 。 , AG; Akritas, EK; Malaschonok, GI (1996). "シルベスターの（行列式）恒等式のさまざまな証明". Mathematics and Computers in Simulation . 42 ( 4– 6): 585. doi : 10.1016/S0378-4754(96)00035-3 に 引用されています。 ↑ ブレソー、デイビッド (1999). 証明と確認：交代符号行列予想の物語 . ケンブリッジ大学出版局. ISBN 9781316582756 。↑ Zeilberger, Doron (1997). "Dodgsonの行列式評価規則は二股をかける男女によって証明された" . Electron. J. Comb . 4 (2) R22. doi : 10.37236/1337 . 2023年 10月27日 取得 。
さらに読む Bressoud, David M. および Propp, James、「交代符号行列予想はどのように解決されたか」、アメリカ数学会報 、46 (1999)、637-646。Knuth, Donald 、「重複するパフィアン」、電子組合せ論ジャーナル 、3 巻2号（1996年）。ロトキン、マーク（1959）。 「契約法の 注釈」。アメリカ数学月報 。66 （6）：476–479。doi ：10.2307 /2310629。JSTOR 2310629 。 Mills, William H.、Robbins, David P.、Rumsey, Howard, Jr.、「マクドナルド予想の証明」、Inventiones Mathematicae 、66 (1982)、73-87。 Mills, William H.、Robbins, David P.、Rumsey, Howard, Jr.、「交代符号行列と下降平面分割」、Journal of Combinatorial Theory 、シリーズA ロビンス、デビッド・P.、物語1 、 2 、 7 、 42 、 429 、 7436 、 ⋯ {\displaystyle 1,2,7,42,429,7436,\cdots } The Mathematical Intelligencer 、13 (1991)、12-19。 
