行列式による数え上げ

概要

非交差経路やspanning treeなどの組合せ対象を行列式に対応させ、LGV補題・行列木定理で数える。

入力: 始点x_1<…<x_K、時刻Nの終点y_1<…<y_K。辺は位置を保つか1増やすので、M_ij=C(N,y_j−x_i)が単独経路数。範囲外の二項係数は0。

行列式を展開すると、始点iを終点π(i)へ結ぶ経路族にsgn(π)を掛けた総和となる。交差する族は最初の共通頂点と二経路を一定規則で選び、そこから後ろを交換する。これは積重みを保ち、置換の符号を反転する対合である。

打消し後に残るのは頂点非共有な族。一般のDAGでは複数の端点置換が残り得るため、行列式は常に非共有族の単なる総数になるわけではない。

この時間格子では、順序を逆転する二経路は同じ時刻・位置を必ず共有する。従って非共有族の端点対応は恒等置換のみで、その符号が正だからdet Mが求める数になる。

入力: 非空頂点集合Sの誘導グラフ。各非ループ辺uvの重みwをL_uu,L_vvへ+w、L_uv,L_vuへ−wとして足す。多重辺は重みを加算し、自己ループは除く。

根rの行と列を削った行列L^(r)の行列式が全域木の辺重み積の総和になる。接続行列BからL=BWB^Tと書き、Cauchy–Binetで辺集合へ展開すると、|S|−1辺の集合のうち木だけが小行列式の二乗1を持つためである。

無向木ではどの根を削っても同じ。|S|=1は空行列式1、非連結なら0。法上の掃き出しではpivot交換による符号を保ち、1集合O(|S|³)。

有向木へ転用する場合、根へ向かう木には出次数Laplacianを用いる。L_uuにuから出る非ループ重み和、L_uvに−w(u→v)を置く。BEST定理が必要とするのはこちらの向きである。

考え方

determinantの符号付き置換和を、木やpath族の組合せ対象へ対応させる。行列木定理はLaplace行列の余因子で全域木を数え、LGVは交差pathの相殺から非交差path族を取り出す。

成立条件と計算量

密行列のdeterminantは通常O(N³)。LGVで符号なしの個数になるには始終点の順序などの条件が必要。modが体でないとpivot除算を使えない。有向・無向でLaplace行列の向きと定義を合わせる。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。行列木定理やLGV補題の対応を理解し、組合せ対象を行列式で数える。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-determinant-counting

行列式による数え上げ

習得する技能

  • 辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。
  • DAG上の経路数行列を作り、交差する経路族の符号反転と端点対応の条件から、LGVで頂点非共有経路族を数えられる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 線形方程式・rank。

このUnitを直接前提とする単元: BEST定理によるEuler circuit数え上げ。

線形方程式・rankで得た考え方と実装を再利用し、行列式による数え上げの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 行列式による数え上げの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠