行列の定義と基本性質
行列（Matrix）は、数値を長方形の配列状に配置した構造体です。一般に \(m \times n\) の次元を持つ行列 \(A\) は、以下のように表されます。
\(m = n\) のとき、これを正方行列あるいは\((n)\) 次行列と呼びます。また、対角成分のみが 1 で他の要素が 0 となる行列を単位行列（Identity Matrix）\(I\) と記します。例えば 2 次の場合：
基本演算ルール
行列演算には加減算、スカラー倍、そして行列乗積があります。
- 加法・减法: 同じサイズの行列同士に対して、対応する位置の要素を計算します。
- スカラー倍: 各要素に定数を掛ける操作です。
- 乗積（Matrix Multiplication）: 行列 \(A\) (\(m \times n\)) と \(B\) (\(n \times p\)) の積 \(C\) (\(m \times p\)) を求めるときの公式は以下の通りです。
$$ C_{i,j} = \sum_{k=1}^{n} A_{i,k} \times B_{k,j} $$
この演算は結合則と分配則を満たしますが、交換則は一般的に成立しません。この性質により、べき乗に対する計算（快速累乗）が可能となります。
行列高速幂と実装
標準的な行列乗算は \(O(N^3)\) かかります。これを用いた \(A^K\) の計算は \(O(N^3 \log K)\) で実現可能です。以下はテンプレート的な実装例を示します。
#include <vector>
#include <iostream>
using namespace std;
const long long MOD = 1e9 + 7;
const int MAX_DIM = 105;
// 行列構造体の再定義
struct Matrix {
int size;
vector<vector<long long>> data;
Matrix(int n) : size(n), data(n, vector<long long>(n, 0)) {}
// 単位行列生成
static Matrix identity(int n) {
Matrix res(n);
for (int i = 0; i < n; ++i) res.data[i][i] = 1;
return res;
}
// 行列乗算演算子オーバーロード
Matrix operator*(const Matrix& other) const {
Matrix result(size);
for (int i = 0; i < size; ++i) {
for (int k = 0; k < size; ++k) {
if (data[i][k] == 0) continue; // 最適化：ゼロ除外
for (int j = 0; j < size; ++j) {
result.data[i][j] = (result.data[i][j] + data[i][k] * other.data[k][j]) % MOD;
}
}
}
return result;
}
// 高速幂計算
Matrix power(long long exp) const {
Matrix res = identity(size);
Matrix base = *this;
while (exp > 0) {
if (exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
return res;
}
};ここで注意すべき点は、任意の正則な行列 \(A\) について \(A^0 = I\) が成り立つことです。
動的計画法の転化
線形漸化式で表される数列の計算において、行列の応用は特に強力です。
フィボナッチ数列の高速化
通常の DP は \(O(N)\) ですが、行列表現を使うことで \(O(\log N)\) に短縮できます。
漸化式 \(F_i = F_{i-1} + F_{i-2}\) を行列形式に変換します：
$$ \begin{bmatrix} F_{i} \\ F_{i+1} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{i-1} \\ F_{i} \end{bmatrix} $$
これを繰り返せば、初期状態からの累積を計算するために行列べき乗が使用できます。
Matrix fib_matrix(int n) {
Matrix T(2);
T.data[0][1] = 1;
T.data[1][0] = 1;
T.data[1][1] = 1;
Matrix res = T.power(n - 1);
// 初期ベクトル [1, 1] に対応させると n-1 回の遷移後に得られる
long long ans = res.data[0][0];
return ans;
}グラフ理論との親和性
行列表現は最短経路問題とも深く関連しています。従来の Floyd-Warshall アルゴリズムの考え方を行列乗算に応用し、「至れらなる最小重み」の演算（$(\min, +)$ 半環）として扱うことができます。
固定歩数の最短経路
例えば「ちょうど L 歩移動した場合の最短距離」といった問題を解く際、隣接行列を基底とした $(\min, +)$ 乗算を行うことで解決可能です。
// 最短行列乗算 (min-plus algebra)
struct MinMatrix {
// ... コンストラクタ省略 ...
MinMatrix operator*(const MinMatrix& rhs) const {
MinMatrix ret(size);
// 初期値は無限大
fill(ret.data.begin(), ret.data.end(), INF);
for(int i=0; i<size; ++i){
for(int k=0; k<size; ++k){
for(int j=0; j<size; ++j){
ret.data[i][j] = min(ret.data[i][j], dist[i][k] + dist[k][j]);
}
}
}
return ret;
}
// ... 省略 ...
};この手法は、辺数が多いグラフや、特定の手数制限付き移動問題などに応用されます。また、複数のクエリがある場合、一旦前処理でべき乗を計算しておき、その後クエリごとにベクトルとの乗算（\(O(N^2)\)）を行うことで効率化を図れます。
行列式の計算と性質
行列式 \(\det(A)\) は、正方行列のスカラー不変量であり、逆行列の存在判定や体積比などに利用されます。定義は以下の通りです。
ガウス消去法による計算
素数法での計算では、ガウス消去法によって上三角行列に変形し、対角成分の積をとります。ただし、割り算が必要ないよう剰余逆元を使うか、または拡張ユークリッド法に基づく「行列の除法なしガウス消去」（GCD 版）を使用します。
long long determinant(Matrix& M) {
long long det = 1;
int n = M.size;
for(int i=0; i<n; ++i){
int pivot = i;
while(pivot < n && M[i][pivot] == 0) pivot++;
if(M[i][pivot] == 0) return 0; // 0 になる
if(pivot != i) {
swap(M.row(i), M.row(pivot));
det = (mod - det) % mod;
}
// 現在のピボットを使って下から消す
long long inv = pow_mod(M[i][i], mod-2);
for(int j=i+1; j<n; ++j){
if(M[j][i] != 0){
long long factor = M[j][i] * inv % mod;
for(int k=i; k<n; ++k){
M[j][k] = (M[j][k] - factor * M[i][k]) % mod;
}
}
}
det = det * M[i][i] % mod;
}
return (det + mod) % mod;
}非素数体の場合は、逆元が存在しないため、gcd を用いて互いに打ち消すようにして行列を消去していく必要があります。
LGV 定理
Lindström–Gessel–Viennot（LGV）定理は、有向無閉路グラフ（DAG）において、開始点集合から終了点集合への「非交差経路組」の総数を求めるための強力なツールです。
特定の点間のパスの総数を表す行列の行列式を取ることで、条件を満たさない組み合わせが相殺され、望みの結果が得られます。