遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

ぱらぱらめくる『線形代数と数え上げ』

パラパラめくるシリーズ 線形代数 数え上げ カステレイン行列
  • カステレイン行列と数え上げのことが気になった
  • その両方が含まれている本書を買って眺めてみる

線形代数と数え上げ［増補版］ [ 高崎 金久 ]

線形代数と数え上げ［増補版］ [ 高崎 金久 ]

  • この本の扱うトピックの英語版としては、Mishigan State Univ. がPDFをアップロードしていて(

[https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf:title=Combinatorics:
The Art of Counting] by Bruce E. Sagan、その書籍版が

Combinatorics: The Art of Counting (Graduate Studies in Mathematics)

Combinatorics: The Art of Counting (Graduate Studies in Mathematics)

Amazon

前書き

  • 「行列と木の定理』
    • 「可能な全域木の総数はグラフのラプラシアンと呼ばれる行列の余因子として表せる。また、この行列の固有値を用いて全域木の個数を表す定式化もある」
  • カステレインの定理
    • 「グラフが平面的ならば、可能な完全マッチングの総数はある反対称行列の「パフ式」の絶対値として表せる」
    • 「パフ式は行列式の平方根であり、グラフがもう少し特殊なもの(２部グラフ)ならば、パフ式の代わりに行列式をを用いることもできる」
  • 非交差経路和に対するLGV(Lindstrom-Gessel-Viennot)公式
    • 「平面分割、あるいは３次元ヤング図形の数え上げ問題はLGV公式の格好な応用例」
    • 「シューア函数に対するヤコビ-トゥルーディ公式、ジャンベリ公式などの行列式表示もLGV公式によって説明できる」

増補版まえがき

  • フック公式
    • 「フック公式は一般線形群や対称群の規約表現の次元をヤング図形のフックの言葉で記述する公式」
    • 「これらの次元の値は半標準盤や標準盤の個数に等しく、シューア函数の特出として求めることができる」
  • 「フック公式が成り立つからくりはヤング図形とマヤ図形の相互関係によって説明できる」
  • この本の続編が『線形代数とネットワーク』

線形代数とネットワーク [ 高崎金久 ]

線形代数とネットワーク [ 高崎金久 ]

第１部　３次元ヤング図形の数え上げ

第１章　平面分割と非交差経路

  • LGV公式が本書全体の中心
  • LGV公式の行列式を計算する過程でシューア函数が登場する
  • シューア函数は多変数対称多項式の古典的な例。表現論・可積分系・パンルヴェ方程式などとも関係が深い
  • ３次元ヤング図形は、単位立方体を原点詰めで第一象限に積むパターンで、それは、行列の左上を原点と見た平面格子と考えたときに非負整数要素で大小制約のある行列として表現できる。この行列では、同じ整数を持った領域を区画と考えると、一種の平面分割になるので、３次元ヤング図形は平面分割を表しているとも見える
  • これをさらに、非交差経路のセットとみることもできる
  • LGV公式は、この非交差経路の場合の数にきれいな式表現(行列式を使う)を与える
  • LGV公式が言っているのは
    • 閉路の存在しない有向グラフに、適合条件(始点が２つと終点が２つ、あったときに、２つの経路に交叉がなかったとすると、終点を入れ替えると交叉のない２経路は作れない。。。平面化グラフのこと？)があったら、始点集合と終点集合とを結ぶ非交差経路セットの総数は、始点-終点の個々のペアの経路数を要素G_{i,j} = _{r+s}C_{r+i-j}とした行列の行列式になる。どうしてこんな仕組みになっているかというと、行列式は、集合のﾄﾞ・モルガンの定理、inclusion-exclusionルールの計算式になっているから
  • これを使うと、正の整数 r,s,tでできた直方体と合致する３次元ヤング図形の場合の数の数え上げがN_{r,s,t} = \text{det} \begin{pmatrix} _{r+s}C_{r+i-j} \end{pmatrix}_{i,j=1}^t
  • さらに、シューア函数(対称性函数)を用いることでN_{r,s,t} = \prod_{i=1}^r \prod_{j=1}^s \prod_{k=1}^t \frac{i+j+k-1}{i+j+k-2}と単純な式になる
my.macmahon <- function(r,s,t){
	ret <- 1
	for(i in 1:r){
		for(j in 1:s){
			for(k in 1:t){
				ret <- ret * (i+j+k-1)/(i+j+k-2)
			}
		}
	}
	return(ret)
}

r <- 1
s <- 1
t <- 1

my.macmahon(r,s,t)

# １次元
rs <- 1:100
v <- rep(0,length(rs))
for(i in 1:length(rs)){
	v[i] <- my.macmahon(rs[i],s,t)
}

plot(rs,v)

# ２次元
n <- 9
rs <- 1:n
ss <- n
rss <- expand.grid(rs,ss)
v <- rep(0,length(rss[,1]))
for(i in 1:length(v)){
	v[i] <- my.macmahon(rss[i,1],rss[i,2],t)
}

plot(rs,v)

第２章　LGV公式

  • LGV公式が言っているのは
    • 閉路の存在しない有向グラフに、適合条件(始点が２つと終点が２つ、あったときに、２つの経路に交叉がなかったとすると、終点を入れ替えると交叉のない２経路は作れない。。。平面化グラフのこと？)があったら、始点集合と終点集合とを結ぶ非交差経路セットの総数は、始点-終点の個々のペアの経路数を要素G_{i,j} = _{r+s}C_{r+i-j}とした行列の行列式になる。どうしてこんな仕組みになっているかというと、行列式は、集合のﾄﾞ・モルガンの定理、inclusion-exclusionルールの計算式になっているから

第３章　平面分割とシューア函数

  • LGV公式により、非交差経路の組の場合の数が行列式で表せることとなった
  • この行列式を函数に格上げして、その対称性に留意するとシューア函数を使うことができるようになる
  • 対称性が存在することは非交差経路セットが３次元ヤング図形と対応することから、幾何学的に感じ取ることもできる
  • ヤング版を３次元対象物と観ることもできるが、(k,k,k)を視点として原点を見下ろして２次元の絵にすると、立方体の面(正方形)がひし形として描かれる。正方形の法線方向を考えると、３次元空間で平行光線を当てると日向と日陰に分けられる。そのような見方をすることもできる。そこにも幾何学的対称性を認めることができる

第４章　ヤコビ-トゥルーディ公式

  • 分割を一般化してヤコビ-トゥルーディ公式が導かれる
  • 「一般のヤング図形に対するシューア函数を非交差経路和として解釈し、LGV公式によってヤコビ-トゥルーディ公式を導出」

第５章　非交差経路とフェルミオン

第６章　ワイルの指標公式

  • 「表現論の観点では、シューア函数は一般線形群のある既約表現の指標であり、ワイルの指標公式はそれを行列式の比として表すもの」
  • ワイルの指標公式は、行列式の比(割り算)の形をしている
  • リー群・リー環とかの話

第７章　マクマホンの公式

  • マクマホンの公式は整数の式。それを実数変数qで表された式でq \to 1の極限を取ったものとするという話
  • 簡単な連続函数と、その極限として離散状態とを考え、数え上げとは極限(量子化)であるとの枠組み(か？）
  • q-数え上げ ( q-enumeration ) と呼ばれる
  • q-変形の例として、二項係数のq-form "q-binomial coefficient)を挙げる
  • https://en.wikipedia.org/wiki/Gaussian_binomial_coefficient:titel=Wiki 英語記事に詳しい
  • \begin{pmatrix} n \\ m \end{pmatrix}_q = \sum_{\lambda \subseteq ( (n-m)^m)} q^{|\lambda|}と言う式が『線形代数と数え上げ』にあるが、この\lambdaは整数分割になっており、ちょっと面倒くさい
  • Wiki記事の式によれば、:\begin{pmatrix} n \\ m \end{pmatrix}_q = \frac{(1-q^n)(1-q^{n-1})...(1-q^{n-m+1})}{(1-q)(1-q^2)...(1-q^m)}
my.q.binom <- function(n,m,q){
	ret <- 1
	for(i in 1:m){
		ret <- ret * (1-q^{n-i+1}) / (1-q^i)
	}
	return(ret)
}

q <- seq(from=-1,to=1.2,length=400)

v <- rep(0,length(q))


n <- 5
m <- 2

V <- factorial(n)/(factorial(m)*factorial(n-m))

for(i in 1:length(v)){
	v[i] <- my.q.binom(n,m,q[i])
}

plot(q,v,type="l")
abline(v=1)
abline(h=V)

f:id:ryamada:20220123112617j:plain

第８章　平面分割の対角断面

  • シューア過程と呼ばれる確率過程の研究から注目を浴びるようになった
  • 位相的弦理論に応用

第９章　平面分割と非交差経路

第２部　完全マッチングと全域木の数え上げ

第１０章　ダイマー模型

  • ダイマー模型と２部グラフと完全マッチング
  • タイリングとも関係
  • ダイマー模型から、状態数、エネルギー状態などにつながり、量子力学的になる。全場合を網羅するのが「分配函数」。確率の総和が１になるようにする正規化項
  • 「カステレインはダイマー模型の分配函数を線形代数的に計算する方法を示した」
  • 「分配函数が直接に行列式として表せるのはグラフが平面的(な)場合に限られる」
  • 平面化可能グラフは球面に描けるということ
  • トーラスに描けるグラフについて拡張された
  • 球面上の場合の分配函数は１個の行列
  • トーラス上の場合の分配函数は４個の行列
  • (球面に描ける)平面化可能グラフのダイマー模型のダイマーの取り方の場合の数(分配函数)は、カステレイン行列Kの行列式の絶対値
  • カステレイン行列の要素は、N個の頂点セット２つを持つ２部グラフについてのNxN行列。行が第１セット、列が第２セットに対応し、第１・第２の頂点間にエッジがなければ０、エッジがあれば値が入る。その値は「そのダイマーの重みに符号をつけたもの」
  • 「Kの固有ベクトルを直接構成して、Kを対格かし、その固有値の積としてKの行列式を表すことにしてみた
  • 2m x 2n の正方格子の場合には Z = |\text{det}(K)| = \prod_{k=1}^m \prod_{l=1}^n 4a^2 \cos ^2 {\frac{k \pi}{2m+1}} + 4b^2 \cos^2{\frac{l \pi}{2n+1}}) と美しい。。。
  • さらに物理学的には、m,n \to \inftyにおいて、自由エネルギーが
  • F = - \lim _{m,n \to \infty} \frac{\log{Z}}{4mn}
  • F = -\frac{1}{\pi^2} \int_0^{\frac{\pi}{2}} d \theta \int_0 ^ {\frac{\pi}{2}} d \tau \log{4a^2 \cos^2{\theta} + 4b^2 \cos^2{\tau}}) になるという

第１１章　カステレイン行列

  • 分配函数は、すべての場合の数
  • 相関関数は、頂点重複のない辺の(亜)集合に対応する場合の数(ある周辺度数に対する場合の数に相当するだろう)

第１２章　有限正方格子上のダイマー模型

  • 扱いやすいグラフでやってみる

第１３章　パフ式とその使い方

  • パフ式は偶数次の反対称行列に定義される
  • 外積代数と関係する
  • 反対称行列だから箙と関係してくる

第１２章　全域木の数え上げ

第１３章　全域木と完全マッチングの対応

付録A

付録B

付録C　発展的話題