1
大学数学基礎解説
文献あり

要素が全部aの正方行列の固有多項式を対合で求める

180
0

正方行列An=(a)i,j=1nを,要素が全部an×n行列とする (aは定数).本稿ではAnの固有多項式を,組合せ論を使う方法で計算する.

任意の非負整数nに対して以下が成立.
det(AnxIn)=(1)n(xnnaxn1).

証明に入る前にグラフの閉路と行列式の関係について復習する.
有限有向グラフGの部分グラフで,各節点の入次数と出次数が1であるものの集合をC(G)とかく.
グラフHC(G)は,より平易に言えば,Gに含まれる互いに疎な閉路をいくつか集めてきてできるグラフである.
グラフHC(G)の連結成分の数をc(H)とかく.また,Hに含まれないGの節点の数をip(H)とかく.

また,グラフGには枝重みe:E(G)Cが付けられているとし,Gの部分グラフHに対してw(H)eE(H)w(e)Hに含まれる枝重みの積を表すとする.
以下のことが知られている.

固有多項式とグラフの閉路の関係

n×n行列Mが枝重み付き有限有向グラフGの隣接行列であるとき,Mの固有多項式det(MxIn)は以下の通り書ける.
det(MxIn)=HC(G)(1)nc(H)xip(H)w(H).

この事実の証明は例えば [1]を参照してほしい.
ここでは,定理2の証明は書かず具体例を紹介するにとどめておく.

定理2の例1


定理2の例2

定理1の証明.

定理2を使うと,計算したい行列式det(AnxIn)は,
det(AnxIn)=HC(Kn)(1)nc(H)xip(H)a|E(H)|
と書ける.ただし,Knn節点の完全有向グラフに,全ての節点へ自己ループを加えてできる有向グラフを表す(下図左を見よ.)

集合C(Kn)の部分集合Snを,枝のない部分グラフと,自己ループ1個だけからなる部分グラフを集めた集合と定義する.例えば,n=7のときS7は下図右のようになる.

左:!FORMULA[38][35574117][0].枝は双方向に張られているとする.右:!FORMULA[39][-692476267][0]の元. 左:K7.枝は双方向に張られているとする.右:S7の元.

定理1の右辺は,この集合Snにわたる和として
HSn(1)nc(H)xip(H)a|E(H)|=(1)n(xnnaxn1)
とかける.

よって,我々が示すべきことは,集合C(Kn)Snにわたる重みの和が0になること,すなわち
HC(Kn)Sn(1)nc(H)xip(H)a|E(H)|=0
である.

これを示すには,枝の数を変えずに,閉路の数を1だけ変化させるような対合
φ:C(Kn)SnC(Kn)Sn
を作ればよい.

グラフの節点を{1,2,,n}とラベル付けする.
HC(Kn)Snとする.グラフHに含まれる節点の中で,ラベルが最小の節点 (iとする)と二番目に小さい節点 (jとする)に注目する.

  • ijが同じサイクルに含まれる場合,サイクルを二つに分離する.
    つまり,(i,x1,,xr,j,y1,,yt)というサイクルを,(i,x1,,xr),(j,y1,,yt)という二つのサイクルに分ける.
  • ijが違うサイクルに含まれる場合,サイクルを一つに融合する.
    つまり,(i,x1,,xr),(j,y1,,yt)という二つのサイクルを(i,x1,,xr,j,y1,,yt)という一つのサイクルにする.

それ以外の部分は変化させない.
この操作をφとすれば,これは所望の対合である.

対合!FORMULA[61][1017910466][0]のようす 対合φのようす

(証明終わり.)

参考文献

[1]
Richard A. Brualdi, Dragos Cvetkovic, A Combinatorial Approach to Matrix Theory and Its Applications, Chapman & Hall, 2008
投稿日:2023811
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

Do everything bijectively.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中