すべての割り付け - ryamadaの遺伝学・遺伝統計学メモ

こちらで、重み付き割り付けのことをやっている
$N!$ 通りのうちの最適順列を求める話
特定の順列が最も都合がよいことを調べているときに、「それ以外のすべての場合」と比べたり、ある割り付けだけを固定して、それ以外の割り付けについてはすべての場合を合算したりしたくなる
そんなとき、「すべての順列」について、「コスト」の和を取りたい
こういうときの捜し物で一番面倒なのは、「その計算式って、なんていう名前なの？」ということ。それがわかるまでが「捜し物」
それがわかってしまえば、「それが『そういう名前』であること」「それについてのかいつまんだ知識」「その計算が難しいこと」など、必要な情報はかなりすぐに集まる
以下はその結果
デターミナントとパーマネントの解説ＰＤＦ
ここで、行列と、順列の関係を見よう
N次正方行列には行列式というのがある(Wiki)
- $det(M)=\sum_{s \in S} sign(s) \prod_{i=1}^N m_{i,s(i)}$ で表される
- ここで、MはN次正方行列、Sはすべての順列を要素とする集合で、sはその要素。sign(s)はsignatureでsが偶置換なら1奇置換なら-1である。 $m_{i,s(i)}$ はMのi行s(i)列要素
- この計算は、N!通りを網羅しなくても、 $M=VTV^(-1)$ と固有値分解して、固有値の積をとればよいので(比較的)簡単
- ここで、行列式には、N!通りの割り付けに対応した項が登場している
- コスト行列Mについて、コストが $\sum_{i=1}^N m_{i,s(i)}$ であるようなとき、 $t_{i,s(i)}=exp(m_{i,s(i)})$ を考えれば $\prod_{i=1}^N t_{i,s(i)}$ を考えることとなり、これは、行列式の項の１つに対応している
パーマネント(Wiki)
- 今、このような $\prod_{i=1}^N m_{i,s(i)}$ をすべての順列について足し合わせたいとする
- $permanent(M)=\sum_{s \in S} \prod_{i=1}^N m_{i,s(i)}$ で表される
- この計算は大変だ、という(こちら)
ここで、割り付けに関して、行列の行列式とパーマネントを見た
２者の違いは係数の定義の違いだった
- さらに一般化して $det^(\alpha)=\sum_{s \in S} \alpha^{N-vn(s)} \prod_{i=1}^N m_{i,s(i)}$ のようにして
- $det^{-1}$ が行列式、 $det^{1}$ がパーマネントとすることもできるという(こちら)
- これも資料
また、別の一般化への道もある
- 割り付け行列は、0,1のみを値に持つ正方行列で、すべての列、すべての行に1はただ１箇所だけである
- この条件を緩めると一般化順列行列になる(こちら)。各行、各列に１か所だけ非ゼロの要素があるような行列のこと
- 別の緩め方もある。各行、各列の和が1になるところは固定して、行列要素が0,1のみではなく、0,-1,1であることを許したものがAlternating sign matrix(こちら)
パーマネントの計算
- 小さいときは、正確に計算、大きいときは推定
  - こちら