接続行列
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/05/07 14:03 UTC 版)
数学において、接続行列(せつぞくぎょうれつ、英: Incidence matrix)は、2つのオブジェクトクラス間の関係を示す行列である。1つ目のクラスをX、2つ目をYとすると、接続行列は、Xのそれぞれの要素について1つの行を、Yのそれぞれの要素について1つの列を持つ。行xおよび列y中の成分はxおよびyが関連(この文脈においてincidentと呼ばれる)しているならば1であり、関連していないならば0である。以下に示すように変種が存在する。
- ^ Coxeter, H.S.M. (1973) [1963], Regular Polytopes (3rd ed.), Dover, pp. 166-167, ISBN 0-486-61480-8
- ^ Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, The Mathematical Association of America, p. 99
接続行列
出典: フリー百科事典『ウィキペディア(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} の固有値は全て非負であることを示す。
※この「接続行列」の解説は、「ラプラシアン行列」の解説の一部です。
「接続行列」を含む「ラプラシアン行列」の記事については、「ラプラシアン行列」の概要を参照ください。
- 接続行列のページへのリンク