上海理工大学学报  2022, Vol. 44 Issue (6): 588-591 PDF

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）所示。

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

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

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

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

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)$

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

 $\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}}(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)$

 $\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)

 $\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}}_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)$

 $\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}$

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

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

 $\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}$

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)$

 $\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}$

5 结束语

 [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