符号图修正拉普拉斯矩阵逆的Moore–Penrose逆组合公式

《Kuwait Journal of Science》：Combinatorial formulas for inverses of modified graph Laplacians of signed graphs via Moore–Penrose inverse

　　

本文给出了连通符号图（signed graph）G的修正拉普拉斯矩阵（modified Laplacian matrix）L(G)+I之逆的逐项组合公式。该方法利用与G关联的满秩矩阵N的Moore–Penrose伪逆（Moore–Penrose pseudoinverse）。研究人员还推导了该逆矩阵各元素的若干性质，其中部分性质反映了符号图的结构特性，包括其是否平衡（balanced）。

论文解读

一、研究背景与问题

图拉普拉斯矩阵及其变体在图论、谱理论、网络科学和数值分析中具有基础性地位。对于无符号图（即所有边均为正边），修正拉普拉斯矩阵L(G)+I的逆矩阵具有双重随机性（doubly stochastic），即元素非负且行和与列和均为1，这一性质在Chebotarev和Shamis提出的矩阵森林定理（Matrix-Forest Theorem）中得到了深刻的组合解释：该逆矩阵的每个元素可表示为图G的根生成森林（rooted spanning forest）的总权重，从而可作为顶点之间相对森林可达性的度量。然而，当图中存在负边时，上述双重随机性不再成立，矩阵森林定理的经典形式也无法直接推广。此前关于修正拉普拉斯矩阵性质的研究主要集中于全正边图，对符号图（signed graph）情形缺乏系统的组合刻画。因此，如何为一般符号图的修正拉普拉斯矩阵逆建立显式的组合公式，并揭示其元素与符号图结构（尤其是平衡性）之间的联系，构成了一个亟待解决的理论问题。

二、研究内容与结论

针对上述问题，研究人员以连通符号图G为对象，系统研究了修正拉普拉斯矩阵L(G)+I的逆矩阵的逐项组合结构。研究人员首先构造了由符号图关联矩阵（incidence matrix）R与单位矩阵I_n拼接而成的满秩矩阵N=(R I_n)，并建立了L(G)+I=NN^?的分解，从而将逆矩阵的计算转化为N的Moore–Penrose伪逆的乘积。在此基础上，研究人员利用Bapat关于Moore–Penrose伪逆的行列式体积公式，对N的所有n阶非零子式进行了完整的图论刻画，引入TU-子图（TU-subgraph）的概念——即连通分量仅为环、恰含一个环的树、或非平衡单圈符号图的生成子图——并据此导出了(L(G)+I)^{-1}逐项的组合公式。该公式表明，逆矩阵的(i,j)元素等于所有满足特定条件的TU-子图H的符号路径与体积平方的加权和除以N的体积平方，其中权重由H中不平衡单圈分量的数目决定。研究人员进一步证明了该公式在平衡符号图情形下退化为Chebotarev–Shamis的经典森林计数公式，从而将矩阵森林定理成功推广至符号图框架。此外，研究人员还推导了逆矩阵元素的若干结构性质，包括零元素出现的充分条件以及两个位置元素相等（至多相差符号）的判定条件，这些性质直接反映了符号图的平衡性与逆矩阵元素之间的内在关联。

三、主要技术方法

研究人员采用的核心方法包括：其一，利用Bapat的行列式体积公式（Theorem 2.1）计算Moore–Penrose伪逆，该公式将伪逆表示为所有满秩子矩阵的逆的加权和；其二，通过将N的列选择解释为在图的每个顶点添加环，建立了列选择与生成子图之间的对应关系，并借助符号图关联矩阵的秩理论（Belardo–Simi?的经典结果）完整刻画了使子矩阵满秩的所有列选择，即TU-子图；其三，对TU-子图的三种允许分量——单个环、恰含一个环的树、非平衡单圈符号图——分别计算其子矩阵的行列式与逆矩阵的显式组合表达式，其中树的逆矩阵元素由路径符号与边的类型权重给出，非平衡单圈图的逆矩阵元素则利用Alazemi等人的定理给出；其四，利用N^?=N^?(L+I)^{-1}的关系，将(L(G)+I)^{-1}的元素与N^?中对应环列的条目建立联系，从而完成组合公式的推导。

四、研究结果

引理2.2（TU-子图的秩刻画）：研究人员证明了N的n个列构成满秩子矩阵当且仅当对应的生成子图每个连通分量均为单个环、恰含一个环的树或非平衡单圈符号图。这一结果将线性代数中的秩条件完全转化为图论中的结构条件，是后续所有组合公式的基础。

引理2.3（子矩阵行列式）：研究人员分别计算了三种允许分量的子矩阵行列式：仅含环时行列式为±1，树加一个环时行列式为±1，非平衡单圈图时行列式为±2。由此得到N的体积平方等于所有TU-子图的权重之和，其中权重为4^{c(H)}，c(H)为不平衡单圈分量数。

定理2.9（N^?的组合公式）：研究人员将Bapat公式应用于N，结合TU-子图的秩刻画与各分量的逆矩阵表达式，给出了N的Moore–Penrose伪逆每个元素的组合求和公式，其中每一项为对应TU-子图的逆矩阵元素乘以该子图的体积平方。

定理2.10（主定理）：研究人员证明了(L(G)+I)^{-1}的(i,j)元素等于所有包含顶点i处环且i、j位于同一分量的TU-子图的符号路径与体积平方的加权和除以vol2N。该公式是全文的核心结果，将逆矩阵元素完全用符号图的组合结构（TU-子图及其路径符号）表达。

定理2.10的推论与性质：当G为全正边图时，该公式退化为Chebotarev–Shamis的经典森林计数公式，验证了结果的兼容性。研究人员还给出了具体实例（例2.12），通过手工枚举TU-子图验证了公式的正确性。

第三节的进一步性质：研究人员推导了逆矩阵元素的若干结构性质，包括零元素的充分条件——即当某类TU-子图不存在时对应元素为零——以及两个位置元素相等（至多相差符号）的判定条件，这些性质直接与符号图的平衡性相关联。

五、讨论与结论

研究人员的讨论部分指出，所建立的组合公式将符号图修正拉普拉斯矩阵逆的研究统一到了TU-子图的框架之下，使得逆矩阵的每个元素都可以通过枚举特定的生成子图来计算，这在理论上揭示了修正拉普拉斯逆与符号图结构之间的深层联系。该结果不仅推广了Chebotarev–Shamis的矩阵森林定理至符号图情形，也为后续研究符号图上的随机游走、扩散过程及顶点间可达性度量提供了新的代数工具。结论部分强调，通过Moore–Penrose伪逆方法获得的逐项组合公式，连同逆矩阵元素的结构性质，共同构成了符号图修正拉普拉斯矩阵逆的完整组合理论，其中平衡性作为关键的结构不变量在公式中通过权重4^{c(H)}自然体现。