拉普拉斯矩阵群逆的分块表示

Block Representation of Laplacian Matrix Group Inverse

摘要: 令G为具有拉普拉斯矩阵L(G)和无符号拉普拉斯矩阵Q(G)的加权图。根据L(G)的广义舒尔补的群可逆条件，以及拉普拉斯矩阵的其它性质，利用分块矩阵求群逆的计算方法，计算L(G)群逆的分块表达式。并通过例子说明计算结果。

Abstract: Let G be a weighted graph with Laplacian matrix L(G) and signless Laplacian matrix Q(G). According to the group invertibility condition of the generalized Schur complement of L(G) and other properties of Laplacian matrix. An expression for the group inverse of L(G) is calculated by using the method of group inverse of block matrix. Moreover, an example has been constructed to illustrate the result.

1. 引言

对于 $n\times n$ 矩阵A，A的群逆定义为 $n\times n$ 矩阵X，满足矩阵方程：

$AXA=A$， $XAX=X$ 和 $AX=XA$。

一般来讲，并非每个方阵都有群逆，矩阵A具有群逆的充分必要条件是它的指数为1，或等价地， $\text{rank}\left(A\right)=\text{rank}\left(A^2\right)$ (参见 [1] )。如果A的群逆存在，则它是唯一的，记为 $A^{\text{\#}}$。如果 $A^{\text{\#}}$ 存在，则称矩阵A

是群可逆的。文献 [2] 中给出了分块矩阵的群逆的一些表示。令 $M=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)$，其中A是可逆的，M的舒

尔补 $S=D-C{A}^{-1}B$ 是矩阵分析中的基本工具，也是许多矩阵不等式的来源。使用舒尔补方法处理矩阵问题的想法应用十分广泛。当它扩展到更一般的情况时，广义舒尔补 $S=D-C{A}^{\text{\#}}B$ 在 $M^{\text{\#}}$ 的表达式中起着重要作用(参见 [3] )。对于 $n\times m$ 矩阵B，B的Moore-Penrose逆矩阵是满足以下矩阵方程(参见 [4] [5] )的 $m\times n$ 矩阵 $B^{†}$ ：

$B{B}^{†}B=B$， $B^{†}B{B}^{†}=B^{†}$， ${\left(B{B}^{†}\right)}^H=B{B}^{†}$ 和 ${\left(B^{†}B\right)}^H=B^{†}B$，

其中 $B^H$ 表示B的共轭转置。值得指出的是，任何复矩阵都存在唯一的Moore-Penrose逆矩阵。Moore-Penrose逆的更多基本性质可以参考 [6]。

在本文中，我们考虑简单、无向的赋权图。令 $G=\left(V\left(G\right),E\left(G\right)\right)$ 是带有顶点集 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ 和边集 $E\left(G\right)=\left\{e_1,e_2,\cdots ,e_m\right\}$ 的无向图，G的每条边都标记有一个正实数，称为边的权重。令 $A\left(G\right)$ 是G的 $n\times n$ 邻接矩阵，其中如果G中没有连接顶点 $v_i$ 和 $v_j$ 的边，则其 $\left(i,j\right)$ 项等于0，否则等于连接顶点 $v_i$ 和 $v_j$ 的边的权重。令 $D\left(G\right)$ 为度矩阵，其对角线元素为 $d_G\left(v_1\right),d_G\left(v_2\right),\cdots ,d_G\left(v_n\right)$，其中 $d_G\left(v_i\right)$ 等于G中与顶点 $v_i$ 相关联的边的权重之和。矩阵 $D\left(G\right)-A\left(G\right)$ 和 $D\left(G\right)+A\left(G\right)$ 分别称为G的拉普拉斯矩阵和无符号拉普拉斯矩阵。容易验证G的拉普拉斯矩阵和无符号拉普拉斯矩阵都是半正定的。令 $L\left(G\right)$ 为加权图G的拉普拉斯矩阵。由于 $L\left(G\right)$ 是对称的，因此 $L^{\text{\#}}\left(G\right)$ 存在并且L^#(G) = L^†(G)。

关于分块矩阵群逆的表达式问题是学者们研究较为活跃的部分，但由于该问题难度较大，多数分块矩阵群逆的表达式是建立在一些特定条件下的。受文献 [7] 的启发，我们可以将分块矩阵群逆的一些结论应用在拉普拉斯矩阵上，结合拉普拉斯矩阵自身的性质，得到拉普拉斯矩阵群逆的表达式。本文结构如下，在第2节中我们首先介绍两个重要引理，这些引理帮助我们计算拉普拉斯矩阵的群逆。在第3节中，我们给出拉普拉斯矩阵群逆的分块表示。此外，还构造一个例子来说明上述结果。

2. 预备定理

为了证明主要结果，本节给出一些引理。对于群可逆矩阵S， $S^{\pi }$ 表示矩阵 $I-S{S}^{\text{\#}}$，其中I是单位矩阵。

引理2.1 [8] 设M为艾尔米特半正定矩阵，将方阵M划分为 $M=\left(\begin{array}{cc}A& B\\ B^{\text{T}}& C\end{array}\right)$，其中 $B^{\text{T}}$ 为B的转置矩阵，则 $A^{\pi }B=0$， $B{C}^{\pi }=0$。

引理2.2 [9] 令 $M=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)$，其中A是群可逆的。令 $S=D-C{A}^{\text{\#}}B$ 是M的广义舒尔补。如果 $C{A}^{\pi }B=0$，A和S是群可逆的，则

1) M是群可逆的当且仅当

$\text{rank}\left(A^2+B{S}^{\pi }C\right)=\text{rank}\left(A\right)$，

$A^{\pi }B{S}^{\pi }=0$， $S^{\pi }C{A}^{\pi }=0$， $A^{\pi }B{S}^{\text{\#}}C{A}^{\pi }=0$ ；

2) 如果M是群可逆的，那么有

$M^{\text{\#}}=\left[\left(\begin{array}{cc}0& A^{\pi }B\\ S^{\pi }C& S^{\pi }D\end{array}\right)R+I\right]\cdot W\cdot R\cdot W\cdot \left[I+R\left(\begin{array}{cc}0& B{S}^{\pi }\\ C{A}^{\pi }& D{S}^{\pi }\end{array}\right)\right]$，

其中 $W={\left(I+A^{\text{\#}}B{S}^{\pi }C{A}^{\text{\#}}\right)}^{-1}\oplus I$， $R=\left(\begin{array}{cc}{A}^{\text{\#}}+A^{\text{\#}}B{S}^{\text{\#}}{B}^{\text{T}}{A}^{\text{\#}}& -A^{\text{\#}}B{S}^{\text{\#}}\\ -S^{\text{\#}}{B}^{\text{T}}{A}^{\text{\#}}& S^{\text{\#}}\end{array}\right)$。

3. 矩阵群逆

在本节中，我们给出拉普拉斯矩阵群逆的表达式。

定理3.1令G为具有拉普拉斯矩阵 $L\left(G\right)$ 的加权图。如果 $L\left(G\right)$ 被划分为 $L\left(G\right)=\left(\begin{array}{cc}A& B\\ B^{\text{T}}& C\end{array}\right)$，其中A是群可逆的，广义舒尔补 $S=C-B^{\text{T}}{A}^{\text{\#}}B$，则

$L^{\text{\#}}\left(G\right)=\left[\left(\begin{array}{cc}0& 0\\ S^{\pi }{B}^{\text{T}}& S^{\pi }C\end{array}\right)R+I\right]\cdot W\cdot R\cdot W\cdot \left[I+R\left(\begin{array}{ll}0\hfill & B{S}^{\pi }\hfill \\ 0\hfill & C{S}^{\pi }\hfill \end{array}\right)\right]$，

其中 $B^{\text{T}}$ 是矩阵B的转置， $W_0=I+A^{\text{\#}}B{S}^{\pi }{B}^{\text{T}}{A}^{\text{\#}}$， $W=W_0^{-1}\oplus I$， $R=\left(\begin{array}{cc}{A}^{\text{\#}}+A^{\text{\#}}B{S}^{\text{\#}}{B}^{\text{T}}{A}^{\text{\#}}& -A^{\text{\#}}B{S}^{\text{\#}}\\ -S^{\text{\#}}{B}^{\text{T}}{A}^{\text{\#}}& S^{\text{\#}}\end{array}\right)$。

证明：根据拉普拉斯矩阵的性质，结合引理2.1，我们可以得到 $A^{\pi }B$ 和 $B^{\text{T}}{A}^{\pi }$ 等于0。由于 $L^{\text{\#}}\left(G\right)$ 的存在性，再根据引理2.2，得出

$L^{\text{\#}}(G)=\left[\left(\begin{array}{cc}0& 0\\ S^{\pi }{B}^{\text{T}}& S^{\pi }C\end{array}\right)R+I\right]\cdot W\cdot R\cdot W\cdot \left[I+R\left(\begin{array}{ll}0\hfill & B{S}^{\pi }\hfill \\ 0\hfill & C{S}^{\pi }\hfill \end{array}\right)\right]$，

其中 $R=\left(\begin{array}{cc}{A}^{\text{\#}}+A^{\text{\#}}B{S}^{\text{\#}}{B}^{\text{T}}{A}^{\text{\#}}& -A^{\text{\#}}B{S}^{\text{\#}}\\ -S^{\text{\#}}{B}^{\text{T}}{A}^{\text{\#}}& S^{\text{\#}}\end{array}\right)$， $W_0=I+A^{\text{\#}}B{S}^{\pi }{B}^{\text{T}}{A}^{\text{\#}}$，并且 $W=W_0^{-1}\oplus I$。

例3.1考虑图1所示的加权星图 $K_{1,6}$。

Figure 1. Star graph

图1. 星图

$K_{1,6}$ 的拉普拉斯矩阵是

$L\left(K_{1,6}\right)=\left(\begin{array}{ccccccc}10& -1& -2& -1& -2& -3& -1\\ -1& 1& 0& 0& 0& 0& 0\\ -2& 0& 2& 0& 0& 0& 0\\ -1& 0& 0& 1& 0& 0& 0\\ -2& 0& 0& 0& 2& 0& 0\\ -3& 0& 0& 0& 0& 3& 0\\ -1& 0& 0& 0& 0& 0& 1\end{array}\right)$，

不失一般性，取 $A=\left(\begin{array}{cc}10& -1\\ -1& 1\end{array}\right)$， $B=\left(\begin{array}{ccccc}-2& -1& -2& -3& -1\\ 0& 0& 0& 0& 0\end{array}\right)$ 和 $C=\left(\begin{array}{lllll}2\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 2\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 3\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right)$。

那么

$S=C-B^{\text{T}}{A}^{\text{\#}}B=\left(\begin{array}{ccccc}14/9& -2/9& -4/9& -2/3& -2/9\\ -2/9& 8/9& -2/9& -1/3& -1/9\\ -4/9& -2/9& 14/9& -2/3& -2/9\\ -2/3& -1/3& -2/3& 2& -1/3\\ -2/9& -1/9& -2/9& -1/3& 8\end{array}\right)$，

$S^{\text{\#}}=\left(\begin{array}{ccccc}13/30& -1/6& -1/15& -1/30& -1/6\\ -1/6& 11/15& -1/6& -2/15& -4/15\\ -1/15& -1/6& 13/30& -1/30& -1/6\\ -1/30& -2/15& -1/30& 1/3& -2/15\\ -1/6& -4/15& -1/6& -2/15& 11/15\end{array}\right)$，

$R=\left(\begin{array}{ccccc}1/5& 1/5& 1/5& 1/5& 1/5\\ 1/5& 1/5& 1/5& 1/5& 1/5\\ 1/5& 1/5& 1/5& 1/5& 1/5\\ 1/5& 1/5& 1/5& 1/5& 1/5\\ 1/5& 1/5& 1/5& 1/5& 1/5\end{array}\right)$，

$S^{\pi }=\left(\begin{array}{ccccccc}2/15& 2/15& 1/30& -1/15& 1/30& 1/15& -1/15\\ 2/15& 17/15& 1/30& -1/15& 1/30& 1/15& -1/15\\ 1/30& 1/30& 13/30& -1/6& -1/15& -1/30& -1/6\\ -1/15& -1/15& -1/6& 11/15& -1/6& -2/15& -4/15\\ 1/30& 1/30& -1/15& -1/6& 13/30& -1/30& -1/6\\ 1/15& 1/15& -1/30& -2/15& -1/30& 1/3& -2/15\\ -1/15& -1/15& -1/6& -4/15& -1/6& -2/15& 11/15\end{array}\right)$，

$W=\left(\begin{array}{ccccccc}6/7& -1/7& 0& 0& 0& 0& 0\\ -1/7& 6/7& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 1\end{array}\right)$。

由定理3.1，可得

$L^{\text{\#}}\left(K_{1,6}\right)=\left(\begin{array}{ccccccc}13/147& -8/147& 5/294& -8/147& 5/294& 2/49& -8/147\\ -8/147& 118/147& -37/294& -29/147& -37/294& -5/49& -29/147\\ 5/294& -37/294& 131/294& -37/294& -8/147& -3/98& -37/294\\ -8/147& -29/147& -37/294& 118/147& -37/294& -5/49& -29/147\\ 5/294& -37/294& -8/147& -37/294& 131/294& -3/98& -37/294\\ 2/49& -5/49& -3/98& -5/49& -3/98& 16/49& -5/49\\ -8/147& -29/147& -37/294& -29/147& -37/294& -5/49& 118/147\end{array}\right)$。

推论3.1令G为具有拉普拉斯矩阵 $L\left(G\right)$ 的加权图，如果 $L\left(G\right)$ 被划分为 $L\left(G\right)=\left(\begin{array}{cc}A& B\\ B^{\text{T}}& C\end{array}\right)$，并且广义舒尔补 $S=C-B^{\text{T}}{A}^{\text{\#}}B=0$，则

$L^{\text{\#}}\left(G\right)=\left(\begin{array}{cc}{W}_0^{-1}{A}^{\text{\#}}{W}_0^{-1}& W_0^{-1}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}B\\ B^{\text{T}}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}{W}_0^{-1}& B^{\text{T}}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}B\end{array}\right)$，

这里 $W_0=I+A^{\text{\#}}B{B}^{\text{T}}{A}^{\text{\#}}$。

证明：根据定理3.1，如果 $S=0$，那么 $S^{\pi }=I$， $R=\left(\begin{array}{cc}{A}^{\text{\#}}& 0\\ 0& 0\end{array}\right)$，

$\begin{array}{c}{L}^{\text{\#}}\left(G\right)=\left[\left(\begin{array}{cc}0& 0\\ B^{\text{T}}& C\end{array}\right)R+I\right]\cdot W\cdot R\cdot W\cdot \left[I+R\left(\begin{array}{ll}0\hfill & B\hfill \\ 0\hfill & C\hfill \end{array}\right)\right]\\ =\left(\begin{array}{cc}I& 0\\ B^{\text{T}}{A}^{\text{\#}}& I\end{array}\right)\left(\begin{array}{cc}{W}_0^{-1}& 0\\ 0& I\end{array}\right)\left(\begin{array}{cc}{A}^{\text{\#}}& 0\\ 0& 0\end{array}\right)\left(\begin{array}{cc}{W}_0^{-1}& 0\\ 0& I\end{array}\right)\left(\begin{array}{cc}I& A^{\text{\#}}B\\ 0& I\end{array}\right)\\ =\left(\begin{array}{cc}{W}_0^{-1}{A}^{\text{\#}}{W}_0^{-1}& W_0^{-1}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}B\\ B^{\text{T}}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}{W}_0^{-1}& B^{\text{T}}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}{W}_0^{-1}{A}^{\text{\#}}B\end{array}\right)\end{array}$

设G是一个具有无符号拉普拉斯矩阵 $Q\left(G\right)$ 的加权图，并且 $Q\left(G\right)$ 被划分为 $Q\left(G\right)=\left(\begin{array}{cc}X& Y\\ Y^{\text{T}}& Z\end{array}\right)$。由于 $Q\left(G\right)$ 是半正定的。通过引理2.1，我们有 $X^{\pi }Y=0,Y{Z}^{\pi }=0$，可以得到 $Q^{\text{\#}}\left(G\right)$ 的表达式。

定理3.2令G为具有无符号拉普拉斯矩阵 $Q\left(G\right)$ 的加权图。如果 $Q\left(G\right)$ 被划分为 $Q\left(G\right)=\left(\begin{array}{cc}X& Y\\ Y^{\text{T}}& Z\end{array}\right)$，其中 是群可逆的，广义舒尔补 $S=Z-Y^{\text{T}}{X}^{\text{\#}}Y$，则

$Q^{\text{\#}}\left(G\right)=\left[\left(\begin{array}{cc}0& 0\\ S^{\pi }{Y}^{\text{T}}& S^{\pi }Z\end{array}\right)R+I\right]\cdot W\cdot R\cdot W\cdot \left[I+R\left(\begin{array}{ll}0\hfill & Y{S}^{\pi }\hfill \\ 0\hfill & Z{S}^{\pi }\hfill \end{array}\right)\right]$，

这里

$R=\left(\begin{array}{cc}{X}^{\text{\#}}+X^{\text{\#}}Y{S}^{\text{\#}}{Y}^{\text{T}}{X}^{\text{\#}}& -X^{\text{\#}}Y{S}^{\text{\#}}\\ -S^{\text{\#}}{Y}^{\text{T}}{X}^{\text{\#}}& S^{\text{\#}}\end{array}\right)$

$W=W_0^{-1}\oplus I$

$W_0=I+X^{\text{\#}}Y{S}^{\pi }{Y}^{\text{T}}{X}^{\text{\#}}$

证明：根据无符号拉普拉斯矩阵的性质，结合引理2.1，我们可以得到 $A^{\pi }B$ 和 $B^{\text{T}}{A}^{\pi }$ 等于0。由于 $Q^{\#}\left(G\right)$ 的存在性，再根据引理2.2，得出

$Q^{\#}\left(G\right)=\left[\left(\begin{array}{cc}0& 0\\ S^{\pi }{Y}^{\text{T}}& S^{\pi }Z\end{array}\right)R+I\right]\cdot W\cdot R\cdot W\cdot \left[I+R\left(\begin{array}{ll}0\hfill & Y{S}^{\pi }\hfill \\ 0\hfill & Z{S}^{\pi }\hfill \end{array}\right)\right]$，

其中 $R=\left(\begin{array}{cc}{X}^{\text{\#}}+X^{\text{\#}}Y{S}^{\text{\#}}{Y}^{\text{T}}{X}^{\text{\#}}& -X^{\text{\#}}Y{S}^{\text{\#}}\\ -S^{\text{\#}}{Y}^{\text{T}}{X}^{\text{\#}}& S^{\text{\#}}\end{array}\right)$， $W_0=I+X^{\text{\#}}Y{S}^{\pi }{Y}^{\text{T}}{X}^{\text{\#}}$，并且 $W=W_0^{-1}\oplus I$。

推论3.2令G为具有拉普拉斯矩阵 $Q\left(G\right)$ 的加权图。如果 $Q\left(G\right)$ 被划分为 $Q\left(G\right)=\left(\begin{array}{cc}X& Y\\ Y^{\text{T}}& Z\end{array}\right)$，并且广义舒尔补 $S=Z-Y^{\text{T}}{X}^{\text{\#}}Y=0$，则

$Q^{\text{\#}}\left(G\right)=\left(\begin{array}{cc}{W}_0^{-1}{X}^{\text{\#}}{W}_0^{-1}& W_0^{-1}{X}^{\text{\#}}{W}_0^{-1}{X}^{\text{\#}}Y\\ Y^{\text{T}}{X}^{\text{\#}}{W}_0^{-1}{Y}^{\text{\#}}{W}_0^{-1}& Y^{\text{T}}{X}^{\text{\#}}{W}_0^{-1}{X}^{\text{\#}}{W}_0^{-1}{X}^{\text{\#}}Y\end{array}\right)$

这里 $W_0=I+X^{\text{\#}}Y{Y}^{\text{T}}{X}^{\text{\#}}$。

4. 结语

本文已经求出拉普拉斯矩阵和无符号拉普拉斯矩阵群逆的一种表达式，并且举例说明计算结果。通过测试和比较不同类型的图，我们发现本文给出的表达式与文献 [7] 中所给的表达式相比较而言，利用本文给出的表达式来计算拉普拉斯矩阵群逆时，计算量更小。受文献 [7] 和 [10] 的启发，如何将拉普拉斯矩阵群逆的分块表示应用到电网络图中，以及遇到大型矩阵时相应算法该如何实现，这是需要我们继续深入研究的。

基金项目

国家自然科学基金资助项目(12001368)；上海市青年科技英才杨帆计划(20YF1433100)。