接続行列とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/13 00:05 UTC 版)

「ラプラシアン行列」の記事における「接続行列」の解説

M e v = { 1 , if  v = i − 1 , if  v = j 0 , otherwise . {\displaystyle M_{ev}=\left\{{\begin{array}{rl}1,&{\text{if }}v=i\\-1,&{\text{if }}v=j\\0,&{\text{otherwise}}.\end{array}}\right.} によって与えられる辺e（頂点iとjを連結している; i > j）と頂点vについて要素Mevを持つ | e | × | v | {\textstyle |e|\times |v|} 有向接続行列Mを定義する。 次に、ラプラシアン行列Lは L = M T M , {\displaystyle L=M^{\textsf {T}}M\,,} を満たす（ M T {\textstyle M^{\textsf {T}}} はMの転置行列）。 ここで、単位ノルム固有値ベクトル v i {\textstyle \mathbf {v} _{i}} および対応する固有値 λ i {\textstyle \lambda _{i}} を使った L {\textstyle L} の固有値分解を考える。 λ i = v i T L v i = v i T M T M v i = ( M v i ) T ( M v i ) {\displaystyle {\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{\textsf {T}}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{\textsf {T}}M^{\textsf {T}}M\mathbf {v} _{i}\\&=\left(M\mathbf {v} _{i}\right)^{\textsf {T}}\left(M\mathbf {v} _{i}\right)\\\end{aligned}}} λ i {\textstyle \lambda _{i}} はベクトル M v i {\textstyle M\mathbf {v} _{i}} とそれ自身の内積として書くことができるため、これは λ i ≥ 0 {\textstyle \lambda _{i}\geq 0} であり、したがって L {\textstyle L} の固有値は全て非負であることを示す。

※この「接続行列」の解説は、「ラプラシアン行列」の解説の一部です。
「接続行列」を含む「ラプラシアン行列」の記事については、「ラプラシアン行列」の概要を参照ください。