線形方程式・rank
概要
制約を体上の連立一次方程式へ写し、ガウスの消去法(Gaussian elimination)でrank・可解性・解空間の自由度を求める。独立な式を残すと、自由に選ぶ変数と、それに従って決まる変数が分かれる。
考え方
二つの式でピボットと自由変数を追う
親単元の小例を使う。未知数 は0か1で、条件は
である。 はXORを表す。0と1を要素とする体 では、加算も減算もXORであり、唯一の非零元1の逆元は1である。
各式の係数を一行に並べ、右辺も末尾に付けたものを拡大行列と呼ぶ。縦線の左に の係数、右に定数を書くと、
となる。一行目の の係数1を、消去の基準になるピボットに選ぶ。二行目はその列が既に0なので変える必要はない。次に二行目の の係数1をピボットにし、一行目へ二行目を右辺ごとXORする。
この操作は、一行目を に置き換えたことに対応する。同じ二行目をもう一度XORすれば元へ戻るので、解集合を変えていない。
ピボット列は の二つで、係数行列のrankは2になる。 を決める新しい行は残っていないので、 が自由変数である。残った二行は
と読める。 と自由に選べば、他の二変数が一意に決まる。
特解とkernelから全解を表す
自由変数を0にすると、元の式の特解 が得られる。次に右辺を両方0へ置き換えた同次方程式を考える。右辺0のまま同じ行操作を行うと となるため、その全解は と である。この集合が係数行列の kernel(核) で、非零ベクトル 一つが基底になる。
特解へkernelのベクトルを足しても、左辺の値は変わらない。逆に、元の二つの解の差は同次方程式を満たす。したがって、元の全解はちょうど「特解+kernel」であり、この例では成分ごとのXORで
と書ける。具体的には で 、 で となり、解は 通りである。自由度は1であって、三変数を別々に選べるわけではない。一般にも、特解から部分空間を平行移動した解集合をアフィン空間と呼ぶ。右辺が非零なら、全解そのものが原点を含む部分空間になるとは限らない。
条件を追加すると、自由度が残っていても矛盾する
ここへ を追加する。係数だけを見ると、追加行 は元の二行のXORである。しかし、元の二式をXORした右辺は1なので、新しい右辺0とは一致しない。
消去後の一行目は だった。追加行 へこれをXORすると、次の行が残る。
これは を要求する矛盾行で、解は一つもない。係数行列のrankは2のままで、同次方程式のkernelにも自由度1が残るが、元の方程式の解数を と数えてはいけない。可解性を確認して初めて自由度から解数を求められる。追加条件の右辺も1なら零行 になり、元の二解を保つ。
一般の行列でも同じ操作で解を戻す
係数行列を の 、右辺ベクトルを 、未知ベクトルを とし、 を解く。ここでは行・列番号を0始まりとする。拡大行列 を作り、確定したピボット行数を として、列 を順に調べる。
- 行 以降に の行を探す。なければ、この列の変数は自由変数として次の列へ進む。
- 見つかった行 と行 を交換する。行 全体をピボットの逆元倍して、 にする。
- 他の各行 から、 倍した行 を右辺も含めて引き、その列を0にする。
- 行 に対応するピボット列 を記録し、 を1増やす。
行の交換、非零倍、他の行の倍数の加減は全て可逆であり、解集合を保つ。各ピボット列は対応行だけが1となり、残りの未確定行では処理済みの列が全て0になる。従って得られた非零の係数行は独立で、最後の が係数行列のrankである。
係数が全て0で右辺だけ非零の行があれば解なし。それ以外では、自由列の集合を とし、各自由変数を任意に選べる。消去後の行 に対応するピボット列を とすると、その変数は
で一意に戻る。小例のように全ての他行から消してあれば、右辺に他のピボット変数は残らない。下側の行だけを消す実装では、後ろのピボット行から後退代入し、既に求めた変数の寄与も引く必要がある。
自由変数を全て0にすれば特解を得る。kernelの基底は、右辺を0とし、自由変数を一つだけ1、他を0にして戻したベクトルを、自由列ごとに一本ずつ作る。各ベクトルの自由列部分は異なる単位ベクトルなので独立であり、任意の同次解はその自由変数の値を係数とした組合せで表せる。したがってkernelの次元は 。解が存在するとき、全解は特解+kernelであり、要素数 の有限体 上なら 通りとなる。
問題の構成へどうつなぐか
ABC366 G「XOR Neighbors」では、頂点に書く整数の各ビットについて隣接XOR条件が同次方程式になる。kernelの基底を求め、その各ベクトルを異なる出力ビットへ割り当てる。基底のどれにも1が現れない頂点は、どの同次解でも0なので非零整数を置けない。ここでは kernelの一ベクトルの座標が頂点、複数の基底をまとめる方向が整数のビットである。係数の演算は 上、最後の出力整数の組立てはビットの格納(bit packing)として区別する。
ABC276 Ex「Construct a Matrix」では、非零の積を2の個数の偶奇へ変え、二次元累積XORの四隅を未知数にする。この式には非零の右辺もあるので、矛盾を調べたうえで特解を一つ得ればよい。0を要求する積の条件は別に扱い、求めた特解からマスの値を復元する。小例の特解の復元が構成の一部となる接続である。
成立条件と計算量
体上では全ての非零元に逆元があるため、上の正規化と消去が使える。合成数を法とする剰余では非零ピボットも可逆とは限らず、この手順や解数の式をそのまま使えない。浮動小数点で実数の方程式を扱う場合は、ピボットの選択と誤差の扱いが別途必要になる。
行列の素朴な消去は、高々 個のピボットで各 行の 要素を更新するため、 回の体演算を使う。拡大行列の保存に の空間を使う。消去後に特解を一本出すには 時間、kernelの基底を全て明示して保存するには、追加で 時間・空間が必要になる。解集合全体を列挙しなくても、この基底で表せる。
では行の加減算をビット列のXORでまとめられる。1語のビット数を とすると、右辺を含む一行のXORは かかる。ピボット探索・係数検査の費用もあるため、消去全体は
と評価できる。有限体 での解数 は、矛盾行がない場合の式である。
問題一覧
- ABC366 G「XOR Neighbors」 公式問題
技能・出典
主題: 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 線形方程式・rank / 補助タグ: bitsetによるword並列集合演算、構成解・witness復元
- ABC276 Ex「Construct a Matrix」 公式問題
技能・出典
主題: 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 線形方程式・rank / 補助タグ: bitsetによるword並列集合演算、構成解・witness復元、座標・値の順序保存圧縮、累積和・差分配列
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC299 Ex「Dice Sum Infinity」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 確率・期待値DP / 補助タグ: 線形遷移・行列累乗、線形方程式・rank、法上の四則演算・高速累乗・逆元
- ABC323 G「Inversion of Tree」 公式問題主題: 行列式による数え上げ
技能・出典
主題: 行列式による数え上げ(辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。)。既習技能: factorial convolutionによる多項式Taylor shift(二項係数を階乗で分離し、係数列の反転と一回の畳み込みから P(x+a) の全係数を準線形時間で復元できる。) / 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 行列式による数え上げ / 補助タグ: 線形方程式・rank、factorial convolutionによる多項式Taylor shift
- ABC399 G「Colorful Spanning Tree」 公式問題
技能・出典
主題: 線形matroid交差の乱択rank判定(二つの線形matroid表現から乱択intersection matrixを構成し、Schwartz–Zippelの誤り上界を示したうえでrankを最大共通独立sizeとして判定できる。)。既習技能: 乱択の成功条件と誤り確率を設計する(乱数で選ぶ対象と成功条件を定め、誤り確率を上から評価して必要な反復回数または決定的な事後検証を設計できる。) / 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 線形matroid交差の乱択rank判定 / 補助タグ: 線形方程式・rank、乱択・Monte Carloアルゴリズム
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。体上の消去法を実装し、rankから可解性と自由度を判断する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 線形方程式・基底・分離可能変換へ変換する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-linear-system-rank
線形方程式・rank
習得する技能
- 制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 行列式による数え上げ、線形matroid交差の乱択rank判定、一般グラフの最小重み完全matching。
制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- 線形方程式・rankの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。
根拠
- ABC366 G 公式問題文・公式解説 — 各ビットの同次方程式、kernelの基底による非零条件の判定と出力の構成。
- ABC276 H 公式解説
- ABC276 H 公式問題文
- ABC299 H 公式解説
- ABC299 H 公式問題文
- ABC323 G 公式解説
- ABC323 G 公式問題文