線形matroid交差の乱択rank判定

概要

二つの線形matroidの表現A₁,A₂からA₁diag(r)A₂ᵀを作り、有限体上の乱択rankを共通独立集合の最大sizeとして高確率で判定する。

考え方

二つの線形独立性条件を同時に満たす集合では、それぞれの列ベクトルを組み合わせた行列のrankを使う代数的な特徴付けがある。determinantの項が共通独立集合を表すことを示してから指紋評価を使う。

共通独立size kの列集合Sがあるなら、A₁のあるk行I、A₂のあるk行Jでdet A₁[I,S]とdet A₂[J,S]がともに非零となる。対応するintersection matrixのminorはCauchy–Binetにより Σ_{|T|=k} det A₁[I,T]·det A₂[J,T]·∏_{e∈T}r_e。Tごとに異なるsquare-free monomialなので、Sの非零係数が他項と相殺されず、このminorは非零多項式になる。

逆に共通独立size kが無ければ、全Tで少なくとも一方のdetが0だから全k-minorが恒等的に0。従って変数のままのrankが最大共通独立sizeに一致する。独立一様代入は恒等的0を非零にできず過大評価は起こらない。過小評価だけを非零最大minorの次数kと体サイズで界せる。

成立条件と計算量

行列の大きさに対する消去費用と、ランダム代入の多項式次数から誤判定率を評価する。rank一回だけで実際の最適集合まで復元できるとは限らない。一般のoracle matroid intersectionと前提を混同しない。

表現行列の列を同じ要素順に揃え、A₁ diag(r_e) A₂ᵀのrankを調べる。Cauchy–Binet展開で、共通独立なr列に対応するminorが非零多項式になる。体から独立一様に選んだr_eで真のrankを過小評価する確率は、そのminorの次数rに対して高々r/|F|。二表現の行数がr程度なら素朴な行列構築O(|E|r²)と消去O(r³)を合わせる。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 赤色(2800以上)。二つの線形表現から乱択行列を作り、rankと共通独立集合の大きさを対応させる。

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

概念上の親: Matroidの独立性・greedy・線形交差。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-linear-matroid-intersection

線形matroid交差の乱択rank判定

習得する技能

  • 二つの線形matroid表現から乱択intersection matrixを構成し、Schwartz–Zippelの誤り上界を示したうえでrankを最大共通独立sizeとして判定できる。

前提と範囲

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

直接の前提単元: 線形方程式・rank、matroid greedy、乱択の成功条件と誤り確率を設計する。

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

matroidの独立性・交換公理、線形方程式のrank計算、乱択誤り評価を学んだ後、二つの線形matroidの共通独立rankを一枚の乱択行列へ圧縮する。

このUnitでは扱わないもの

  • 線形matroid交差の乱択rank判定の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠