※ 引述《cevian (cevian)》之銘言：
: https://i.imgur.com/keb74uF.jpg
: 想請教的是第二小題
: 證明A是半正定矩陣
這個矩陣 A 是 P_6 的 Laplace matrix, 其中 P_6 為 6 個點的 path
一般而言,
圖 G=(V,E) 的 Laplace matrix L(G) (|V|×|V| 的方陣) 的定義是:
L(G)_{u,v} := { deg(u) if u=v in V
{ -1 if u≠v in V and uv in E
{ 0 o.w.
L(G) 與另一個矩陣有關
設 D 是 G 的一個 orientation (G 的每一邊給一個方向, 變有向圖 D)
D 的 adjacency matrix A(D) (|V|×|E| 的矩陣) 的定義是:
A(D)_{u,e} := { +1 if e=uv in E(D) for some v
{ -1 if e=vu in E(D) for some v
{ 0 o.w.
而 L(G) 與 A(D) 的關係是
L(G) = (A(D)^T)(A(D)) (與 D 的選法無關)
因此 L(G) 都會是半正定
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.147.157
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1547867169.A.902.html