二維逆問題/特殊矩陣

一個包含加權圖G(V,E,w)資訊的重要物件是它的拉普拉斯矩陣。給定圖的頂點編號，它是一個n乘n的方陣L_G，其中n是圖中頂點的數量，其元素為

l_{kl}:={\begin{cases}\sum _{v_{k}\rightarrow v_{l}}w_{kl}{\mbox{ if}}\ k=l,\\-w_{kl}{\mbox{ if}}\ v_{k}\rightarrow v_{l},\\0,{\mbox{ otherwise,}}\end{cases}}

其中v_k → v_l 表示從頂點v_k到頂點v_l存在一條有向邊，w是權重函式。

練習 (*)。給定一個沒有環的有向圖G，證明可以對它的頂點進行編號，使得對應的拉普拉斯矩陣L_G為三角形矩陣。

給定一個帶有邊界的加權圖，通常方便地先對邊界頂點進行編號，並將它的拉普拉斯矩陣寫成塊的形式。

L_{G}={\begin{pmatrix}A&B\\C&D\end{pmatrix}}

矩陣 $L_{G}$ 關於可逆塊D的舒爾補是矩陣 $L_{G}/D=A-BD^{-1}C.$

練習 (*)。證明以下行列式恆等式:

\det L_{G}=\det(L_{G}/D)\det D.

以下矩陣W(G) 由隨機遊走退出機率組成（圖中加權路徑的總和），作為逆問題的邊界測量起著重要作用。假設加權圖G 有N個邊界節點，則N乘N矩陣的第kl個元素等於從邊界頂點v_k 開始隨機遊走的粒子第一次到達邊界頂點v_l 的機率。對於有限連通圖，矩陣W(G) 的各列之和為1。

練習 (**)。推匯出矩陣

W_{G}

關於圖G 的拉普拉斯矩陣

L_{G}

的塊的顯式公式：

W_{G}=I-D_{A}^{-1}(A-BD^{-1}C).

練習 (***)。證明矩陣W(G) 元素和塊的以下展開公式，

w_{kl}=\sum _{v_{k}{\xrightarrow[{}]{path}}v_{l}}\prod _{e=(p,q)\in path}w(e)/l_{pp},

提示：使用行列式的萊布尼茲定義

w_{kl}\det D={\frac {1}{l_{kk}}}\sum _{v_{k}{\xrightarrow {path}}v_{l}}\prod _{e\in path}l(e)\det D({\tilde {path}},{\tilde {path}}),

其中 ${\tilde {path}}=V-(\partial G\cup path).$

\det W(P,Q)\det D=\pm {\frac {\sum _{\sigma \in S_{n}}(-1)^{\operatorname {sgn}(\sigma )}\sum _{p_{k}{\xrightarrow {paths}}q_{\sigma _{k}}}\prod _{e\in paths}l(e)\det D({\tilde {paths}},{\tilde {paths}})}{\prod _{p\in P}l_{pp}}},

其中

{\tilde {paths}}=V-(\partial G\cup paths).

以上練習為圖 G 的連通性屬性和其拉普拉斯矩陣 L(G) 和擊中機率矩陣 W(G) 的子矩陣的秩之間建立了橋樑。

練習 (*)。 設 G 為一個具有自然邊界的平面圖，按圓周編號。設 P 和 Q 為大小為 n 的兩個不相交的邊界節點子集。證明

(-1)^{\frac {n(n+1)}{2}}\det \Lambda _{G}(P,Q)\geq 0,

當且僅當存在從 P 到 Q 的不相交路徑集時，嚴格不等式成立。

練習 (*)。 證明以下圖中路徑的數量等於二項式係數。

將無環圖粘合在一起相當於將加權路徑矩陣相乘。

練習 (**)。 利用先前練習的結果證明以下**帕斯卡三角形**恆等式，參見 [13]，

{\begin{pmatrix}1&1&1&1&\ldots \\1&2&3&4&\ldots \\1&3&6&\ldots &\ddots \\1&4&10&\ldots &\ddots \\1&\ldots &\ldots &\ddots &\ddots \\\end{pmatrix}}={\begin{pmatrix}1&0&0&0&\ldots \\1&1&0&0&\ldots \\1&2&1&0&\ddots \\1&3&3&\ldots &\ddots \\1&\ldots &\ldots &\ddots &\ddots \\\end{pmatrix}}{\begin{pmatrix}1&1&1&1&\ldots \\0&1&2&3&\ldots \\0&0&1&3&\ddots \\0&0&0&\ldots &\ddots \\0&\ldots &\ldots &\ddots &\ddots \\\end{pmatrix}}.