ルイス・キャロルの行列式の計算方法 (2023)

150日前原文(johndcook.com)

概要

Charles Dodgson （Lewis Carroll）による行列式計算手法「 Dodgson凝縮法」の紹介
手計算に適した方法だが、 機械計算 にも有用
行列を繰り返し凝縮し、行・列を減らしていくアルゴリズム
ゼロによる割り算回避 のための前処理が必要
Gaussian eliminationと同等の計算効率、 整数保持 ・並列化が容易

Dodgson凝縮法（Dodgson Condensation）の概要

Dodgson凝縮法 は、行列式を効率よく計算するための手法
行列のサイズを 1つずつ減らしながら 計算を進めるアルゴリズム
各要素を、その要素と 南・東・南東 の隣接要素で作る2×2小行列の行列式で置き換える
一番下の行と一番右の列は削除
各ステップで 2ステップ前の要素で割り算 を行う必要

アルゴリズム詳細

元の行列を A、k回凝縮した行列を A(k) と表記
A(1) は、2×2小行列の行列式で構成
A(2) 以降は、各2×2行列式を 2ステップ前の要素で割る
割り算の分母の選び方には注意が必要、Dodgson本人の論文でもやや分かりにくい記述
計算例：4×4行列での凝縮手順と結果の検証（例：Mathematicaで228を得る）

ゼロによる割り算回避

アルゴリズム中で ゼロ割り が発生しないようにする必要
Dodgsonの推奨： 行や列の入れ替え、または 他の行を定数倍して加算 することで内部のゼロを回避
この前処理は主に ゼロ割り回避 のためだが、他の理由があるかは不明
元の行列が 整数成分のみ の場合、途中の計算でも全て整数を保持

効率と他手法との比較

初学者は 余因子展開 で行列式計算を学ぶが、これは O(n!) で非効率
Gaussian elimination （部分ピボット付き消去法）は O(n³) で効率的
- Dodgson凝縮法も O(n³) の計算量
- Gaussian eliminationでもゼロ割り回避のため部分ピボットが必要
Dodgson凝縮法は手計算しやすく、拡張性も高い
- 途中で整数を保つため、 整数行列 に向いている
- 各2×2行列式は 並列計算 が可能

Hackerたちの意見

HNのタイトルフィルターが最初の「How」をカットしちゃったね。手動で戻せるよ。

└

「‘how’は省いちゃえ。すっきりするから。」

必要なら与えられたブロックを整理して、内部にゼロが入らないようにしなさい。ゼロってアラビア語から来てたってこと、すっかり忘れてた。別の言語では数字を意味することもあるんだよね。

└

笑　そのつながりに気づかなかったわ — トルコ語ではゼロは「sıfır」で、確かに「cipher」に似てる。パスワードは「şifre」って言うんだけど、これも似てるよね。ネットで調べたら、道筋はsifr（アラビア語でゼロ）→cifre（フランス語、最初はゼロ、その後は数字、さらに暗号メッセージ）→şifre（トルコ語でコード/暗号）って感じらしい。

└

オランダ語も同じだよ：「Cijfer」、ドイツ語は「Ziffer」、フランス語は「Chifre」、スペイン語は「Cifra」。

└

タミル語では、今でもゼロを意味するよ。ただ、タミル語には「f」や「ph」の音がないから、普通は「サイバー」みたいに発音されるんだ。

└

面白い事実：ゼロと数字はアラブ人によって発明されたわけじゃないよ。アラブ人は古代のヒンドゥー教徒/インド人から数学的ゼロ、数字、十進法、数学的計算の概念を学んだんだ。そしてアラブ人から、ヨーロッパ人がそれを学んだ。

└

それがメジャーゼロと彼の組織サイファーの説明になるね、メタルギアシリーズの中で。

ダッジソンの1867年のオリジナル論文は意外と読みやすいよ。数学の記法や用語が時間とともに変わるのに、驚くほど読みやすい。ジャバウォックもかなり読みやすいから、あまり驚くことじゃないね。

└

この場合、「読みやすい」というのは「理解しやすい」という意味だと思うけど、ジャバウォックにはあまり当てはまらないかもね（意図的にそうなってるし）。

仕事と子供たちで頭が疲れてないときに、ちゃんと座ってこれを読みたいな。

テレンス・タオがこれについてブログに書いてたよ。 https://terrytao.wordpress.com/2017/08/28/dodgson-condensati...

うわ、共因子法だけじゃなかったんだね。あれが嫌いで、上級の行列のトピックに興味を持つのが億劫になっちゃった。

└

行列式は現代の上級行列のトピックでは中心的な役割を果たしてないと思う。幸運なことに、最初の線形代数の授業でAxlerの「Linear Algebra Done Right」（行列式を使わない証明を使ってる）を読んだから、長い間行列式について気にしなくて済んだ。編集：共因子展開を超えて、3x3行列の行列式を書くための少なくとも一つの簡単な方法はみんな知っておくべきだよ。この論文にいい調査があるよ：Dardan Hajriza, "New Method to Compute the Determinant of a 3x3 Matrix," International Journal of Algebra, Vol. 3, 2009, no. 5, 211 - 219.

大学の時と同じように、行列式の計算はできるけど、実際に何に使うのか全然わからないな。

└

3blue1brownは友達だよ。

└

例えば、3x3の行列があるとするよ。これは実ベクトルを実ベクトルに写す線形変換なんだ。入力として体積1の立方体があって、それをこの変換に送るとする。行列の行列式の絶対値が、変換された立方体の体積を教えてくれる。符号は、パリティの反転があるかどうかを示してくれる。

└

2x2行列の固有値xを求めるために二次方程式を作成する（|A - xI| = 0）。行列の逆行列は、古典的な随伴行列に行列式の逆数を掛けることで計算できる。クレーマーの法則を使って、行列式を計算することで線形方程式の系を解く。もしxがAの固有値なら、A - xIは非自明な零空間を持つことを考えよう（記憶法として|A - xI| = 0を使う）。

└

他の人も言ってたけど、行列の行列式は、その空間の関連する線形変換について2つのすごく重要な情報を提供するんだ。行列式の符号は、その線形変換が空間の鏡映を含むかどうかを教えてくれるし、行列式の絶対値は、その線形変換が（多次元の）体積を保つかどうかを示してる。つまり、形は変わるけど体積は変わらない等体積変換なのか、空間が拡大するのか圧縮されるのかは、行列式の絶対値が1、1より大きい、または1より小さいかによって決まるんだ。特定の線形変換が何をするのかを理解するには、通常、いくつかの簡単な変換に分解するんだ。例えば、サイズと形を保つ回転や反射（等距離変換）、体積は保つけど形は保たない等体積変換、形は保つけど体積は保たない相似変換（行列式の絶対値から計算されるスケールファクターを使う）などね。行列式は、反射と相似変換という2つの簡単な部分変換を提供してくれるんだ。

└

任意の平行六面体の体積変化を計算できる理由が3つあるよ： - det M = 0 の場合、Mは逆行列を持たない。これを知っておくといろんな理由で便利なんだ。例えば、Mx = bという方程式を両辺で逆行列を取って解くことができないってことになる（x = M \ b）。行列の固有値を見つけるためには、Mx = λxを再配置することができる（M-λI)x = 0、det M-λI = 0という多項式方程式になる）。 - 回転は体積を保つから、回転群はdet M = 1の行列として表現できる（まあ、単位に接続された成分ね）。これは理論物理学で便利で、そういう群を扱うときに使える表現が必要なんだ。 - 情報理論では、微分エントロピー（連続確率分布の特定の点を記述するのに必要な平均ビット数）は、分布を広げると増加し、圧縮するとちょうどlog |det M|だけ減少する。非線形変換は、その勾配で線形化できる。これは、正規化フローニューラルネットワークを使った画像圧縮（そして生成）に役立つんだ。

http://www.gutenberg.org/files/37354/37354-pdf.pdf

ハクソク