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

適当に番号をふって作った隣接行列を G とする。
ノード番号に置換σを作用させる。

このとき、G は行・列ともに入れ替えが起こる。
任意の置換は互換の積で書けるから、(i,j)の互換T_ijを考えれば良い。

これを繰り返すと、任意の置換Sを作用した隣接行列を得ることができる。

互換行列は対称かつ直交行列であるから(cf. 行列の変換)、

とおくと、

これは直交変換であるから、固有値は変化しない。
またGの特異値は  の固有値の平方根であるから、これも変化しない。

例

互換 (1 2) を作用させる。

を左右からかければよい。

このとき、いずれの固有値も{0,0,0}である。また、特異値は{√2,0,0}である。