接続行列
無向グラフに対してその向き付け接続行列は、列ごとに符号を反転させることを除いて一意的である。これは、列の成分の符号を反転させることが辺の向きの逆転に対応するためである。
グラフGの非向き付け接続行列は定理
A ( L ( G ) ) = B ( G ) T B ( G ) − 2 I m {\displaystyle A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}}
によってその線グラフ(英語版) L(G) の隣接行列と関連している。上式において、A(L(G)) はGの線グラフの隣接行列、B(G) は接続行列、Imは次元mの単位行列である。
離散ラプラシアン(またはキルヒホッフ行列)は式
B ( G ) B ( G ) T {\displaystyle B(G)B(G)^{\textsf {T}}}
によって向き付け接続行列B(G) から得られる。
グラフの整数サイクル空間(英語版)はその向き付け接続行列の零空間に等しい。これは整数または実数または複素数にわたる行列と見なされる。二値サイクル空間はその向き付けまたは非向き付け接続行列の零空間である。これは、二元体にわたる行列と見なされる。
結合構造(英語版)(Incidence structure)Cの「接続行列」はp × q行列B(またはその転置)である。ここで、pおよびqはそれぞれ「点」および「線」の数であり、点piおよびLjが接続しているならばBi,j = 1、それ以外は0となる。この場合、接続行列はこの構造のレフィグラフ(英語版)のbiadjacency行列でもある。全てのレフィグラフに対してハイパーグラフが存在し、その逆もまた同様であるため、結合構造の接続行列はハイパーグラフを記述する。