1. 謎の表の掛け算ルール？
数学の授業で行列を習ったとき、こんなルールがありました。
A = | a b | B = | e f |
| c d | | g h |
A × B = | ae+bg af+bh |
| ce+dg cf+dh |計算の仕方はわかるのですが、何のためにこれを計算するのかがわかりませんでした。
数字を四角く並べて、妙な順番で掛け合わせる。
あんまり意味が見えないまま、計算練習をしていました。
ただ、最近、競技プログラミングの問題を解いていて、行列が役に立ちました1。
2. 用途1：繰り返しの変換を畳む（行列累乗）
2.1. フィボナッチ数列で見る三つのアプローチ
フィボナッチ数列は、アルゴリズムの入門でよく使われる題材です2。
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)最初に習う実装は再帰です。
(defun fib-naive (n)
(if (< n 2) n
(+ (fib-naive (- n 1))
(fib-naive (- n 2)))))Code language: Lisp (lisp)同じ値を何度も計算するので、N が大きくなると指数的に遅くなります3。
そこで、再計算を減らす「DP（動的計画法）」を使います。
(defun fib-dp (n)
(let ((dp (make-array (1+ n) :initial-element 0)))
(setf (aref dp 1) 1)
(loop for i from 2 to n do
(setf (aref dp i) (+ (aref dp (- i 1))
(aref dp (- i 2)))))
(aref dp n)))Code language: Lisp (lisp)これで、O(N) になり、速くなりました。
ただ、N = 10^18 のような巨大な値を要求されると、これでも間に合いません。
ここで、使えるのが行列なんです。
漸化式 F(n) = F(n-1) + F(n-2) は、こう書き直せます。
| F(n+1) | | 1 1 | | F(n) |
| F(n) | = | 1 0 | × | F(n-1) |「次の状態ベクトル」が「今の状態ベクトル」に行列を掛けた結果になっています。
同じ行列を N-1 回掛ければ F(N) が求まるので、
| F(n+1) | | 1 1 |^(n-1) | F(1) |
| F(n) | = | 1 0 | × | F(0) |Mat^(n-1) を指数を2進数に分解してから累乗を求めれば O(log N) になります（二分累乗）4。
2.2. 行列操作の基本関数
ここで、行列操作の基本関数を定義しておきます。
- make-matrix size
- make-identity-matrix size
- copy-matrix size S D
- multiply-matrix size X Y D
- power-matrix size Mat power
(defun make-matrix (size)
(make-array (list size size)
:element-type 'fixnum
:initial-element 0))
;; 単位行列：対角成分が1、それ以外が0
(defun make-identity-matrix (size)
(let ((mat (make-matrix size)))
(loop for i below size do
(setf (aref mat i i) 1))
mat))
(defun copy-matrix (size s d)
(loop for i below size do
(loop for j below size do
(setf (aref d i j) (aref s i j))))
d)
;; 行列積 X × Y を D に格納する
(defun multiply-matrix (size x y d)
(let ((out (if (or (eq x d) (eq y d))
(make-matrix size)
d)))
(loop for i below size do
(loop for j below size do
(setf (aref out i j) 0)
(loop for k below size do
(setf (aref out i j)
(+ (aref out i j)
(* (aref x i k)
(aref y k j)))))
(when (not (eq out d))
(copy-matrix size out d))
d))
;; 二分累乗で Mat^power を計算する
;; power=0 のとき単位行列を返す
(defun power-matrix (size mat power)
(let ((result (make-identity-matrix size)))
(loop while (plusp power) do
(when (oddp power)
(multiply-matrix size result mat result))
(multiply-matrix size mat mat mat)
(setf power (ash power -1)))
result))Code language: Lisp (lisp)2.3. フィボナッチの行列累乗の実装
この行列関数を使うと、n 項目のフィボナッチ数は、以下のように求められます。
(defun fib-matrix (n)
(when (< n 2) (return-from fib-matrix n))
(let* ((size 2)
(mat (make-matrix size)))
(setf (aref mat 0 0) 1 (aref mat 0 1) 1
(aref mat 1 0) 1 (aref mat 1 1) 0)
(let ((powered (power-matrix size mat (1- n))))
(aref powered 0 0))))
(format t "F(10) = ~a~%" (fib-matrix 10)) ; 55
(format t "F(50) = ~a~%" (fib-matrix 50))
(format t "F(100) = ~a~%" (fib-matrix 100))Code language: Lisp (lisp)ベンチマークを比較してみると、大きな差があります。
| N | 素朴な再帰 | DP | 行列累乗 | 比較の見どころ |
|---|---|---|---|---|
| 10 | 0.001 ms | ほぼ0 ms | 0.004 ms | 小さすぎて差はほぼ意味なし |
| 20 | 0.140 ms | ほぼ0 ms | 0.006 ms | 再帰がすでに行列より約23倍遅い |
| 30 | 17.940 ms | 0.001 ms | 0.006 ms | 再帰はDPの約18,000倍遅い |
| 35 | 195.218 ms | 0.001 ms | 0.006 ms | 再帰はDPの約195,000倍遅い |
| 40 | 実用外 | 0.001 ms | 0.007 ms | 再帰はここで打ち切り |
| 1,000 | 実用外 | 0.022 ms | 0.013 ms | 行列累乗がDPを上回り始める |
| 100,000 | 実用外 | 2.149 ms | 0.020 ms | 行列累乗はDPの約107倍速い |
| 1,000,000 | 実用外 | 26.301 ms | 0.024 ms | 行列累乗はDPの約1,096倍速い |
| 10^9 | 実用外 | 実用外 | 0.037 ms | 巨大なNでもほぼ変わらない |
| 10^18 | 実用外 | 実用外 | 0.080 ms | log N なのでまだ一瞬 |
2.4. ボトムアップDPと行列累乗の対応
フィボナッチで見えた構造は、競技プログラミングの多くの動的計画法を使う問題で出てきます。
行列積が使えるのは、ボトムアップDPの更新が「今の状態の各成分を定数倍して足し合わせる」形のときです。
遷移行列が毎回変わらないなら、N 回のループは行列の N 乗になります。
N 回のループ O(状態数 × N)
行列累乗 O(状態数^3 × log N)とくに状態数が小さく N が大きい問題で、劇的に速くなります。
「更新ループを行列の累乗に対応させる」——これが競プロで行列累乗を使う核心です5。
3. 用途2：行列の歴史と連立方程式
「行列」の考え方は、用途ごとに段階的に生まれました。
近代的な「行列」は、19世紀になってイギリスの数学者シルベスターが1850年に matrix という言葉を作り、ケイリーが1858年の論文で加法・乗法・逆行列を体系化しました6。
この体系化によって、行列は「係数の整理表」から、それ自体が演算できる対象へと発展しました。
しかし、最も古い起源は、紀元前後に成立した中国の数学書『九章算術』にあります7。
そこでは、連立一次方程式を解くために、係数を表に並べて行・列を操作する方法が使われていました。
たとえば、こういう問題です。
上等の米3束、中等の米2束、下等の米1束で合計39斗
上等の米2束、中等の米3束、下等の米1束で合計34斗
上等の米1束、中等の米2束、下等の米3束で合計26斗係数だけ取り出して表に並べ、行を足したり引いたりして未知数を消す計算法で、現代の「ガウス消去法」とほぼ同じ発想の記録が残されています8。
3.1. 係数表とガウス消去法
「係数の整理表」をそのまま操作するのが、ガウス消去法です。
もともと、行列が必要とされた背景には、「複数の量が互いに影響し合う関係を、まとめて扱いたい」という動機がありました。
- 産業連関表なら、各産業の供給と需要が一致する。
- 力学なら、上向きの力と下向きの力が釣り合う。
- 電気回路なら、各点で流れ込む電流と流れ出る電流が等しい。
これらはすべて「複数の量の線形結合がある値に等しい」という形で、行列の係数表として書けます。
3.2. 問題：三種類の米
競プロ的な問題で考えてみましょう。
三種類の米があります。
上等の米 1 束あたりの量を x 斗、中等の米 1 束あたりの量を y 斗、下等の米 1 束あたりの量を z 斗とします。x, y, z を求めてください。
次の 3 つの条件が与えられます。
上等の米 a11 束、中等の米 a12 束、下等の米 a13 束で、合計 b1 斗
上等の米 a21 束、中等の米 a22 束、下等の米 a23 束で、合計 b2 斗
上等の米 a31 束、中等の米 a32 束、下等の米 a33 束で、合計 b3 斗たとえば、入力例としては
3 2 1 39
2 3 1 34
1 2 3 26出力例は、
37/4 17/4 11/43.3. 連立方程式と拡大係数行列
入力例は、次の連立方程式を表します。
3x + 2y + z = 39
2x + 3y + z = 34
x + 2y + 3z = 26係数だけ取り出して「拡大係数行列」にします9。
| 3 2 1 | 39 |
| 2 3 1 | 34 |
| 1 2 3 | 26 |3.4. 行の基本変形
連立方程式の解を変えないように、行単位で操作をし、拡大係数行列の左側が単位行列になるように変形しています。
| 1 0 0 | x |
| 0 1 0 | y |
| 0 0 1 | z |たとえば、式1と式2を入れ替えても解は同じです。
また、式全体を2で割っても同じ条件を表します。
さらに、式2から式1の2倍を引いても、元の条件から導ける式なので、解の集合は変わりません。
このような操作の結果、残った数字 x y z が求める解になります。
使える行列の演算は、「行基本変形」です。
- 行の交換（swap-rows）
- 行全体を0でない数で割る、または掛ける（scale-row）
- ある行に、別の行の定数倍を足す（add-scaled-row）
(defun swap-rows (a row1 row2 start-col end-col)
(loop for col from start-col to end-col do
(rotatef (aref a row1 col)
(aref a row2 col))))
(defun scale-row (a row factor start-col end-col)
(loop for col from start-col to end-col do
(setf (aref a row col)
(* factor (aref a row col)))))
(defun add-scaled-row (a target source factor start-col end-col)
;; target 行に、source 行の factor 倍を加える
(loop for col from start-col to end-col do
(incf (aref a target col)
(* factor (aref a source col)))))Code language: Lisp (lisp)3.5. ピボット選択（find-pivot-row）
ただし、行の基本操作を数値計算するときに、誤差の問題があります。
特に浮動小数点数で計算する場合、小さい数で割ると誤差が大きくなります。
そのため、普通は「ピボット選択」をします。
ピボット選択とは、割る値としてできるだけ絶対値の大きい行を選んでから行を交換する工夫です。
- find-pivot-row
- normalize-pivot-row
- eliminate-column
(defun find-pivot-row (a col n)
(loop for row from col below n
when (not (zerop (aref a row col)))
do (return row)))
(defun normalize-pivot-row (a pivot-row pivot-col n)
;; ピボットを 1 にする
(let ((pivot-value (aref a pivot-row pivot-col)))
(scale-row a pivot-row (/ 1 pivot-value) pivot-col n)))
(defun eliminate-column (a pivot-row pivot-col n)
;; pivot-col 列について、pivot-row 以外を 0 にする
(loop for row below n do
(unless (= row pivot-row)
(let ((factor (- (aref a row pivot-col))))
(add-scaled-row a row pivot-row factor pivot-col n)))))Code language: Lisp (lisp)ここでは簡単のため、非ゼロの行を見つけたらそれをピボットにします。
浮動小数点数で安定に計算したい場合は、絶対値が最大の行を選ぶ部分ピボット選択を使います。
ただ、find-pivot-row は、ピボットが見つからない場合に nil が返り、swap-rows でエラーになります。
特異行列、つまり逆行列を持たない行列の場合があるからです。
3.6. ガウス消去法の実装
ガウス消去法は、これらの操作を組み合わせて、拡大係数行列の左側が単位行列になるように、段階的に変形しています。
(defun gaussian-elimination (n a)
;; a は n × (n+1) の拡大係数行列
(loop for col below n do
(let ((pivot-row (find-pivot-row a col n)))
(swap-rows a col pivot-row col n)
(normalize-pivot-row a col col n)
(eliminate-column a col col n)))
(loop for i below n
collect (aref a i n)))
(defun main ()
(let* ((n 3)
(a (make-array (list n (1+ n)))))
(loop for i below n do
(loop for j below (1+ n) do
(setf (aref a i j) (read))))
(destructuring-bind (x y z)
(gaussian-elimination n a)
(format t "~a ~a ~a~%" x y z))))
(main)Code language: Lisp (lisp)行列の各行が「一つの条件式」で、各列が「一つの未知数の係数」です。
行を足したり定数倍したりして未知数を消していく操作が、そのままコードになっています10。
3.7. 吐き出し法で逆行列を作る（inverse-matrix）
ガウス消去法で、組み合わせた行基本変形の組み合わせは、「逆行列」に相当します。
つまり、行列として考えると、
係数行列 A、未知数ベクトル v、右辺ベクトル bとして、A v = b を解いて、v = A^-1 bを作っているわけです。
ガウス消去法の行基本変形の合成 E は、A を単位行列 I に変形しています。
[A | b]
→ [E A | E b]
→ [I | A^-1 b]Code language: CSS (css)そのため、 A を単位行列 I に変形することは、左から A^-1 を掛けることに対応しています。
拡大行列では、同じ操作が右辺 b にも適用されます。
これによって、v = A^-1 bが得られます。
逆行列そのものを求めてから、未知数ベクトルを求めることもできます。
その場合は、「吐き出し」法で逆行列を求めるのが一般的です。
これは、swap-rows、scale-row、add-scaled-row を組み合わせた方法で、先ほどのガウス消去法の一般化した方法論と言えます。
(defun make-identity-matrix (n)
(let ((m (make-array (list n n) :initial-element 0)))
(loop for i below n do
(setf (aref m i i) 1))
m))
(defun inverse-matrix (n a)
;; A を I に変形しながら、右側の I を A^-1 に変形する
(let ((inv (make-identity-matrix n)))
(loop for col below n do
(let ((pivot-row (find-pivot-row a col n)))
(swap-rows a col pivot-row 0 n)
(swap-rows inv col pivot-row 0 n)
(let ((p (aref a col col)))
(scale-row a col (/ 1 p) 0 n)
(scale-row inv col (/ 1 p) 0 n))
(loop for row below n do
(unless (= row col)
(let ((factor (- (aref a row col))))
(add-scaled-row a row col factor 0 n)
(add-scaled-row inv row col factor 0 n))))))
inv))Code language: Lisp (lisp)なお、この `inverse-matrix` は引数 `a` を破壊的に変更します。
元の行列を残したい場合は、あらかじめコピーしてから渡します。
ちなみに、行列式の余因子展開から逆行列を作る、A^-1 = 1/det(A) * adj(A) 公式もあります。det(A) は行列式、adj(A) は余因子行列の転置です。
逆行列と右辺ベクトルをかけて、出てくる結果が答えということになります。
(defun multiply-matrix-vector (n a v)
(loop for i below n
collect
(loop for j below n
sum (* (aref a i j)
(aref v j)))))
(defun main ()
(let* ((n 3)
(a (make-array '(3 3)))
(b (make-array 3)))
(loop for i below n do
(loop for j below n do
(setf (aref a i j) (read)))
(setf (aref b i) (read)))
(let* ((inv (inverse-matrix n a))
(answer (multiply-matrix-vector n inv b)))
(format t "~{~a~^ ~}~%" answer))))
(main)Code language: Lisp (lisp)4. 用途3：グラフを行列で表して探索する（隣接行列）
4.1. グラフを行列で表す
グラフは点と辺の集まりで、「隣接行列」で表せます11。
点が4つ（0, 1, 2, 3）あり、
0から1、0から2、1から3、2から3 という辺がある場合
隣接行列 A:
0 1 2 3
0[ 0 1 1 0 ]
1[ 0 0 0 1 ]
2[ 0 0 0 1 ]
3[ 0 0 0 0 ]Code language: CSS (css)A[i][j] = 1 は「点 i から点 j へ1ステップで行ける」を意味します。
4.2. 行列積で多段の経路が出る
A × A = A^2 を計算すると、
A^2[i][j] = Σ_k A[i][k] × A[k][j]これは「点 i から点 k を経由して点 j へ行けるか」の合計です。A^2[i][j] は「2ステップで i から j へ行く経路の数」になり、同様に A^N[i][j] は「N ステップで i から j へ行く経路の数」になります12。
4.3. Lispでの実装
;; 隣接行列を作る
(defun make-adjacency-matrix (n edges)
(let ((mat (make-matrix n)))
(dolist (edge edges)
(setf (aref mat (first edge) (second edge)) 1))
mat))
;; N ステップで i から j へ行く経路数を求める
(defun count-paths (n edges steps)
(let* ((adj (make-adjacency-matrix n edges))
(powered (power-matrix n adj steps)))
powered))
(let* ((n 4)
(edges '((0 1) (0 2) (1 3) (2 3)))
(result (count-paths n edges 2)))
(format t "2ステップで0から3: ~a通り~%" (aref result 0 3))
; 0→1→3 と 0→2→3 の2通り
(format t "2ステップで0から1: ~a通り~%" (aref result 0 1)))
; 経路が存在しないので 0通りCode language: Lisp (lisp)4.4. 到達可能性の判定
「N ステップ以内に到達できるか」を見たいなら、A^0 + A^1 + ... + A^N の各成分が正かどうかを調べます。
BFSで十分な場合も多いですが、「ちょうど N ステップで到達する経路数」のような問題では行列累乗が使いやすいです。
競プロでは「有向グラフ上で K 回移動したときの到達先の個数」や、確率的な遷移を N 回繰り返したときの各状態の確率（マルコフ連鎖）などに応用されます。
5. 用途4：空間の変換を合成する（座標変換）
5.1. 回転・拡大・平行移動を行列で表す
2D の座標変換は行列で書けます。
点 (x, y) を変換する操作を見てみましょう。
拡大（x方向にa倍、y方向にb倍）:
| ax | | a 0 | | x |
| by | = | 0 b | × | y |
回転（角度θ）:
| x cosθ - y sinθ | | cosθ -sinθ | | x |
| x sinθ + y cosθ | = | sinθ cosθ | × | y |平行移動だけは 2×2行列 では表せません。
そこで「同次座標」と呼ばれる表現を使います。(x, y) を (x, y, 1) として3次元に拡張することで、平行移動も行列で書けるようになります13。
平行移動（dx, dy）:
| x + dx | | 1 0 dx | | x |
| y + dy | = | 0 1 dy | × | y |
| 1 | | 0 0 1 | | 1 |これで、回転・拡大・平行移動をすべて3×3行列で統一して扱えます。
5.2. 変換の合成が行列積になる
複数の変換を順番に適用したいとき、行列積で合成できます。
「回転してから平行移動する」変換:
M = 平行移動行列 × 回転行列点に何度も変換を適用する代わりに、先に変換を合成した行列 M を作っておけば、あとは点ごとに M を掛けるだけです。
10万点に50種類の変換を適用するなら、50個の行列を先に合成して1個にしてから、10万回掛けます14。
5.3. Lispでの実装
(defun make-2d-transform-matrix ()
(make-array '(3 3) :element-type 'double-float
:initial-element 0.0d0))
(defun identity-transform ()
(let ((m (make-2d-transform-matrix)))
(setf (aref m 0 0) 1.0d0
(aref m 1 1) 1.0d0
(aref m 2 2) 1.0d0)
m))
;; 平行移動行列
(defun translation-matrix (dx dy)
(let ((m (identity-transform)))
(setf (aref m 0 2) (coerce dx 'double-float)
(aref m 1 2) (coerce dy 'double-float))
m))
;; 回転行列（角度はラジアン）
(defun rotation-matrix (theta)
(let ((m (make-2d-transform-matrix))
(c (cos theta))
(s (sin theta)))
(setf (aref m 0 0) c (aref m 0 1) (- s)
(aref m 1 0) s (aref m 1 1) c
(aref m 2 2) 1.0d0)
m))
;; 拡大行列
(defun scale-matrix (sx sy)
(let ((m (make-2d-transform-matrix)))
(setf (aref m 0 0) (coerce sx 'double-float)
(aref m 1 1) (coerce sy 'double-float)
(aref m 2 2) 1.0d0)
m))
;; 3×3 行列積（浮動小数点版）
(defun multiply-3x3 (a b)
(let ((result (make-2d-transform-matrix)))
(loop for i below 3 do
(loop for j below 3 do
(setf (aref result i j)
(loop for k below 3
sum (* (aref a i k) (aref b k j))))))
result))
;; 点に変換を適用する
(defun apply-transform (m x y)
(let ((xf (+ (* (aref m 0 0) x) (* (aref m 0 1) y) (aref m 0 2)))
(yf (+ (* (aref m 1 0) x) (* (aref m 1 1) y) (aref m 1 2))))
(values xf yf)))
;; 「90度回転してから(3,5)平行移動」を合成
(let* ((rot (rotation-matrix (/ pi 2)))
(trans (translation-matrix 3 5))
(combined (multiply-3x3 trans rot)))
(multiple-value-bind (x y) (apply-transform combined 1.0d0 0.0d0)
(format t "変換後: (~,2f, ~,2f)~%" x y)))
; (1,0) を90度回転すると (0,1)、そこに(3,5)移動で (3, 6)Code language: Lisp (lisp)ゲームエンジンや3Dグラフィックスでは、モデルの変換・カメラの変換・投影変換をそれぞれ行列で表して、最終的に一つの行列に合成してからGPUに送ります15。
変換を先に合成できることが、行列を使う実用上の理由になっています。
6. 行列という道具の正体
四つの用途を振り返ると、共通する形が見えてきます。
- 行列累乗では、状態ベクトルが今の状態で、行列が変換規則でした。
- ガウス消去法では、係数の行が一つの条件式で、行操作が「条件を組み合わせて未知数を消す操作」でした。
- 隣接行列では、各成分が点間のつながりで、行列積が「中継点を経由した到達可能性の合成」でした。
- 座標変換では、行列が変換規則そのもので、行列積が「変換の合成」でした。
どれも「複数の量の関係を表にして、まとめて操作する」という形です。
教科書で行列がわかりにくかったのは、「何の関係を表しているか」が見えない状態で計算ルールだけを先に教わったからだと思います。
行列を見たとき「これは何の係数の表か」「何の変換規則か」「何のつながりか」を問えれば、あの妙に見えた掛け算のルールも必然に変わります16。
行列積の `ae+bg` は、単なる妙な計算パズルではありません。
「A の1行目が作る量」に対して、「B の1列目が持つ影響」をすべて足し合わせているのです。
大事なのは、最初から行列があることではありません。
複数の量のあいだにある関係を、行列として作れることです。
状態の遷移、連立方程式の係数、グラフのつながり、座標変換は、どれも「量と量の関係」を行列として表せます。
いったん関係を行列にできれば、あとは行列積・行列累乗・逆行列・行基本変形といった共通の道具で扱えます。
- 競技プログラミングとは、与えられた問題をプログラムで解く速さや正確さを競うコンテスト形式の活動です。日本ではAtCoderが代表的なプラットフォームで、毎週コンテストが開催されています。 – AtCoder
- フィボナッチ数列の名前は、13世紀イタリアの数学者レオナルド・フィボナッチに由来します。兎の繁殖を題材にした数学書『算盤の書』（Liber Abaci、1202年）でこの数列が紹介されました。 – Fibonacci sequence – Wikipedia
- 素朴な再帰の計算量は O(2^N) になります。F(n) を計算するとき F(n-1) と F(n-2) をそれぞれ再帰的に計算するため、呼び出し回数が倍々に増えます。メモ化再帰（一度計算した値を記録して再利用する手法）を使えば O(N) に落とせます。 – 行列累乗まとめ（競プロ）- Zenn
- 二分累乗は「繰り返し二乗法」や「ダブリング」とも呼ばれます。N を2進数で表したとき、各ビットが1であるものだけを掛け合わせることで、log2(N) 回の行列積で Mat^N を計算できます。 – 行列累乗まとめ（競プロ）- Zenn
- 行列積1回の計算量は O(状態数^3) です。状態数が大きいと行列累乗がかえって遅くなるため、「状態数が小さく N が大きい」という条件が揃う問題に特に有効です。 – 行列累乗まとめ（競プロ）- Zenn
- ケイリーの論文「A Memoir on the Theory of Matrices」は1858年に英国王立協会の Philosophical Transactions に掲載されました。この論文で単位行列・行列の加法・乗法・逆行列・行列の累乗が導入され、行列が独立した数学的対象として確立されました。 – A Memoir on the Theory of Matrices – Royal Society
- 『九章算術』の制作年代は紀元前1世紀から紀元後2世紀とされています。著者は不明ですが、前漢の張蒼や耿寿昌が加筆したとされ、263年に魏の劉徽が注釈本を制作しました。246個の問題を収めた問題集形式の数学書で、第8章「方程」に連立方程式の解法が収録されています。 – 九章算術 – Wikipedia
- ガウスの消去法（Gaussian elimination）は、係数行列に対して前進消去と後退代入の2ステップで連立一次方程式を解くアルゴリズムです。同様のアルゴリズムは前漢の九章算術で初めて記述されたとされています。 – ガウスの消去法 – Wikipedia
- 拡大係数行列とは、連立方程式の係数行列に右辺の定数列を付け加えたものです。この行列に対して行操作（行の交換・定数倍・加減算）を行うことで、方程式を解けます。 – 掃き出し法（ガウスの消去法）による連立方程式の解法 – 高校数学の美しい物語
- コード中のピボット選択（部分選択法）は数値的安定性のために行います。対象の列で絶対値が最大の行を先頭に持ってくることで、小さい数で割ることによる誤差を抑えます。 – ガウスの消去法 – Wikipedia
- グラフのデータ構造には隣接行列と隣接リストの2種類があります。隣接行列はメモリ使用量が O(頂点数^2) になりますが、2点間の辺の有無を O(1) で確認できます。隣接リストはメモリ効率が良い反面、辺の有無確認に O(次数) かかります。 – 隣接行列・隣接リスト – Qiita
- この性質を利用すると「有向グラフ上でちょうどK回移動したときの到達先の個数」や「確率的な遷移をN回繰り返したときの各状態の確率（マルコフ連鎖）」なども行列累乗で求められます。 – 行列累乗 カテゴリー – けんちょんの競プロ精進記録
- 同次座標（homogeneous coordinates）は、回転・平行移動・拡大縮小・射影などの変換を一つの行列で統一的に扱うための表現方法です。コンピュータビジョンや3DCGで標準的に使われており、OpenGLやWebGLでも座標は4次元の同次座標ベクトルで表現されます。 – 同次座標系 – CVMLエキスパートガイド
- 行列を掛ける順番に注意が必要です。「拡大してから回転して、次に平行移動する」変換は M = 平行移動行列 × 回転行列 × 拡大行列 と右から左の順に掛けます。順番を変えると結果が異なります。 – チュートリアル3：行列 – opengl-tutorial.org
- OpenGLではモデル変換・ビュー変換・投影変換の3種類の行列を扱います。それぞれを別々に計算してから合成することで、頂点ごとに一度の行列積で最終的な画面座標に変換できます。 – チュートリアル3：行列 – opengl-tutorial.org
- 行列の掛け算が「妙な順番」に見えるのは、変換の合成を正しく機能させるための計算順序だからです。行列積 AB は「Bの変換をしてからAの変換をする」合成変換を表しています。 – 行列 – Wikipedia