行列式の計算史

手計算から最先端アルゴリズムまで

目次

1. はじめに

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

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

前提知識

  • 行列と行列式の基本概念（$2 \times 2$, $3 \times 3$ の行列式が計算できる程度）
  • $O$ 記法（ビッグ・オー記法）の意味：$O(n^3)$ は「$n$ が大きいとき計算量が $n^3$ に比例する」程度の理解で十分
  • 行列の積の定義（第6節以降で使用）
黎明期 公式の時代 消去法 計算機 高速化 最先端 1683 関孝和 1693 Leibniz 1750 Cramer 1772 Laplace 1801 Gauss 1812 Cauchy 1948 LU分解 1968 Bareiss 1969 Strassen 1990 C–W 2012 Williams 2024 最新 O(n!) O(n³) O(nω) 計算量: O(n!) → O(n³) → O(n2.37...)　——　340年で階乗オーダーから多項式オーダーへ

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 の研究は完全に独立であり、東西の数学が同時期に同じ概念に到達した注目すべき例である。

この時代の計算量：まだ体系的な計算手法は確立されておらず、小さい行列に対する個別の計算に限られていた。現代の用語で言えば、定義に基づく計算は $O(n \cdot n!)$ に相当する。

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

3.1 Cramer の公式（1750）

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

$$x_j = \frac{\det(A_j)}{\det(A)}$$

ここで $A_j$ は係数行列 $A$ の第 $j$ 列を定数項で置き換えた行列である。

Cramer の公式は理論的に美しいが、$\det(A)$ を定義通りに計算すると $n!$ 個の項の和になるため、$n$ 個の未知数に対して $O(n \cdot n!)$ の計算量が必要となる。$n = 20$ の場合、約 $20! \approx 2.4 \times 10^{18}$ 回の演算が必要であり、手計算はもちろんコンピュータでも非現実的である。

3.2 Laplace 展開（1772）

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

$$\det(A) = \sum_{j=1}^{n} (-1)^{i+j} \, a_{ij} \, M_{ij}$$

この再帰的な手法は構造的に明快であり、理論的な証明でよく用いられる。しかし計算量は再帰的に $T(n) = n \cdot T(n-1)$ となり、結局 $O(n!)$ である。

$O(n!)$ の壁：$n$ が大きくなると $n!$ は指数関数よりも速く増大する。Cramer も Laplace も、この壁を越えることはできなかった。突破口を開いたのは Gauss である。

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

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

4.1 Gauss の消去法（1801）

Carl Friedrich Gauss（カール・フリードリヒ・ガウス）は 1801 年の『数論研究（Disquisitiones Arithmeticae）』で消去法を体系化した。行基本変形で行列を上三角行列に変形し、対角成分の積として行列式を計算する手法は、計算量を一気に $O(n^3)$ に引き下げた。

$O(n!)$ と $O(n^3)$ の差は劇的である：

$n$$n!$（Laplace 展開）$n^3$（Gauss 消去法）高速化倍率
2280.25倍（逆転）
36270.22倍（逆転）
424640.38倍（逆転）
5120125≈ 1倍（交差点）
103,628,8001,000≈ 3,600倍
20$2.4 \times 10^{18}$8,000≈ $3 \times 10^{14}$倍
100$9.3 \times 10^{157}$$10^6$≈ $10^{151}$倍
10⁰ 10³ 10⁶ 10⁹ 10¹² 10¹⁵ 10¹⁸ 計算量（対数スケール） 1 2 5 10 20 行列サイズ n（対数スケール） n = 5（交差点） n=1: 共に 1 3.6 × 10⁶ 10³ 2.4 × 10¹⁸ 直線（傾き 3） n!（Laplace 展開） n³（Gauss 消去法）

図：$n!$ と $n^3$ の比較（両対数スケール）。多項式 $n^3$ は直線（傾き $3$）となり、$n!$ の超多項式的な増大が際立つ。$n = 1$ で一致し、$n = 5$ 付近で再び交差する。

$n \leq 4$ では $n!$ の方がむしろ小さく、Laplace 展開で十分に計算できる。$n = 5$ が両者の交差点であり、ここではほぼ同じ計算量となる。$n \geq 10$ では差が急激に開き、Gauss 消去法の優位性は圧倒的になる。つまり「$O(n^3)$ が常に速い」のではなく、小さい行列では定義通りの展開で十分であり、$n$ の増大とともに消去法の威力が発揮されるのである。

Gauss はまた「determinant」という語を初めて使用した人物の一人でもある（ただし、現在とはやや異なる文脈で）。

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

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$ の積に分解する：

$$A = LU$$

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

$$\det(A) = \det(L) \cdot \det(U) = \prod_{i=1}^{n} l_{ii} \cdot \prod_{i=1}^{n} u_{ii}$$

1948 年に Alan Turing（アラン・チューリング）は部分ピボット（partial pivoting）を導入し、数値安定性を大幅に改善した。浮動小数点演算では丸め誤差が蓄積するため、各ステップで最大の要素を選んでピボットとする工夫が不可欠である。

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）の分野で特に有用である。

Bareiss が活躍する場面：

  • 数式処理システム（Mathematica, SymPy, SageMath）：変数を含む行列の行列式を厳密に計算する際、浮動小数点演算は使えない。Bareiss なら整数・多項式のまま処理できる。
  • 暗号理論：有限体 $\mathbb{F}_p$ 上の行列式計算では、除算（逆元計算）は高コストである。Bareiss の分数回避は体の演算を最小化する。
  • グラフ理論：Kirchhoff の行列木定理により、グラフの全域木の数は Laplacian 行列の余因子として求まる。この行列は整数成分なので、Bareiss で厳密に計算するのが自然である。

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

6.1 Strassen の衝撃（1969）

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

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

$$O(n^{\log_2 7}) = O(n^{2.807\ldots})$$

が達成される。$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）と呼ばれ、$n \times n$ 行列の乗算に必要な計算量のオーダーを $O(n^\omega)$ と書く。

核心的な等価性：

行列乗算、LU 分解、行列式、逆行列の計算量はすべて $O(n^\omega)$ であり、互いに帰着可能である。したがって、行列乗算の高速化は自動的に行列式の高速化をもたらす。

6.3 $\omega$ の歴史的推移

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

年研究者$\omega$ の上界備考
—（定義通り）3.0標準的な行列乗算
1969Strassen2.807$\log_2 7$、最初の突破
1979Pan2.796
1981Schönhage2.548$\tau$ 定理
1982Coppersmith–Winograd2.496
1986Strassen2.479レーザー法
1990Coppersmith–Winograd2.376長年の最良記録
2010Stothers2.3737CW法の改良
2012Williams2.3729
2014Le Gall2.3729わずかに改善
2020Alman–Williams2.3728
2022Duan–Wu–Zhou2.3719新手法で大幅改善
2024Williams–Xu–Xu–Zhou2.3713現在の最良記録

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

7.1 理論的下界

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

$$\omega \geq 2$$

現在の最良記録 $\omega \leq 2.3713\ldots$ と下界 $\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つの系譜に分類できる。

① 定義ベース（展開法） O(n!) 関孝和 / Leibniz 1683 / 1693 Cramer の公式 1750 Laplace 展開 1772 理論・証明で活躍 ② 消去法ベース O(n³) Gauss 消去法 1801 LU 分解 20世紀 部分ピボット付き LU LAPACK Bareiss (1968) 整数特化 実用上の標準手法 ③ 高速行列乗算ベース O(nω), ω→2? Strassen 1969 | 2.807 C–W 1990 | 2.376 Williams+ 2012 | 2.373 DWXZ+ 2024 | 2.371 理論的最先端 ブロック LU で帰着

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

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

9. まとめ

時代代表的手法計算量用途・特徴
17世紀 関孝和・Leibniz $O(n \cdot n!)$ 連立方程式の解法として行列式を発見（$n \leq 5$ の手計算）
18世紀 Cramer / Laplace $O(n!)$ 理論・証明、小行列（$n \leq 4$）の手計算
19世紀 Gauss 消去法 $O(n^3)$ 教育・手計算、消去法の原型
20世紀前半 LU 分解 + ピボット $O(n^3)$ 実用の標準（LAPACK, NumPy, MATLAB）
1969〜 Strassen / CW $O(n^{2.376\ldots})$ 超大規模行列、$O(n^3)$ の壁を突破
2020年代 Williams ほか / Duan ほか $O(n^{2.371\ldots})$ 純粋理論、$\omega = 2$ への漸近的改善

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

参考文献

関連ページ