nopu@wiki
nopu@wiki

隣接行列はwell-defined

ノードの番号の振り方によって、隣接行列の固有値は変化しない

適当に番号をふって作った隣接行列を G とする。
ノード番号に置換σを作用させる。
i \mapsto \sigma(i)
このとき、G は行・列ともに入れ替えが起こる。
任意の置換は互換の積で書けるから、(i,j)の互換T_ijを考えれば良い。
G \mapsto T_{ij} G T_{ij}
これを繰り返すと、任意の置換Sを作用した隣接行列を得ることができる。
G \mapsto T_p \cdots T_1 G T_1 \cdots T_p
互換行列は対称かつ直交行列であるから(cf. 行列の変換)、
S = T_1 \cdots T_p
とおくと、
G \mapsto S^\mathrm{T} G S
これは直交変換であるから、固有値は変化しない。
またGの特異値は G^\mathrm{T} G の固有値の平方根であるから、これも変化しない。

例
G = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}
互換 (1 2) を作用させる。
T = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}
を左右からかければよい。
\widetilde{G} = T G T = \begin{pmatrix} 0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}
このとき、いずれの固有値も{0,0,0}である。また、特異値は{√2,0,0}である。
「隣接行列はwell-defined」をウィキ内検索
最終更新：2010年10月26日 23:54
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。