2025/12/27 4:03
**ルイス・キャロルが行列式を計算した方法（2023）**
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
Lewis Carrollの「Dodgson濃縮」は、(n\times n) 行列の行列式を計算するための洗練されたアルゴリズムです。各ステップでは、すべての要素をその周囲の (2\times2) サブマトリクスの行列式に置き換え、下部の行と右端の列を捨てた後、新しい各要素を元の行列から二つ手前の要素で割ります。Carrollの1867年の論文では、分母としてどの隣接要素（(i) と (i+1)、または (j) と (j+1)）を使用すべきかが曖昧に示されており、現代の実践ではゼロ分母を避けるために行や列を並べ替えるか、線形結合を適用して解決します。整数行列から開始すると、中間行列と除算はすべて正確な整数で残るため、Dodgson濃縮はガウス消去法が導入する可能性のある非整数中間値を回避します。このアルゴリズムは (O(n^3)) の演算量（ガウス消去に匹敵）を要し、自然に並列化できるため、多コアCPUやGPUでの実装に魅力的です。その単純さから教育ツールとしても有用であり、シンボリック計算や暗号学的応用における正確な整数代替手段としても役立ちます。例えば、次の行列にこの方法を適用すると
[
\begin{pmatrix}
3&1&4&1\
5&9&2&6\
0&7&1&0\
2&0&2&3
\end{pmatrix}
]
行列式は228となります。
本文
チャールズ・ドッグソン（ルイス・キャロル）
現在「ドッグソン濃縮法」と呼ばれる手法を発見した人物。
概要
基本的な考え方は、行列を繰り返し 濃縮 することです：
元の行列から1 行と 1 列ずつ減らした新しい行列に置き換えます。
新しい行列の各要素は、その位置の要素とその南・東・南東隣接セルからなる (2\times2) 部分行列の行列式です。
底辺の行と右端の列は、こうした隣接セルが存在しないため除外されます。
アルゴリズムのもう一つの要素（分母に関する部分）は、記号を導入してから説明します。
詳細
- (A) は求めたい行列式を持つ元の行列。
- (A(k)) は濃縮操作を (k) 回行った後の行列。
ステップ 1 – 概要で述べた方法により (A(1)) を計算します。
ステップ 2 – (k \ge 2) のとき、(A(k)) の各要素は
(2\times2) 行列式を「２ ステップ前の行列」のある要素で割ったものです（具体的な分母は記号で明示します）。
ドッグソンが1867 年に発表した原稿は読めますが、
どの要素が分母になるかが混乱しやすいです。彼の最初の例では、該当する要素が偶然同じ値になっているため、分母の位置が明確に示されていません。
例
濃縮法を用いて (4\times4) 行列の行列式を求めるとき：
Det[{{3, 1, 4, 1}, {5, 9, 2, 6}, {0, 7, 1, 0}, {2, 0, 2, 3}}]
計算結果は 228 です。
割り算
アルゴリズムには割り算が含まれるため、ゼロ除算を避ける必要があります。
ドッグソンは次のように助言しています：
与えられた行列ブロック（内部）が 0 を含まないように配置し直す。
行または列を転置するか、ある行に別の行の整数倍を加えることで実現できる。
この前処理によりゼロ除算が起きず、元の行列が整数要素で構成されている場合、途中経路上のすべての行列も整数となります。
効率性
- 余因子展開（従来の方法）は (O(n!)) のステップ数を必要とします。
- 部分ピボット付きガウス消去法 と ドッグソン濃縮法 はともに (O(n^3)) で実行できます。
濃縮法は手計算でも簡単に教えられ、拡張性が高く、途中のすべての行列を整数で保つ点が魅力です。また、各 (2\times2) 行列式を同時に計算できるため、自然と並列化可能です。
関連投稿
- 余因子・行列式・随伴行列
- なぜ 1 列のある行列式が重要か？
- 線形代数の応用