二维逆问题/特殊矩阵

一个包含加权图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}}.