行列式の計算史

1. はじめに

$n \times n$ 行列の行列式を計算する——この問題は 340 年以上にわたって数学者と計算機科学者を魅了してきた。17世紀に関孝和と Leibniz が連立方程式の解法として行列式の概念を発見して以来、計算量は $O(n!)$ から $O(n^3)$、そして $O(n^{2.371\ldots})$（理論上の上界。実用の標準はピボット付き LU 分解の $O(n^3)$）へと改善されてきた。

本稿では、行列式の計算手法がいつ・どのように進化してきたかを概観し、手法間の系譜を系統図として整理する。

2. 黎明期：連立方程式から行列式へ（17世紀）

2.1 関孝和（1683）

行列式の歴史は、日本の数学者関孝和（せき たかかず）に始まる。1683年の著作『解伏題之法（かいふくだいのほう）』において、関は連立方程式を解くために、現在の行列式に相当する計算手法を独自に開発した。

関は「行列式」という言葉こそ使わなかったが、$2 \times 2$、$3 \times 3$、$4 \times 4$、$5 \times 5$ の行列式を計算する一般的な方法を与えた。これは Leibniz の研究より約 10 年早い。

2.2 Leibniz（1693）

ヨーロッパでは、Gottfried Wilhelm Leibniz（ゴットフリート・ヴィルヘルム・ライプニッツ）が 1693 年に l'Hôpital への手紙の中で、連立方程式が解をもつ条件を行列式的な表現で述べた。Leibniz は、係数を二重添字 $a_{ij}$ で表し、それらの積と符号の組み合わせで解の存在条件を記述した。

関と Leibniz の研究は完全に独立であり、東西の数学が同時期に同じ概念に到達した注目すべき例である。

3. 公式の時代（18世紀）

3.1 Cramer の公式（1750）

Gabriel Cramer（ガブリエル・クラメル）は 1750 年の著作で、$n$ 元連立1次方程式の解を行列式で表す公式を発表した。

ここで $A_j$ は係数行列 $A$ の第 $j$ 列を定数項で置き換えた行列である（この公式は $\det(A) \neq 0$ のときに成り立つ）。

Cramer の公式は理論的に美しいが、$\det(A)$ を定義通りに計算すると $n!$ 個の項の和になるため、$\det(A)$ と $\det(A_1), \ldots, \det(A_n)$ の $n+1$ 個の行列式それぞれに $O(n \cdot n!)$、合わせて $O(n^2 \cdot n!)$ の計算量が必要となる。$n = 20$ の場合、行列式 1 個の項の数だけでも $20! \approx 2.4 \times 10^{18}$ 個あり、手計算はもちろんコンピュータでも非現実的である。

3.2 Laplace 展開（1772）

Pierre-Simon Laplace（ピエール＝シモン・ラプラス）は 1772 年に、行列式を、小行列式（minor）に符号を付けた余因子で展開する一般的な方法を与えた。これが余因子展開（Laplace 展開）である。

ここで $i$ は展開に使う行（固定）、$M_{ij}$ は第 $i$ 行と第 $j$ 列を除いた小行列式である。この再帰的な手法は構造的に明快であり、理論的な証明でよく用いられる。しかし計算量は再帰的に $T(n) = n \cdot T(n-1)$ となり、結局 $O(n!)$ である。

なお、1771 年に Vandermonde（ヴァンデルモンド）は、行列式を連立方程式の付属物としてではなく独立した数学的対象として初めて扱った。これは行列式理論の発展において重要な転換点であった。

4. Gauss 消去法：$O(n!)$ から $O(n^3)$ へ（19世紀に普及）

4.1 Gauss と消去法（1809〜1810）

Carl Friedrich Gauss（カール・フリードリヒ・ガウス）は、1809〜1810 年に小惑星パラスの軌道計算（最小二乗法の正規方程式）で消去法を体系的に用い、これが手計算者の間に広まった（そのため現在「Gauss の消去法」と呼ばれる）。消去法そのものはもっと古く、中国の『九章算術』や Newton（1670 年頃）にも見える。行基本変形で行列を上三角行列に変形し、対角成分の積をとれば行列式が求まる（行を交換すると符号が反転し、行を定数倍すると行列式もその倍になるので、それを記録しておく）。この方法なら計算量は $O(n^3)$ で済む。

$O(n!)$ と $O(n^3)$ の差は劇的である（下の表は定数倍を無視して $n!$ と $n^3$ をそのまま比べた目安）：

定数倍を無視した $n!$ と $n^3$ では、$n = 5$ 付近が両者の交差点になる。ただし実際の乗算回数（除算を含む）で数えると、余因子展開は $2, 9, 40, 205$ 回、消去法は $3, 10, 23, 44$ 回（$n = 2$〜$5$）で、$n \leq 3$ では余因子展開、$n \geq 4$ では消去法の方が少ない。$n \geq 10$ では差が急激に開き、Gauss 消去法の優位性は圧倒的になる。つまり「$O(n^3)$ が常に速い」のではなく、小さい行列では定義通りの展開で十分であり、$n$ の増大とともに消去法の威力が発揮されるのである。

Gauss はまた「determinant」という語を初めて使用した人物の一人でもある（1801 年の『数論研究（Disquisitiones Arithmeticae）』で、二次形式の判別式の意味で。現在とはやや異なる文脈である）。

消去法による行列式の計算は、行列式の導出：行基本変形と上三角行列で詳しく解説している。

4.2 Cauchy と行列式の体系化（1812）

Augustin-Louis Cauchy（オーギュスタン＝ルイ・コーシー）は 1812 年の論文 "Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment" で行列式の理論を体系的に整理し、「determinant」を現在の意味で定着させた。行と列の対称性、積の行列式が行列式の積に等しいこと（$\det(AB) = \det(A)\det(B)$）など、多くの基本的性質をこの論文で確立した。

4.3 Dodgson condensation（1866）

『不思議の国のアリス』の著者として知られる Charles Dodgson（チャールズ・ドジソン、筆名ルイス・キャロル）は、1866 年に凝縮法（condensation）と呼ばれる手法を発表した。これは Desnanot–Jacobi 恒等式に基づき、行列を縮小しながら行列式を計算する方法である。計算量は $O(n^3)$ だが、Gauss 消去法とは異なるアプローチとして興味深い。ただし、中間段階でゼロ除算が発生する場合があり、数値的安定性に課題がある。

5. 計算機時代：LU 分解と数値安定性（20世紀）

5.1 LU 分解と部分ピボット

20世紀に入ると、Gauss 消去法は LU 分解として定式化され、コンピュータの登場とともに数値計算の中心となった。行列 $A$ を下三角行列 $L$ と上三角行列 $U$ の積に分解する：

行列式は対角成分の積として計算できる：

LU 分解は 1938 年にポーランドの天文学者 Tadeusz Banachiewicz が導入した。1948 年には Alan Turing（アラン・チューリング）が消去法・LU 分解の丸め誤差を解析し、浮動小数点演算では、各ステップで現在の列の中で絶対値が最大の要素をピボットに選ぶ部分ピボット（partial pivoting）が数値的安定性のために重要であることが広く認識されるようになった（多くの行列で安定に働くが、どんな行列でも安定とは限らない）。行の交換を伴うので分解は $PA = LU$（$P$ は置換行列）となり、$L$ の対角成分を 1 とすれば $\det(A) = \operatorname{sgn}(P) \prod_{i=1}^{n} u_{ii}$ である（行の交換の回数が奇数なら符号が反転する）。

5.2 LAPACK と実用的な実装

LU 分解は LAPACK（Linear Algebra PACKage）の中核アルゴリズムとなり、NumPy, MATLAB, Julia など主要な数値計算環境で標準的に使用されている。計算量は $O(n^3)$ であり、定数係数も小さいため、実用上はこれが最も広く使われる手法である。

5.3 Bareiss アルゴリズム（1968）

Erwin Bareiss（アーウィン・バレイス）は 1968 年に分数なし消去法（fraction-free elimination）を発表した。整数行列に対して整数のまま計算を進め、中間段階での分数の発生を回避する。

通常の Gauss 消去法は除算を含むため、整数行列でも有理数が中間結果に現れる。Bareiss アルゴリズムでは適切な除算を組み合わせることで整数性を保つ。計算量は同じ $O(n^3)$ だが、数式処理（symbolic computation）の分野で特に有用である。

6. 高速アルゴリズムの幕開け（1969〜）

6.1 Strassen の衝撃（1969）

1969 年、Volker Strassen（フォルカー・シュトラッセン）は行列乗算を $O(n^3)$ より速く行える画期的なアルゴリズムを発表した。通常の $2 \times 2$ 行列の積には 8 回の乗算が必要だが、Strassen は巧妙な組み合わせにより 7 回に削減した。

これを再帰的に適用すると：

が達成される。$O(n^3)$ が最善と信じられていた常識を覆す結果であり、「$O(n^3)$ の壁」の存在自体が否定された。

6.2 行列式と行列乗算の計算量的等価性

行列式の計算は行列乗算に帰着できる。具体的には：

• LU 分解は行列乗算と同じ計算量 $O(n^\omega)$ で実行可能（Block LU decomposition）
• 行列式は LU 分解の対角成分の積なので、同じく $O(n^\omega)$
• 逆行列も同じ $O(n^\omega)$（Bunch–Hopcroft, 1974）

ここで $\omega$ は行列乗算指数（matrix multiplication exponent）と呼ばれ、任意の $\varepsilon > 0$ について $n \times n$ 行列の乗算が $O(n^{\omega + \varepsilon})$ で行えるような指数の下限（inf）である。$O(n^\omega)$ そのものが達成されるとは限らないが、本稿では慣例に従って $O(n^\omega)$ と書く。

6.3 $\omega$ の歴史的推移

Strassen 以降、$\omega$ の上界を下げる研究が精力的に進められた：

7. 最先端：$\omega = 2$ は達成可能か？

7.1 理論的下界

$n \times n$ 行列の乗算結果は $n^2$ 個の成分をもつ。入力も $2n^2$ 個の成分があるので、すべてを読むだけで $\Omega(n^2)$ の計算量が必要である。したがって：

2024 年時点の記録 $\omega < 2.3714$ と下界 $\omega \geq 2$ の間にはまだギャップがある。多くの研究者は $\omega = 2$ が成り立つと予想しているが、証明はされていない。

7.2 実用性の壁

理論的に最良のアルゴリズムが実用的とは限らない。Strassen 以降の高速アルゴリズムには共通の課題がある：

• 巨大な定数係数：$O$ 記法に隠された定数が極めて大きく、理論上の優位性が発揮されるのは天文学的なサイズの行列に限られる（galactic algorithm）
• 数値安定性：高速アルゴリズムは数値的に不安定になりやすい
• メモリ効率：再帰的な分割がメモリアクセスパターンを複雑にする

実用的には、$n$ が数百〜数千程度なら LAPACK の LU 分解（$O(n^3)$）が最速であり、非常に大きな行列に対しても Strassen アルゴリズム（$O(n^{2.807})$）が限界である。$O(n^{2.37\ldots})$ のアルゴリズムが実用的に使われたことはない。

8. 系統図：3つの系譜

行列式の計算手法は大きく3つの系譜に分類できる。

3つの系譜の関係をまとめると：

• 系譜①（定義ベース）は計算量 $O(n!)$ と非効率だが、理論的な議論や証明で今も活躍する
• 系譜②（消去法ベース）は $O(n^3)$ で、実用上の標準手法である
• 系譜③（高速行列乗算ベース）は理論上 $O(n^{2.37\ldots})$ を達成するが、実用には至っていない
• 系譜②と③はブロック LU 分解を通じて理論的に（代数的計算量の意味で）等価であり、行列乗算の高速化が直接 LU 分解の高速化につながる

9. まとめ

340年の歴史を振り返ると、行列式の計算は「階乗時間 → 多項式時間 → 理論限界への挑戦」という3つの段階を経てきた。第一の革命は消去法（Gauss の名で呼ばれる）による $O(n!)$ から $O(n^3)$ への改善であり、第二の革命は Strassen による $O(n^3)$ の壁の突破である。$\omega = 2$ の達成は理論計算機科学・代数的計算量の大きな未解決問題の一つとして、今なお研究が続いている。

よくある質問