このページではミニチュア1をM1のように略記する。
M1とM2はフィボナッチ数列を扱う.M1では,フィボナッチ数列の第n項を約log n回の演算で
計算する方法を紹介する.これは,行列のかけ算をうまく扱うことで得られる.
M2では,フィボナッチ数列の一般項の表示を与える.結果はよく知られたものだが,
ここでは数列のなすベクトル空間に二種類の基底を見つけるという方法が紹介される.
M3とM4では極値集合論の典型的な不等式を扱う.
M3では,二元体が自然に登場して活躍するのだが,これによって奇数街のクラブ問題を線形代数的に解決する.
M4では,古典的なFisherの不等式をやはり
行列の階数の議論を通して証明する.
問題の組合せ構造を反映する行列が正則であることを示すのに,行列の正値性を利用している.
M5は誤り訂正符号の紹介である.ハミング符号を例に,生成行列と符号化,パリティチェック行列
と復号化などが説明され,二元体上のベクトル空間の基底や連立方程式の解空間が,線形符号から
意味づけられる.
M6とM7は離散幾何からの話題を扱う.M6では「平面上の四点で,どの二点間の距離も奇数の
ものはない」という定理を,距離情報を与える行列の階数を調べることで証明する.
M7は距離に関する三角不等式の高次元版を扱う.実対称行列が直交行列で対角化できること
から出発して,「与えられた距離をもつR^n(n次元ユークリッド空間)内のn+1点の存在は,
距離情報から得られる行列の半正定値性と同値である」ことが証明される.
M8はグラフのパッキングの話題から,n点完全グラフをm個の完全二部グラフに分割する
問題を扱う.m=n-1個に分割するのは簡単だが,m=n-2個には分割できない
ことを示すところが面白い.
ここでは問題を隣接行列の言葉に翻訳し,階数の議論に持ち込んでいる.
M9は再び,離散幾何の話題.「R^3の等角直線(どの二直線間の角度も等しい直線)は
最大6本であり,R^dでは(d+1)/2本を超える等角直線はとれない」ことを
示す.等角直線から作られる行列たちが,d次実対称行列のつくるベクトル空間内で
線形独立になることを使う.
M10とM11はアルゴリズムを扱う.M10では与えられたグラフから三角形を検出するには,
隣接行列の自乗を調べればよいことを示す.これは行列の積を高速に計算する動機を
与え,その計算量についても言及される.M11では,大きな二つの行列の積の計算結果が
与えられたとき,それが正しいかどうかを,積を計算せずに,高精度,
高速に確かめる方法――いわゆる確率的検証――が紹介される.
M12では,分割に関するDehnの結果のひとつ「縦横の比が無理数の長方形は,有限個の
正方形に分割できない」ことを示す.証明においてはRがQ上のベクトル空間であることが
本質的な役割を果たす.
M13とM14はスペクトルグラフ理論(隣接行列の固有値を扱うグラフの話)の紹介である.
M13では10点完全グラフを3個のペテルセングラフに分割できないことを,隣接行列の
固有値と重複度を利用して示す.M14では,内周5で最小次数r≧3, 頂点数r^2+1
のグラフが存在するならr=3 (ペテルセングラフ),r=7 (Hoffman-Singletonグラフ),
r=57 (これは未発見)の可能性しかないことが証明される.
M15とM16の証明の舞台は多項式の作るベクトル空間で,その次元や線形結合の様子を調べる.
これにより,M15ではR^dにおける二距離集合(二点間の距離が与えられた二種類の値だけを
とる集合)の上界を与える.M16では,R^dのd次元立方体について,指定された頂点は避け,
それ以外の2^d-1個の頂点をすべて覆うにはd枚の超平面が必要なことを示す.
M17では極値集合論における線形代数手法の典型例として,交差サイズをひとつだけ禁止すると
集合族のサイズがたちまち小さくなるというFrankl-Wilsonの定理を証明する.
M18ではこの定理を応用したKahn-Kalaiの構成を紹介する.
これは,R^d内の直径1の集合をd+1個に分割して,各部分の直径を1より
小さくできるか,というBorsukの問いに否定的な答を与える.
M19とM20では連立方程式の解空間の次元が証明の鍵となる.M19では,ディスクレパンシー理論
の例として,Beck-Fialaの定理をとりあげる.M20では,ある条件をみたすR^dのベクトルたち
が与えられたとき,それらをうまく並べかえると先頭から途中までの和がよい性質を
みたすというSteinitzの補題を扱う.
M21は行列と木の定理(Matrix-tree theorem)を扱う.
これはグラフの全域木の個数をラプラス行列の行列式で表示するもので,
有名な結果だが,ここでの証明はまだあまり有名ではないもの(Gessel-Viennotの補題を
ふまえたもの)が採用されている.
M22の話題は,二部グラフの完全マッチングの数え上げだ.これは隣接行列の
パーマネントの計算と同じで,計算量的に難しいとされている(#P完全).しかし
平面グラフの場合には,Kasteleyn符号化なる操作で別の行列の行列式の計算に帰着
でき,全体を多項式時間で実行できることを示す.
M23では,ある条件をみたす整数分割の個数が単峰であることを証明する.これはCayleyが
明らかだと主張し,Sylvesterによって証明された結果だ.ここでは冪集合の
包含行列の階数に関するGottliebの定理を用いる証明が紹介される.
M24からM27は,多項式の零点の個数に関するSchwartz-Zippelの定理の応用が紹介される.
M24では,与えられた二部グラフに完全マッチングがあるかどうかを調べる.
この検査を行列式が非零かどうかの計算に帰着させ,
その計算を多項式時間で行う確率的アルゴリズムを与える.
M25では,掛谷の針の問題からはじめて,掛谷集合に関する(未解決の)掛谷予想と,
ごく最近証明された掛谷予想の有限体版を紹介する.
M26では,n文字置換の集合Pに対して,Pの二つの置換の合成が全部でいくつあるかを
高速に数える確率的アルゴリズムを示し,
M27では,有限集合上に二項演算が与えられたとき,それが結合則をみたすかどうかを
高速に判定する確率的アルゴリズムを構成する.
M28とM29はグラフGのShannon容量を扱う.M28ではShannon容量を定義した後,
グラフの直交表現を用いて長さ5のサイクルのShannon容量が√5であることを証明する(Lovaszに
よるもの).
またShannon容量と独立数との関係,その計算量についても言及される.
M29ではG+HのShannon容量がGのShannon容量とHのShannon容量の和より大きいような
グラフG,Hの存在を示す(Alonによるもの).
証明には異なる体におけるグラフの関数表現を用いる.
M30では,R^dのエル1距離に関する等距離集合(どの二点間の距離も等しい集合)の
サイズに多項式上界O(d^4)を与える.証明では,まずエル1の等距離集合を
ユークリッド距離の近似的等距離集合に埋め込み,そのサイズの上界を,距離情報から
得られる実対称行列の階数の下界から得ている.
M31はグラフの最疎切断を扱う.これは応用上,重要であるが,計算量的には難しい(NP困難).
ここではラプラス行列の第二固有値を利用するCheeger-Alon-Milman不等式を示し,
高速な近似アルゴリズムを提示する.
M32では,Knasterの問題の反例として,「nが大きいとき,
R^nの単位球面上のn点集合Kで,
原点周りのどんな回転ρに対しても,ρKの点のエル∞ノルムが
一定値にならないものがある」ことを示す.実際に,ρKの半数のノルムは
4/√nより大,残りのノルムはこれより小,というKを構成する.
M33は極値集合論の交差集合族に関する結果(非対称なBollobasの定理)を扱う.
ここでは外積代数を手早く導入し,それを使った鮮やかな証明が紹介される.
同種の結果には代数的でない証明が可能な場合も少なくないが,
この結果には線形代数的な証明法しか知られておらず,
この手法の強力さを示す好例といえよう.
戻る