線形方程式・基底・分離可能変換へ変換する

概要

複数の条件を同時に満たす値を探す、与えられた値のXORで作れる値を調べる、配列全体に決まった変換をかける。この三つは線形代数で扱えるが、入力も求めるものも異なる。まず何を未知数とし、何を答えとして得たいかを分けよう。行列式による数え上げは別の単元で扱う。

考え方

制約を解くと、特解と動かせる方向が得られる

0か1の三つの未知数 x1,x2,x3x_1,x_2,x_3 に、次の条件を課してみる。

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を要素とし、加算・乗算を2で割った余りで行う体を F2\mathbb F_2 と呼ぶ。この体の加算はXORなので、上の条件は連立一次方程式になる。

独立な条件の数である rank(階数) は2で、三つの未知数に対して自由に選べる値が一つ残る。条件を満たす一つの解を特解と呼び、この例では (1,0,0)(1,0,0) を選べる。右辺を両方0にした方程式の解集合が kernel(核) であり、この例では (1,1,1)(1,1,1) 一つを基底に持つ。基底とは、その組合せで集合の全要素を一意に表せる独立なベクトルの組である。

特解にkernelの要素を成分ごとにXORすると元の条件を保つ。したがって、全解は

{(1,0,0), (0,1,1)}\{(1,0,0),\ (0,1,1)\}

となる。「一つ構成する」なら特解、「どれだけ動かせるか」ならkernel、「何通りか」なら自由度を使う。同じ消去結果でも、要求に応じて取り出すものが変わる。線形方程式・rankでは、この二式の行を実際に消去し、自由変数から両方の解を復元する。さらに条件を加えたとき、自由度が残っていても矛盾して解がなくなる場合を確かめる。

生成できる値と、値配列の変換を区別する

同じXORでも、ベクトルが入力として与えられ、その組合せでどの値を作れるかを聞かれることがある。一方、配列の各値が既知で、全体に線形変換をかけたい場合もある。次のように入力と欲しい結果を見比べると、進む子単元を選べる。

  • 制約を満たす未知数を求める。 上の二式から、解の有無・特解・kernelの基底を得たいなら、線形方程式・rankへ進む。
  • 与えられた値で作れる値を管理する。 入力が (1,1,0)(1,1,0) と (0,1,1)(0,1,1) なら、XORで作れる値は (0,0,0)(0,0,0)、(1,1,0)(1,1,0)、(0,1,1)(0,1,1)、(1,0,1)(1,0,1) の四つである。この集合を二本の基底で表す方法は、XOR線形基底で扱う。
  • 値配列全体を決まった規則で変換する。 添字を2ビットで表す4要素の配列 (1,2,3,4)(1,2,3,4) に、各ビット方向の和・差の変換をかけると (10,−2,−4,0)(10,-2,-4,0) を得る。こうした配列全体の計算を軸ごとの小変換で行う方法は、分離可能線形変換・Walsh–Hadamard変換で扱う。

二つ目の例の二本は、最初の連立方程式の係数行でもある。ただし、制約を解くときは「各行との積和が指定された右辺になる未知ベクトル」を探し、基底を持つときは「入力ベクトルを選んでXORした結果」を表す。係数行の生成する集合とkernelは別の空間である。

三つ目の例では配列の並びを添字 00,01,10,1100,01,10,11 の順とし、変換は整数の和・差で計算している。添字のビット演算と、配列の値の演算を混同しない。特にWalsh–Hadamard変換を逆に戻すには2で割れることが必要で、係数を F2\mathbb F_2 にすると和と差が同じになり、元へ戻せない。各軸の小変換へ分けられる条件と具体的な更新は子単元で扱う。

成立条件と計算量

線形方程式の消去では、計算する係数が体をなし、選んだ非零のピボット(消去の基準にする係数)に逆元があることを確認する。合成数を法とする剰余では、非零でも割れない係数がある。

一般体の密行列消去とビット列のXOR消去では演算費用が違う。行数を rr、列数を cc とすると、素朴な密行列消去は O(rcmin⁡(r,c))O(rc\min(r,c)) 回の体演算を使う。F2\mathbb F_2 の行はビット列としてまとめてXORできるが、複数語にまたがる行を定数時間とは数えない。XOR基底は値のビット長、分離可能変換は配列長と軸ごとの変換の大きさで費用を評価する。具体的な計算量は各子単元で確認する。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

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

関連問題

前提・学習成果・出典

導入対象の目安: 青色(1600–1999)。rank・基底・線形写像を制約と変換の共通言語として学ぶ入口。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-linear-algebra-xor

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 行列式による全域木・非交差pathの計数は行列式計数の単元で扱う。通常の多項式畳み込み・生成関数と、幾何の面積行列式も対象外とする。

根拠