上海理工大学学报  2022, Vol. 44 Issue (6): 588-591   PDF    
块为K4的cp-图的距离矩阵的行列式和逆
李瑞红, 高月凤     
上海理工大学 理学院,上海 200093
摘要: 基于某些特殊图矩阵的求逆结果提出了一类新的图(块为K4的cp-图)的逆矩阵求解问题,并将其与完全图求逆矩阵作对比,得出了适宜的求解方法,进而得出它的行列式与逆矩阵,均是与图中块数b相关的函数。通过初等行列式变换,求得距离矩阵的特征值和对应重数。
关键词: 块图     距离矩阵     行列式         
The determinant and inverse for the distance matrix of the cp-graph with block of K4
LI Ruihong, GAO Yuefeng     
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Based on the inverse results of some special graph matrices, a new class of graph (cp-graph with block K4) for the inverse matrix solving was put forward. It was compared with the inverse matrix of complete graph, and the appropriate solution method is obtained. Then, its determinant and inverse matrix are obtained, and they are the functions related to the number of blocks in the graph. The eigenvalues and corresponding multiplicity of the distance matrix are obtained by the elementary determinant transformation.
Key words: block graph     distance matrix     determinant     inverse    
1 问题的提出

$ G = (V,E) $ 是一个有限的、连通的、无向的简单图,其中, $ V $ 是顶点集, $ E \subset V \times V $ 是边集。假设图 $ G $ 中存在 $ (u,v) $ 路,那么,称 $ G $ 的2个顶点 $ u $ $ v $ 是连通的。连通是顶点集 $ V $ 上的一个等价关系。因此,可以将顶点集 $ V $ 划分为非空子集 $ {V_1} $ $ {V_2} $ ,···, $ {V_\omega } $ ,使得2个顶点 $ u $ $ v $ 是连通的当且仅当它们属于同一个子集 $ {V_i} $ ,子图 $ G[{V_1}] $ $ G[{V_2}] $ ,···, $ G[{V_\omega }] $ 称为 $ G $ 的连通分支。若 $ G $ 只有一个连通分支,则称 $ G $ 是连通图。将 $ G $ 中顶点 $ i $ $ j $ 相邻记作 $i\sim j$ 。顶点 $ i $ 的度记作 $ {\delta _i} $ $ G $ 中从顶点 $ i $ $ j $ 的距离 $ d(i,j) $ 是从 $ i $ $ j $ 的最短路的长度。图 $ G $ 的距离矩阵是一个 $ n \times n $ 的矩阵,记为 ${\boldsymbol{D}}(G) = [{d_{ij}}]$ ,若 $ i \ne j $ $ {d_{ij}} = d(i,j) $ ;若 $ i = j $ $ {d_{ij}} = 0 $ 。图 $ G $ 的拉普拉斯矩阵是一个 $ n \times n $ 的矩阵,记为 ${\boldsymbol{ L}}(G) = [{l_{ij}}] $ ,若 $ i = j $ $ {l_{ij}} = {\delta _i} $ ;若 $ i \ne j $ $ i \sim j $ $ {l_{ij}} = - 1 $ ;否则为 $ 0 $ 。另外,将 $ n $ 阶的全1矩阵记作 $ {{\boldsymbol{J}}_n} $ $ n $ 阶的单位矩阵记作 $ {{\boldsymbol{I}}_n} $ 。如果一个顶点个数为 $ n $ 的图,它的每个顶点都和其他顶点相邻,那么,称这个图为完全图,记作 $ {{\boldsymbol{K}}_n} $ 。如果图 $ G $ 的顶点集 $ V $ 被分为2个子集 $ {V_1} $ $ {V_2} $ ,使得边集 $ E \subset {V_1} \times {V_2} $ ,那么,称图 $ G $ 为二部图。 $ {T_n} $ 是以2个顶点为基点,由 $ n - 2 $ 个三角形组成的图,如图1(a)所示。

在连通图 $ G $ 中,如果 $ v \in V(G) $ ,且 $ G - v $ 不连通,那么,称 $ v $ $ G $ 的一个割点。 $ G $ 的一个不含割点的极大连通子图称为图的块。如果一个矩阵 ${\boldsymbol{ A}} $ 既是元素非负,又是半正定的,那么,称这个矩阵是双非负的。若一个实对称矩阵 $ {\boldsymbol{A}} $ 可以被分解成 $ {\boldsymbol{A}} = {\boldsymbol{B}}{{\boldsymbol{B}}^{\rm{T}}} $ ,且 $ {\boldsymbol{B}} $ 是非负矩阵,则称 $ {\boldsymbol{A}} $ ${\rm{cp }}$ -矩阵。如果 $ G $ 的每个双非负对称矩阵 $ {\boldsymbol{A}} $ 都是 ${\rm{cp}} $ -矩阵,那么,称图 $ G $ ${\rm{cp}} $ -图。现给出 $ G $ $ {\rm{cp}} $ -图的几个等价条件。


图 1 $ {T_n} $ $ K_4^{(2)} $ $ K_4^{(b)} $ Fig. 1 $ {T_n} $ $ K_4^{(2)} $ $ K_4^{(b)} $

引理1[1]  图 $ G $ 的下列性质等价:

a. $ G $ 是一个 $ {\rm{cp}} $ -图;

b. $ G $ 的每个块都是一个 $ {\rm{cp}} $ -图;

c. $ G $ 的每个块是二部图,或者是 $ {K_4} $ ,或者是 $ {T_n} $

如果图的每一块都是完全二部图,则称它为双块图。对于这种 $ {\rm{cp}} $ -图,Hou等[2]研究了它的距离矩阵的行列式和逆,且距离矩阵的逆是由拉普拉斯矩阵(或者类拉普拉斯矩阵)表示的。对于每一块都是 $ {T_n} $ ${\rm{cp}}$ -图,Das 等[3]给出了该图的距离矩阵的行列式和逆。如果一个图由连通无向图、强连通有向图和强连通混合图组成,那么,称此图为距离定义良好的图。在文献[4]中得出了距离定义良好的图的距离矩阵的行列式和逆。Hou等[5]发现了块为有向圈的图的距离矩阵的行列式和逆。Hou等[6]得到了圈−团图的距离矩阵的逆的公式。其他相关结论见文献[7-11]。

本文主要目的是计算每个块是 $ {K_4} $ 的一类 $ {\rm{cp}} $ -图的距离矩阵的行列式和逆。固定一个顶点 $ n $ ,作为图的中心割点,将图记为 $ K_4^{(b)} $ ,其中, $ b $ $ b $ ≥2)为块的数量,如图1的(b)和(c)所示。

2 单块的行列式和逆

现计算单块的行列式和逆。对 $ K_4^{} $ 的顶点进行适当的标注,如图2所示。


图 2 $ {K_4} $ Fig. 2 $ {K_4} $

K4对应的距离矩阵

$ {\boldsymbol{D}}(G) = \left( {\begin{array}{*{20}{c}} 0&1&1&1 \\ 1&0&1&1 \\ 1&1&0&1 \\ 1&1&1&0 \end{array}} \right) $

定理1 假设 $ {\boldsymbol{D}}(G) $ $ K_4^{} $ 的距离矩阵,那么, $ {\boldsymbol{D}}(G) $ 的行列式和逆分别为

$ \det ({\boldsymbol{D}}(G)) = - 3 \text{,} {{\boldsymbol{D}}^{{{ - }}1}}(G) = \frac{1}{3}{{\boldsymbol{J}}_4} - {{\boldsymbol{I}}_4} $

证明 根据行列式的计算可得 $\det ({\boldsymbol{D}}(G)) = - 3$ $ {\boldsymbol{D}}(G) $ 的逆是由文献[3]的公式 ${(a{{\boldsymbol{J}}_m} + b{{\boldsymbol{I}}_m})^{ - 1}} = \dfrac{{ - a}}{{mab + {b^2}}}{{\boldsymbol{J}}_m} + \dfrac{1}{b}{{\boldsymbol{I}}_m}$ 得到的,即

$\begin{split}& {{\boldsymbol{D}}^{{{ - }}1}}(G) = {({\boldsymbol{J}} - {\boldsymbol{I}})^{ - 1}} = \dfrac{1}{3}{{\boldsymbol{J}}_4} - {{\boldsymbol{I}}_4}{\text{ = }}\\& \qquad\qquad\left( {\begin{array}{*{20}{c}} {{{ - }}\dfrac{2}{3}}&{\dfrac{1}{3}}&{\dfrac{1}{3}}&{\dfrac{1}{3}} \\ {\dfrac{1}{3}}&{{{ - }}\dfrac{2}{3}}&{\dfrac{1}{3}}&{\dfrac{1}{3}} \\ {\dfrac{1}{3}}&{\dfrac{1}{3}}&{{{ - }}\dfrac{2}{3}}&{\dfrac{1}{3}} \\ {\dfrac{1}{3}}&{\dfrac{1}{3}}&{\dfrac{1}{3}}&{{{ - }}\dfrac{2}{3}} \end{array}} \right) \end{split} $
3 矩阵 ${\boldsymbol{ D}}(K_4^{(b)})$ 的行列式和逆

现研究 $ {\boldsymbol{D}}(K_4^{(b)}) $ 的距离矩阵。不失一般性,假设图 $ G $ $ b $ 个块,那么,顶点数 $ n = 3b + 1 $ ,对应的图如图1的(c),它对应的距离矩阵

$ {\boldsymbol{D}}(G) = \left( {\begin{array}{*{20}{c}} {{{\boldsymbol{J}}_3} - {{\boldsymbol{I}}_3}}&{2{{\boldsymbol{J}}_3}}& \cdots &{2{{\boldsymbol{J}}_3}}&{{{\boldsymbol{j}}_3}} \\ {2{{\boldsymbol{J}}_3}}&{{{\boldsymbol{J}}_3} - {{\boldsymbol{I}}_3}}& \cdots &{2{{\boldsymbol{J}}_3}}&{{{\boldsymbol{j}}_3}} \\ \vdots & \vdots &{}& \vdots & \vdots \\ {2{{\boldsymbol{J}}_3}}&{2{{{\boldsymbol{J}}}_3}}& \cdots &{{{\boldsymbol{J}}_3} - {{\boldsymbol{I}}_3}}&{{{\boldsymbol{j}}_3}} \\ {{\boldsymbol{j}}_3^{\rm{T}}}&{{\boldsymbol{j}}_3^{\rm{T}}}& \cdots &{{\boldsymbol{j}}_3^{\rm{T}}}&{\boldsymbol{O}} \end{array}} \right) $

若图 $ G $ 的顶点子集 $ {V'} $ 使得图 $ G - {V'} $ 不连通,则称 $ {V'} $ $ G $ 的顶点割。 $ k $ -顶点割是指有 $ k $ 个顶点的顶点割。图 $ G $ 的所有 $ k $ -顶点割中最小的 $ k $ 称为 $ G $ 的连通度。若 $ G $ 的连通度大于或等于 $ k $ ,则称 $ G $ $ k $ -连通图[7]。若 ${\boldsymbol{A}} = ({a_{ij}})$ 是一个 $ n \times n $ 的矩阵,则 $ {c_{ij}} $ 是指元素 $ {a_{ij}} $ 的代数余子式,代数余子式的和 $Cof({\boldsymbol{A}}) = \displaystyle \sum\limits_{i,j} {{c_{ij}}}$ ,矩阵 $ {\boldsymbol{A}} $ 的伴随矩阵为 $ {{\boldsymbol{A}}^*} = ({c_{ji}}) $

引理2[8-9]   若 $ G $ 是一个连通图,并且具有2连通块 $ {G_1} $ $ {G_2} $ ,···, $ {G_b} $ ,那么,

$ \det ({{\boldsymbol{D}}_G}) = \sum\limits_{i = 1}^b {\det ({{\boldsymbol{D}}_{{G_i}}})} \prod\limits_{j \ne i} {Cof({{\boldsymbol{D}}_{{G_j}}})} $ (1)

定理2 假设 ${\boldsymbol{D}}(G)$ 是图 $ K_4^{(b)} $ 的距离矩阵,那么,

$ \det ({\boldsymbol{D}}) = {( - 1)^b} \times 3b \times {4^{b - 1}} $
$ {{\boldsymbol{D}}^{{{ - }}1}} = - \hat {\boldsymbol{L}} + \frac{1}{{{\lambda _G}}}{\boldsymbol{\beta}} {{\boldsymbol{\beta}} ^{\rm{T}}} $

其中, $\hat {\boldsymbol{L}} = \displaystyle \sum\limits_{i = 1}^b {\dfrac{1}{4}} \hat {\boldsymbol{L}}_i$ $ \hat {\boldsymbol{L}}_i$ 是第 $ i $ 个块(去掉割点)的拉普拉斯矩阵。

$ \hat {\boldsymbol{L}}_i = \left( {\begin{array}{*{20}{c}} {{{\boldsymbol O}_{3 \times 3}}}& \cdots &{{{\boldsymbol O}_{3 \times 3}}}& \cdots &{{{\boldsymbol O}_{3 \times 3}}}&{{{\boldsymbol O}_{3 \times 1}}} \\ \vdots &{}& \vdots &{}& \vdots & \vdots \\ {{{\boldsymbol O}_{3 \times 3}}}& \cdots &{{{\boldsymbol{L}}_i}}& \cdots &{{{\boldsymbol O}_{3 \times 3}}}&{ - {{\boldsymbol{j}}_{3 \times 1}}} \\ \vdots &{}& \vdots &{}& \vdots & \vdots \\ {{{\boldsymbol O}_{3 \times 3}}}& \cdots &{{{\boldsymbol O}_{3 \times 3}}}& \cdots &{{{\boldsymbol O}_{3 \times 3}}}&{{{\boldsymbol O}_{3 \times 1}}} \\ {{{\boldsymbol O}_{1 \times 3}}}& \cdots &{ - {\boldsymbol{j}}_{1 \times 3}^{\rm{T}}}& \cdots &{{{\boldsymbol O}_{1 \times 3}}}&3 \end{array}} \right) . $
$ \begin{split}& {{\boldsymbol{L}}_i} = \left( {\begin{array}{*{20}{c}} 3&{ - 1}&{ - 1} \\ { - 1}&3&{ - 1} \\ { - 1}&{ - 1}&3 \end{array}} \right) \text{,} {\lambda _G} = \frac{3}{4}{{b}} \end{split}$
$ {{\boldsymbol{\beta}} ^{\rm{T}}} = \left( {\frac{1}{4},\frac{1}{4},\frac{1}{4},\cdots,\frac{1}{4},\frac{{4 - 3b}}{4}} \right) $

证明 图 $ K_4^{(b)} $ 的每个块的行列式 $ \det ({{\boldsymbol{D}}_i}) = - 3 $ ,每个块的代数余子式的和

$\begin{split} Cof({{\boldsymbol{D}}_k}) =& \sum\limits_{i,j} {c{}_{ij}} = {{\boldsymbol{j}}^{\rm{T}}}{\boldsymbol{D}}_k^*{\boldsymbol{j}} = \det ({{\boldsymbol{D}}_k}){{\boldsymbol{j}}^{\rm{T}}}{\boldsymbol{D}}_k^{ - 1}{\boldsymbol{j}} = \\&( - 3) \times \frac{4}{3} = - 4 \end{split} $

由式(1)可知,对于 ${\boldsymbol{D}}(G)$

$ \det ({\boldsymbol{D}}) = \sum\limits_{i = 1}^b {( - 3)} \prod\limits_{j \ne i} {( - 4)} = {( - 1)^b} \times 3b \times {4^{b - 1}} $

根据文献[12]的定理3给出的块图(每个分块为完全图,顶点数不必相同)的求逆公式可知,当分块都为 $ K_4^{} $ 时,可得

$ {{\boldsymbol{D}}^{{{ - }}1}} = \hat {\boldsymbol{L}} + \frac{1}{{{\lambda _G}}}{\boldsymbol{\beta}} {{\boldsymbol{\beta}} ^{\rm{T}}} $
4 矩阵 ${\boldsymbol{D}}(K_4^{(b)})$ 的谱性质

现研究 ${\boldsymbol{D}}(K_4^{(b)})$ 的谱性质。

定理3 假设 $ {\boldsymbol{D}}(G) $ 是图 $ K_4^{(b)} $ 的距离矩阵。那么,图 $ G $ 的特征值及对应的重数如表1所示.


表 1 特征值及重数 Table 1 Eigenvalues and multiplicities

证明 根据 $ G $ 的距离矩阵,有

$ \begin{split}& \lambda {\boldsymbol{I}} - {\boldsymbol{D}}(G) = \\ &\left( {\begin{array}{*{20}{c}} {\lambda {{\boldsymbol{I}}_3} - {{\boldsymbol{J}}_3} + {{\boldsymbol{I}}_3}} & { - 2{{\boldsymbol{J}}_3}} & \cdots & { - 2{{\boldsymbol{J}}_3}} & { - {{\boldsymbol{j}}_3}} \\ { - 2{{\boldsymbol{J}}_3}} & {\lambda {{\boldsymbol{I}}_3} - {{\boldsymbol{J}}_3} + {{\boldsymbol{I}}_3}} & \cdots & { - 2{{\boldsymbol{J}}_3}} & { - {{\boldsymbol{j}}_3}} \\ \vdots & \vdots & {} & \vdots & \vdots \\ { - 2{{\boldsymbol{J}}_3}} & { - 2{{\boldsymbol{J}}_3}} & \cdots & {\lambda {{\boldsymbol{I}}_3} - {{\boldsymbol{J}}_3} + {{\boldsymbol{I}}_3}} & { - {{\boldsymbol{j}}_3}} \\ { - {\boldsymbol{j}}_3^{\rm{T}}} & { - {\boldsymbol{j}}_3^{\rm{T}}} & \cdots & { - {\boldsymbol{j}}_3^{\rm{T}}} & \lambda \end{array}} \right) \end{split} $

令此矩阵行块的标签为 $ {{\boldsymbol{R}}_1} $ $ {{\boldsymbol{R}}_2} $ ,···, $ {{\boldsymbol{R}}_b} $ ;列块的标签为 $ {{\boldsymbol{C}}_1} $ $ {{\boldsymbol{C}}_2} $ ,···, $ {{\boldsymbol{C}}_b} $ 。按照下面的算法求它的特征多项式。

a. ${{\boldsymbol{R}}_1} \to \displaystyle \sum\limits_{i = 1}^b {{{\boldsymbol{R}}_i}}$ $ {{\boldsymbol{C}}_j} \to {{\boldsymbol{C}}_j} - {{\boldsymbol{C}}_1} $ $ j = 2,3, \cdots ,b $

b. 对于每个行块,将块内所有行加到第1行,块内的第1列的负一倍加到第2,3列;

c.交换矩阵第2行和最后1行以及第2列和最后1列。

得到矩阵

$ \left( {\begin{array}{*{20}{c}} {{{\boldsymbol{D}}_1}}&{{{\boldsymbol O}_{3 \times 3}}}& \cdots &{{{\boldsymbol O}_{3 \times 3}}}&{{{\boldsymbol O}_{3 \times 1}}} \\ {{{\boldsymbol{D}}_3}}&{{{\boldsymbol{D}}_2}}& \cdots &{{{\boldsymbol O}_{3 \times 3}}}&{{{\boldsymbol O}_{3 \times 1}}} \\ \vdots & \vdots &{}& \vdots & \vdots \\ {{{\boldsymbol{D}}_3}}&{{{\boldsymbol O}_{3 \times 3}}}& \cdots &{{{\boldsymbol{D}}_2}}&{{{\boldsymbol O}_{3 \times 1}}} \\ {\boldsymbol{d}}&{{{\boldsymbol O}_{1 \times 3}}}& \cdots &{{{\boldsymbol O}_{1 \times 3}}}&{\lambda + 1} \end{array}} \right) $

其中,

$ {{\boldsymbol{D}}_1} = \left( {\begin{array}{*{20}{c}} {\lambda + 4 - 6b}&{ - 3b}&0 \\ { - 1}&\lambda &0 \\ {1 - 2b}&{ - b}&{\lambda + 1} \end{array}} \right) $
$ {{\boldsymbol{D}}_2} = \left( {\begin{array}{*{20}{c}} {\lambda + 4 - 6b}&0&0 \\ {1 - 2b}&{\lambda + 1}&0 \\ {1 - 2b}&0&{\lambda + 1} \end{array}} \right) $
$ {{\boldsymbol{D}}_3} = \left( {\begin{array}{*{20}{c}} { - 6}&{ - 3}&0 \\ { - 2}&{ - 1}&0 \\ { - 2}&{ - 1}&0, \end{array}} \right),\;\;d = \left( {\begin{array}{*{20}{c}} 0&{ - b}&0 \end{array}} \right) $

整理可得, $ {\boldsymbol{D}}(G) $ 的特征多项式

$ \begin{split}& {(\lambda + 1)^{2b}}{(\lambda + 4 - 6b)^{b - 1}}(\lambda - (3b - 2 + \sqrt {9{b^2} - 9b + 4} ))\cdot\\&\qquad(\lambda - (3b - 2 - \sqrt {9{b^2} - 9b + 4} )) \end{split} $

由此得出 $ {\boldsymbol{D}}(G) $ 的特征值及重数。

5 结束语

本文得到了分块为 $ K_4^{} $ $ {\rm{cp}} $ -图的距离矩阵的行列式和逆的公式,然而,图类仍然是比较特殊的,研究的方法也较为单一。作者将考察更多图类的距离矩阵,在更一般的图中找出距离矩阵的行列式和逆矩阵,进一步研究逆矩阵的应用和距离矩阵特征值的性质。希望这个结果可以为别的类似的块图提供解决方案。

参考文献
[1]
BERMAN A, SHAKED-MONDERER N. Completely positive matrices[M]. River Edge: World Scienfic, 2003.
[2]
HOU Y P, SUN Y J. Inverse of the distance matrix of a bi-block graph[J]. Linear and Multilinear Algebra, 2016, 64(8): 1509-1517. DOI:10.1080/03081087.2015.1099599
[3]
DAS J, JAYARAMAN S, MOHANTY S. Distance matrix of a class of completely positive graphs: determinant and inverse[J]. Special Matrices, 2020, 8(1): 160-171. DOI:10.1515/spma-2020-0109
[4]
ZHOU H. The inverse of the distance matrix of a distance well-defined graph[J]. Linear Algebra and its Applications, 2017, 517: 11-29. DOI:10.1016/j.laa.2016.12.008
[5]
HOU Y P, CHEN J. Inverse of the distance matrix of a cactoid digraph[J]. Linear Algebra and its Applications, 2015, 475: 1-10. DOI:10.1016/j.laa.2015.02.002
[6]
HOU Y P, FANG A X, SUN Y J. Inverse of the distance matrix of a cycle-clique graph[J]. Linear Algebra and its Applications, 2015, 485: 33-46. DOI:10.1016/j.laa.2015.07.022
[7]
苏静, 马飞, 姚兵. 2-连通图的一些等价定义[J]. 东北师大学报(自然科学版), 2017, 49(1): 33-37. DOI:10.16163/j.cnki.22-1123/n.2017.01.007
[8]
GRAHAM R L, HOFFMAN A J, HOSOYA H. On the distance matrix of a directed graph[J]. Journal of Graph Theory, 1977, 1(1): 85-88. DOI:10.1002/jgt.3190010116
[9]
BAPAT R B, LAL A K, PATI S. A q-analogue of the distance matrix of a tree [J]. Linear Algebra and its Applications, 2006, 416(2/3): 799-814.
[10]
BAPAT R B, LAL A K, PATI S. The distance matrix of a bidirected tree[J]. Electronic Journal of Linear Algebra, 2009, 18: 233-245.
[11]
ZHOU H, DING Q, JIA R L. Inverse of the distance matrix of a weighted cactoid digraph[J]. Applied Mathematics and Computation, 2019, 362: 124552. DOI:10.1016/j.amc.2019.06.066
[12]
BAPAT R B, SIVASUBRAMANIAN S. Inverse of the distance matrix of a block graph[J]. Linear and Multilinear Algebra, 2011, 59(12): 1393-1397. DOI:10.1080/03081087.2011.557374