線形方程式・rank

概要

制約を体上の連立一次方程式へ写し、ガウスの消去法(Gaussian elimination)でrank・可解性・解空間の自由度を求める。独立な式を残すと、自由に選ぶ変数と、それに従って決まる変数が分かれる。

考え方

二つの式でピボットと自由変数を追う

親単元の小例を使う。未知数 x1,x2,x3x_1,x_2,x_3 は0か1で、条件は

x1⊕x2=1,x2⊕x3=0\begin{aligned} x_1\oplus x_2&=1,\\ x_2\oplus x_3&=0 \end{aligned}

である。⊕\oplus はXORを表す。0と1を要素とする体 F2\mathbb F_2 では、加算も減算もXORであり、唯一の非零元1の逆元は1である。

各式の係数を一行に並べ、右辺も末尾に付けたものを拡大行列と呼ぶ。縦線の左に x1,x2,x3x_1,x_2,x_3 の係数、右に定数を書くと、

[110∣1011∣0]\left[\begin{array}{ccccc} 1&1&0&\mid&1\\ 0&1&1&\mid&0 \end{array}\right]

となる。一行目の x1x_1 の係数1を、消去の基準になるピボットに選ぶ。二行目はその列が既に0なので変える必要はない。次に二行目の x2x_2 の係数1をピボットにし、一行目へ二行目を右辺ごとXORする。

[101∣1011∣0]\left[\begin{array}{ccccc} 1&0&1&\mid&1\\ 0&1&1&\mid&0 \end{array}\right]

この操作は、一行目を x1⊕x3=1x_1\oplus x_3=1 に置き換えたことに対応する。同じ二行目をもう一度XORすれば元へ戻るので、解集合を変えていない。

ピボット列は x1,x2x_1,x_2 の二つで、係数行列のrankは2になる。x3x_3 を決める新しい行は残っていないので、x3x_3 が自由変数である。残った二行は

x1=1⊕x3,x2=x3x_1=1\oplus x_3,\qquad x_2=x_3

と読める。x3=t∈F2x_3=t\in\mathbb F_2 と自由に選べば、他の二変数が一意に決まる。

特解とkernelから全解を表す

自由変数を0にすると、元の式の特解 (1,0,0)(1,0,0) が得られる。次に右辺を両方0へ置き換えた同次方程式を考える。右辺0のまま同じ行操作を行うと x1=x3, x2=x3x_1=x_3,\ x_2=x_3 となるため、その全解は (0,0,0)(0,0,0) と (1,1,1)(1,1,1) である。この集合が係数行列の kernel(核) で、非零ベクトル (1,1,1)(1,1,1) 一つが基底になる。

特解へkernelのベクトルを足しても、左辺の値は変わらない。逆に、元の二つの解の差は同次方程式を満たす。したがって、元の全解はちょうど「特解+kernel」であり、この例では成分ごとのXORで

(x1,x2,x3)=(1,0,0)⊕t(1,1,1)(t∈{0,1})(x_1,x_2,x_3)=(1,0,0)\oplus t(1,1,1) \qquad(t\in\{0,1\})

と書ける。具体的には t=0t=0 で (1,0,0)(1,0,0)、t=1t=1 で (0,1,1)(0,1,1) となり、解は 23−2=22^{3-2}=2 通りである。自由度は1であって、三変数を別々に選べるわけではない。一般にも、特解から部分空間を平行移動した解集合をアフィン空間と呼ぶ。右辺が非零なら、全解そのものが原点を含む部分空間になるとは限らない。

条件を追加すると、自由度が残っていても矛盾する

ここへ x1⊕x3=0x_1\oplus x_3=0 を追加する。係数だけを見ると、追加行 (1,0,1)(1,0,1) は元の二行のXORである。しかし、元の二式をXORした右辺は1なので、新しい右辺0とは一致しない。

消去後の一行目は [1,0,1∣1][1,0,1\mid1] だった。追加行 [1,0,1∣0][1,0,1\mid0] へこれをXORすると、次の行が残る。

[000∣1]\left[\begin{array}{ccccc} 0&0&0&\mid&1 \end{array}\right]

これは 0=10=1 を要求する矛盾行で、解は一つもない。係数行列のrankは2のままで、同次方程式のkernelにも自由度1が残るが、元の方程式の解数を 23−22^{3-2} と数えてはいけない。可解性を確認して初めて自由度から解数を求められる。追加条件の右辺も1なら零行 0=00=0 になり、元の二解を保つ。

一般の行列でも同じ操作で解を戻す

係数行列を r×cr\times c の AA、右辺ベクトルを bb、未知ベクトルを xx とし、Ax=bAx=b を解く。ここでは行・列番号を0始まりとする。拡大行列 [A∣b][A\mid b] を作り、確定したピボット行数を p=0p=0 として、列 j=0,…,c−1j=0,\ldots,c-1 を順に調べる。

  1. 行 pp 以降に Ai,j≠0A_{i,j}\ne0 の行を探す。なければ、この列の変数は自由変数として次の列へ進む。
  2. 見つかった行 ii と行 pp を交換する。行 pp 全体をピボットの逆元倍して、Ap,j=1A_{p,j}=1 にする。
  3. 他の各行 kk から、Ak,jA_{k,j} 倍した行 pp を右辺も含めて引き、その列を0にする。
  4. 行 pp に対応するピボット列 jj を記録し、pp を1増やす。

行の交換、非零倍、他の行の倍数の加減は全て可逆であり、解集合を保つ。各ピボット列は対応行だけが1となり、残りの未確定行では処理済みの列が全て0になる。従って得られた非零の係数行は独立で、最後の pp が係数行列のrankである。

係数が全て0で右辺だけ非零の行があれば解なし。それ以外では、自由列の集合を FF とし、各自由変数を任意に選べる。消去後の行 ii に対応するピボット列を jj とすると、その変数は

xj=bi−∑f∈FAi,fxfx_j=b_i-\sum_{f\in F}A_{i,f}x_f

で一意に戻る。小例のように全ての他行から消してあれば、右辺に他のピボット変数は残らない。下側の行だけを消す実装では、後ろのピボット行から後退代入し、既に求めた変数の寄与も引く必要がある。

自由変数を全て0にすれば特解を得る。kernelの基底は、右辺を0とし、自由変数を一つだけ1、他を0にして戻したベクトルを、自由列ごとに一本ずつ作る。各ベクトルの自由列部分は異なる単位ベクトルなので独立であり、任意の同次解はその自由変数の値を係数とした組合せで表せる。したがってkernelの次元は c−pc-p。解が存在するとき、全解は特解+kernelであり、要素数 qq の有限体 Fq\mathbb F_q 上なら qc−pq^{c-p} 通りとなる。

問題の構成へどうつなぐか

ABC366 G「XOR Neighbors」では、頂点に書く整数の各ビットについて隣接XOR条件が同次方程式になる。kernelの基底を求め、その各ベクトルを異なる出力ビットへ割り当てる。基底のどれにも1が現れない頂点は、どの同次解でも0なので非零整数を置けない。ここでは kernelの一ベクトルの座標が頂点、複数の基底をまとめる方向が整数のビットである。係数の演算は F2\mathbb F_2 上、最後の出力整数の組立てはビットの格納(bit packing)として区別する。

ABC276 Ex「Construct a Matrix」では、非零の積を2の個数の偶奇へ変え、二次元累積XORの四隅を未知数にする。この式には非零の右辺もあるので、矛盾を調べたうえで特解を一つ得ればよい。0を要求する積の条件は別に扱い、求めた特解からマスの値を復元する。小例の特解の復元が構成の一部となる接続である。

成立条件と計算量

体上では全ての非零元に逆元があるため、上の正規化と消去が使える。合成数を法とする剰余では非零ピボットも可逆とは限らず、この手順や解数の式をそのまま使えない。浮動小数点で実数の方程式を扱う場合は、ピボットの選択と誤差の扱いが別途必要になる。

r×cr\times c 行列の素朴な消去は、高々 min⁡(r,c)\min(r,c) 個のピボットで各 rr 行の O(c)O(c) 要素を更新するため、O(rcmin⁡(r,c))O(rc\min(r,c)) 回の体演算を使う。拡大行列の保存に O(r(c+1))O(r(c+1)) の空間を使う。消去後に特解を一本出すには O(c)O(c) 時間、kernelの基底を全て明示して保存するには、追加で O(c(c−rank⁡A))O(c(c-\operatorname{rank}A)) 時間・空間が必要になる。解集合全体を列挙しなくても、この基底で表せる。

F2\mathbb F_2 では行の加減算をビット列のXORでまとめられる。1語のビット数を ww とすると、右辺を含む一行のXORは O(⌈(c+1)/w⌉)O(\lceil(c+1)/w\rceil) かかる。ピボット探索・係数検査の費用もあるため、消去全体は

O(rc+rmin⁡(r,c)⌈c+1w⌉)O\left(rc+r\min(r,c)\left\lceil\frac{c+1}{w}\right\rceil\right)

と評価できる。有限体 Fq\mathbb F_q での解数 qc−rank⁡Aq^{c-\operatorname{rank}A} は、矛盾行がない場合の式である。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 青色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠