长安大学理学院，陕西 西安

收稿日期：2024年1月14日；录用日期：2024年2月4日；发布日期：2024年4月11日

摘要

本文利用矩阵的低秩性、分块性等性质给出了星图的邻接矩阵、关联矩阵、距离矩阵、拉普拉斯矩阵和无符号拉普拉斯矩阵的Moore-Penrose广义逆。以上结论对进一步研究星图的代数性质提供了理论支撑，同时对研究其他图类的相关矩阵的广义逆提供了理论参考。

关键词

星图，分块矩阵，Moore-Penrose广义逆

Moore-Penrose Inverses of the Related Matrices of Star Graphs

Yuhao Wang

School of Science, Chang’an University, Xi’an Shaanxi

Received: Jan. 14^th, 2024; accepted: Feb. 4^th, 2024; published: Apr. 11^th, 2024

ABSTRACT

Based on the properties of the low rank, partitioned matrix structure, we give the explicit form for the Moore-Penrose inverse of the adjacency matrix, incidence matrix, distance matrix, Laplacian matrix and signless-Laplacian matrix of star graphs, which provides theoretical support for further study of the algebraic properties of star graphs and theoretical aid for the study of the generalized inverse for matrices of other graphs.

Keywords:Star Graph, Block Matrix, Moore-Penrose Inverse

Copyright © 2024 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

设图G是一个无向简单图，其顶点集为 $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)={\left(a_{ij}\right)}_{n\times n}$ ，其中：当顶点 $v_i$ 与 $v_j$ 相邻时， $a_{ij}=1$ ；反之 $a_{ij}=0$ 。图G的点边关联矩阵 $M\left(G\right)={\left(m_{ij}\right)}_{n\times m}$ ，当顶点 $v_i$ 与 $e_j$ 关联时， $m_{ij}=1$ ；反之 $m_{ij}=0$ 。图G的距离矩阵 $D={\left(d_{ij}\right)}_{n\times n}$ ，其中 $d_{ij}$ 表示顶点 $v_i$ 与 $v_j$ 之间的最短距离。图G的度矩阵 $\bar{D}\left(G\right)=diag\left(d_1,d_2,\cdots ,d_n\right)$ ，其中 $d_i$ 表示顶点 $v_i$ 的邻点数。图G的拉普拉斯矩阵 $L\left(G\right)=\bar{D}\left(G\right)-A\left(G\right)$ 。图G的无符号拉普拉斯矩阵 $Q\left(G\right)=\bar{D}\left(G\right)+A\left(G\right)$ 。

设图 $\Gamma$ 是一个有向简单图，其顶点集为 $V\left(\Gamma \right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ ，边集为 $E\left(\Gamma \right)=\left\{e_1,e_2,\cdots ,e_m\right\}$ 。定义图 $\Gamma$ 的点边关联矩阵 $H\left(\Gamma \right)={\left(h_{ij}\right)}_{n\times m}$ ，当顶点 $v_i$ 是有向边 $e_j$ 的起点时， $h_{ij}=-1$ ；当顶点 $v_i$ 是有向边 $e_j$ 的终点时， $h_{ij}=1$ ；反之 $v_i$ 与 $e_j$ 不关联时， $h_{ij}=0$ 。

对任意的 $A\in {ℝ}^{m\times n}$ ，如果存在 $X\in {ℝ}^{n\times m}$ ，满足下面4个条件：

$AXA=A;XAX=X;{\left(AX\right)}^T=AX;{\left(XA\right)}^T=XA,$

则称X是A的Moore-Penrose广义逆矩阵 [1] ，记为 $A^{+}$ 。当矩阵A可逆时，容易证得 $A^{+}=A^{-1}$ ；当A为行满秩矩阵时，有右逆 $A_R^{-1}=A^T{\left(A{A}^T\right)}^{-1}$ ，为列满秩矩阵时，有左逆 $A_L^{-1}={(A^{T}A)}^{-1}{A}^T$ ，容易证明此时A的左逆或右逆就是A的Moore-Penrose广义逆。反之当A既不行满秩又不列满秩时可以使用满秩分解和奇异值分解去求解 $A^{+}$ ，但事实上，使用上述两种方法得到的广义逆的表示形式可能非常复杂，图的相关矩阵对于研究图的性质有关键作用，因此给出图矩阵广义逆的简洁表示形式是非常有意义的。

近几十年来，图相关矩阵的广义逆的研究受到了广泛关注，Bapat等人给出了距离正则图和完全多部图的关联矩阵的Moore-Penrose广义逆，接着又给出了偶数个顶点的轮图的距离矩阵的求逆公式，详见文献 [2] [3] [4] 。Hessert和Mallik给出了图的无符号拉普拉斯矩阵和边拉普拉斯矩阵的Moore-Penrose广义逆 [5] ，接着又给出了单圈图关联矩阵的逆 [6] 。Alazemi等人考虑对对称矩阵A进行公平划分，得到了

$A^{+}\left(\text{Π}\right)={\left(A\left(\text{Π}\right)\right)}^{+}$ 的充分条件，从而利用 ${\left(A\left(\text{Π}\right)\right)}^{+}$ 重构出 $A^{+}$ ，极大地简化了Moore-Penrose广义逆的求解 [7] 。本文依据星图相关矩阵的结构特点，利用分块矩阵给出了星图邻接矩阵、关联矩阵、距离矩阵、拉普拉斯矩阵以及无符号拉普拉斯的Moore-Penrose广义逆的具体表示形式，对进一步研究星图的代数性质提供了理论支撑，同时对研究其他图类的相关矩阵的广义逆提供了理论参考。

2. 预备知识

设A为实数域上的n阶分块矩阵，分块划分为 $\text{Π}=\left(X_1,\cdots ,X_m\right)$ ，其中每一个 $X_i$ 均为非空不交集合，且有 $X_1\cup \cdots \cup X_m=\left\{1,\cdots ,n\right\}$ ，矩阵A的每一块 $A_{ij}\in {ℝ}^{\left|X_i\right|\times \left|X_j\right|}\left(1\le i,j\le m\right)$ ，即：

$A=\left(\begin{array}{ccc}{A}_{11}& \cdots & A_{1m}\\ ⋮& & ⋮\\ A_{m1}& \cdots & A_{mm}\end{array}\right).$

令 $A\left(\text{Π}\right)\in {ℝ}^{m\times m}$ 为划分 $\text{Π}$ 对应的商矩阵， $A\left(\text{Π}\right)$ 中的元素 $A{\left(\text{Π}\right)}_{ij}$ 等于分块矩阵 $A_{ij}$ 的平均行和。如果矩阵A的每一个分块 $A_{ij}\left(1\le i,j\le m\right)$ 每一行的和都等于这个分块矩阵的平均行和，则称划分 $\text{Π}$ 是矩阵A的一个公平划分。

定理2.1指出对于对称矩阵A，如果 $\text{Π}$ 是矩阵A的一个公平划分，则 $\text{Π}$ 也是A的Moore-Penrose广义逆矩阵 $A^{+}$ 的一个公平划分。

定理2.1 [7] 设 $A\in {ℝ}^{m\times n}$ 且 $A^T=A$ ， $\text{Π}=\left(X_1,\cdots ,X_m\right)$ 是矩阵A的一个公平划分，对应的商矩阵为 $A\left(\text{Π}\right)$ ，且 $X=\text{diag}\left(\left|X_1\right|,\cdots ,\left|X_m\right|\right)$ 。则 $\text{Π}$ 也是 $A^{+}$ 的一个公平划分，对应的商矩阵

$A^{+}\left(\Pi \right)=X^{-1\text{/}2}{\left(X^{1\text{/}2}A\text{}\left(\Pi \right)\text{}\text{}{X}^{-1\text{/}2}\right)}^{+}{X}^{1\text{/}2}\text{.}$

引理2.1给出了一个 $A^{+}\left(\text{Π}\right)$ 和 ${\left(A\left(\text{Π}\right)\right)}^{-1}$ 等价的充分条件。

引理2.1 [7] 设A是一个对称矩阵， $\text{Π}=\left(X_1,\cdots ,X_m\right)$ 是矩阵A的一个公平划分，对应的商矩阵为 $A\left(\text{Π}\right)$ 。如果 $A\left(\text{Π}\right)$ 可逆，则 $A^{+}\left(\text{Π}\right)$ 也可逆且 $A^{+}\left(\text{Π}\right)={\left(A\left(\text{Π}\right)\right)}^{-1}$ 。

引理2.2~2.4给出了Moore-Penrose广义逆的相关性质和计算公式。

引理2.2 [8] 设 $A\in {ℝ}^{m\times n}$ ， $A^{+}$ 为矩阵A的Moore-Penrose广义逆，则有 ${\left(A{A}^T\right)}^{+}={\left(A^{+}\right)}^T{A}^{+}$ 。

引理2.3 [8] 设A是一个对称矩阵，则 $A^{-1}$ 或 $A^{+}$ 也是对称矩阵。

引理2.4 [8] 设 $A\in {ℝ}^{m\times n}$ ，且有满秩分解 $A=FG$ ，其中 $F\in {ℝ}^{m\times r},G\in {ℝ}^{r\times n}$ ， $r=r\left(A\right)=r\left(F\right)=r\left(G\right)$ 。则有 $A^{+}=G^T{\left(F^{T}A{G}^T\right)}^{-1}{F}^T$ 。

引理2.5给出了图的拉普拉斯矩阵、无符号拉普拉斯矩阵和关联矩阵之间的关系。

引理2.5 [9] 对于无向简单图G，给其每条边赋方向，记为图 $\Gamma$ ，则有

$Q\left(G\right)=M\left(G\right)M{\left(G\right)}^T,L\left(G\right)=H\left(\Gamma \right)H{\left(\Gamma \right)}^T.$

引理2.6给出了一种特殊的矩阵满秩分解方法。

引理2.6 [10] 设 $A\in {ℝ}^{m\times n}$ ， $rank\left(A\right)=r$ ，则矩阵A存在一个满秩分解 $A=FG$ ，其中， $F\in {ℝ}^{m\times r}$ ， $G\in {ℝ}^{r\times n}$ ，矩阵G为对A施行初等行变换后得到的行最简形矩阵的前r行，令 $j_1,j_2,\cdots ,j_r$ 代表G每一行第一个1所在的列数，矩阵F为A的第 $j_1,j_2,\cdots ,j_r$ 个列向量所构成的矩阵。

在下文的描述中， $j_n$ 代表长度为n的全1列向量， $I_n$ 代表n阶单位矩阵， $J_{m\times n}$ 代表 $m\times n$ 阶全1矩阵， $O_{m\times n}$ 代表 $m\times n$ 阶全0矩阵。

3. 主要结果

命题3.1 设A是实数域上的n阶对称矩阵，如果矩阵A的某些行(列)完全相同，即： $a_{it}=a_{jt}=\cdots =a_{mt}$ ，其中 $i,j,\cdots ,m\in \left\{1,2,\cdots ,n\right\},t=1,2,\cdots ,n,$ 则 $A^{+}$ 的那些行(列)对应也完全相同。

证明：由引理2.6，实数域上的n阶对称矩阵A存在一个满秩分解 $A=FG$ ，其中矩阵G为对A施行初等行变换后得到的行最简形矩阵的前r行。假设矩阵A的第i行和第j行相等，对任意的 $1\le k\le n,$ 由于 $A_{ik}=A_{jk}$ 且 $A=A^T$ ，有 $A_{ki}=A_{kj}$ 。又因G为对A施行初等行变换后得到，故有 ${\left(G^T\right)}_{ik}={\left(G^T\right)}_{jk}$ 。由引理2.4，对任意的 $1\le t\le n$ ， $A^{+}$ 的第i行和第j行元素

${\left(A^{+}\right)}_{i,t}={\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(G^T\right)}_{ik}}{\left({\left(F^{T}A{G}^T\right)}^{-1}{F}^T\right)}_{kt}={\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(G^T\right)}_{jk}}{\left({\left(F^{T}A{G}^T\right)}^{-1}{F}^T\right)}_{kt}={\left(A^{+}\right)}_{j,t}.$

于是A的广义逆矩阵 $A^{+}$ 的第i行和第j行元素对应相等，命题得证。

星图由一个顶点连上若干个孤立顶点得到，如下图G所示。给图G的每条边加上方向变为有向图，如下图 $\Gamma$ 所示。

图1. (a) 无向星图 $G$ 和(b) 有向星图 $\Gamma$

定理3.1给出了星图的邻接矩阵的Moore-Penrose广义逆的分块表示。

定理3.1 设 $G=K_{1,n-1}$ 是一个有n个顶点的无向星图，则其邻接矩阵A的Moore-Penrose广义逆为

$A^{+}=\left(\begin{array}{cc}0& \frac{1}{n-1}{j}_{n-1}^T\\ \frac{1}{n-1}{j}_{n-1}& O_{(n-1)\times (n-1)}\end{array}\right)$ .

证明：根据图1中G的顶点标号，星图 $K_{1,n-1}$ 的邻接矩阵有以下形式：

$A={\left(\begin{array}{ccccc}0& 1& 1& \cdots & 1\\ 1& 0& 0& \cdots & 0\\ 1& 0& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& 0& 0& \cdots & 0\end{array}\right)}_{n\times n}={\left(\begin{array}{cc}0& j_{n-1}^T\\ j_{n-1}& O_{(n-1)\times (n-1)}\end{array}\right)}_{n\times n}$

显然，矩阵A的后 $n-1$ 行(列)相同。考虑对A进行分块划分，划分 $\Pi =\left(X_1,X_2\right),X_1=\left\{1\right\},$ $X_2=\left\{2,3,\cdots ,n\right\}$。容易验证划分 $\text{Π}$ 是一个公平划分，对应的商矩阵

$A\left(\text{Π}\right)=\left(\begin{array}{cc}0& n-1\\ 1& 0\end{array}\right).$

易得商矩阵 $A\left(\text{Π}\right)$ 可逆且有

${\left(A\left(\text{Π}\right)\right)}^{-1}=\left(\begin{array}{cc}0& 1\\ \frac{1}{n-1}& 0\end{array}\right).$

由定理2.1和引理2.1，划分 $\text{Π}$ 也是 $A^{+}$ 的一个公平划分且有

$A^{+}\left(\text{Π}\right)={\left(A\left(\text{Π}\right)\right)}^{-1}=\left(\begin{array}{cc}0& 1\\ \frac{1}{n-1}& 0\end{array}\right).$

由命题3.1， $A^{+}$ 的后 $n-1$ 行(列)也相同，因此利用 $A^{+}\left(\text{Π}\right)$ 重构出 $A^{+}$ 如下：

$A^{+}=\left(\begin{array}{ccccc}0& \frac{1}{n-1}& \frac{1}{n-1}& \cdots & \frac{1}{n-1}\\ \frac{1}{n-1}& 0& 0& \cdots & 0\\ \frac{1}{n-1}& 0& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ \frac{1}{n-1}& 0& 0& \cdots & 0\end{array}\right)=\left(\begin{array}{cc}0& \frac{1}{n-1}{j}_{n-1}^T\\ \frac{1}{n-1}{j}_{n-1}& O_{(n-1)\times (n-1)}\end{array}\right).$

定理得证。

定理3.2给出了星图的关联矩阵的Moore-Penrose广义逆的分块表示。

定理3.2 设 $G=K_{1,n-1}$ 是一个有n个顶点的无向星图，则其关联矩阵M的Moore-Penrose广义逆为

$M^{+}={\left(\begin{array}{cc}\frac{1}{n}{j}_{n-1}& -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right)}_{(n-1)\times n}$ .

证明：由图1中G的顶点及边的标号，其关联矩阵可记为

$M={\left(\begin{array}{cccc}1& 1& \cdots & 1\\ 1& 0& \cdots & 0\\ 0& 1& \ddots & ⋮\\ ⋮& \ddots & \ddots & 0\\ 0& \cdots & 0& 1\end{array}\right)}_{n\times (n-1)}={\left(\begin{array}{c}{j}_{n-1}^T\\ I_{n-1}\end{array}\right)}_{n\times (n-1)}$ .

易证M为列满秩矩阵，故其有左逆，且 $M_L^{-1}={\left(M^{T}M\right)}^{-1}{M}^T$ ，又 $M^{+}=M_L^{-1}$ ，得

$\begin{array}{l}{M}^{+}={\left(M^{T}M\right)}^{-1}{M}^T={\left[\begin{array}{cc}\left(\begin{array}{cc}{j}_{n-1}& I_{n-1}\end{array}\right)& \left(\begin{array}{c}{j}_{n-1}^T\\ I_{n-1}\end{array}\right)\end{array}\right]}^{-1}\left(\begin{array}{cc}{j}_{n-1}& I_{n-1}\end{array}\right)\\ ={\left(J_{n-1}+I_{n-1}\right)}^{-1}\left(\begin{array}{cc}{j}_{n-1}& I_{n-1}\end{array}\right)\\ =\left(-\frac{1}{n}{J}_{n-1}+I_{n-1}\right)\left(\begin{array}{cc}{j}_{n-1}& I_{n-1}\end{array}\right)\\ =\left(\begin{array}{cc}\frac{1}{n}{j}_{n-1}& -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right).\end{array}$

定理得证。

定理3.3给出了星图的距离矩阵的Moore-Penrose广义逆的分块表示。

定理3.3 设 $G=K_{1,n-1}$ 是一个有n个顶点的无向星图，则其距离矩阵D的Moore-Penrose广义逆为

$D^{+}=\left(\begin{array}{cc}\frac{2\left(2-n\right)}{n-1}& \frac{1}{n-1}{j}_{n-1}^T\\ \frac{1}{n-1}{j}_{n-1}& \frac{1}{2}\left(\frac{1}{n-1}{J}_{n-1}-I_{n-1}\right)\end{array}\right)$ .

证明：根据图1中G的顶点标号，星图 $K_{1,n-1}$ 的距离矩阵有以下形式：

$D={\left(\begin{array}{ccccc}0& 1& 1& \cdots & 1\\ 1& 0& 2& \cdots & 2\\ 1& 2& 0& \ddots & ⋮\\ ⋮& ⋮& \ddots & \ddots & 2\\ 1& 2& \cdots & 2& 0\end{array}\right)}_{n\times n}={\left(\begin{array}{cc}0& j_{n-1}^T\\ j_{n-1}& 2\left(J_{n-1}-I_{n-1}\right)\end{array}\right)}_{n\times n}$ ,

通过计算其行列式易证距离矩阵D为可逆矩阵，因而 $D^{+}=D^{-1}$ 。令

$D^{-1}=\left(\begin{array}{cc}m& N\\ P& Q\end{array}\right)$ ,

则有

$\begin{array}{l}D{D}^{-1}=\left(\begin{array}{cc}0& j_{n-1}^T\\ j_{n-1}& 2\left(J_{n-1}-I_{n-1}\right)\end{array}\right)\left(\begin{array}{cc}m& N\\ P& Q\end{array}\right)\\ =\left(\begin{array}{cc}{j}_{n-1}^{T}P& j_{n-1}^{T}Q\\ m{j}_{n-1}+2\left(J_{n-1}-I_{n-1}\right)P& j_{n-1}N+2\left(J_{n-1}-I_{n-1}\right)Q\end{array}\right)\\ =\left(\begin{array}{cc}1& O_{1\times (n-1)}\\ O_{(n-1)\times 1}& I_{n-1}\end{array}\right)\\ =I_n.\end{array}$

因而

$\{\begin{array}{c}{j}_{n-1}^{T}P=1\\ j_{n-1}^{T}Q=O_{1\times (n-1)}\\ m{j}_{n-1}+2\left(J_{n-1}-I_{n-1}\right)P=O_{(n-1)\times 1}\\ j_{n-1}N+2\left(J_{n-1}-I_{n-1}\right)Q=I_{n-1}\end{array}$ $\begin{array}{l}(1)\\ (2)\\ (3)\\ (\; 4\; )\end{array}$

将(1)代入(3)中，得 $m{j}_{n-1}+2j_{n-1}-2P=O_{(n-1)\times 1}$ ，解得 $P=\frac{m+2}{2}{j}_{n-1}$ ，代入(1)中有

$j_{n-1}^{T}P=j_{n-1}^T\cdot \frac{m+2}{2}{j}_{n-1}=\frac{m+2}{2}\cdot \left(n-1\right)=1$ ,

得 $m=\frac{2\left(2-n\right)}{n-1}$ ， $P=\frac{1}{n-1}{j}_{n-1}$ 。又因距离矩阵D为对称矩阵，由引理2.3， $D^{-1}$ 也是对称矩阵，得 $N=P^T=\frac{1}{n-1}{j}_{n-1}^T$ ，代入(4)中有

$j_{n-1}N+2\left(J_{n-1}-I_{n-1}\right)Q=\frac{1}{n-1}{J}_{n-1}-2Q=I_{n-1}$ ,

得 $Q=\frac{1}{2}\left(\frac{1}{n-1}{J}_{n-1}-I_{n-1}\right)$ 。因而

$D^{+}=D^{-1}=\left(\begin{array}{cc}\frac{2\left(2-n\right)}{n-1}& \frac{1}{n-1}{j}_{n-1}^T\\ \frac{1}{n-1}{j}_{n-1}& \frac{1}{2}\left(\frac{1}{n-1}{J}_{n-1}-I_{n-1}\right)\end{array}\right)$ ,

定理得证。

定理3.4给出了星图的无符号拉普拉斯矩阵矩阵的Moore-Penrose广义逆的分块表示。

定理3.4 设 $G=K_{1,n-1}$ 是一个有n个顶点的无向星图，则其无符号拉普拉斯矩阵Q的Moore-Penrose广义逆为

$Q^{+}=\left(\begin{array}{cc}\frac{n-1}{n^2}& \frac{1}{n^2}{j}_{n-1}^T\\ \frac{1}{n^2}{j}_{n-1}& -\frac{n+1}{n^2}{J}_{n-1}+I_{n-1}\end{array}\right)$ .

证明：由引理2.2和引理2.5，得 $Q=M{M}^T$ ， $Q^{+}={\left(M^{+}\right)}^T{M}^{+}$ 。又由定理3.2得

$M^{+}={\left(\begin{array}{cc}\frac{1}{n}{j}_{n-1}& -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right)}_{(n-1)\times n}$ ,

故有

$\begin{array}{l}{Q}^{+}={\left(M^{+}\right)}^T{M}^{+}=\left(\begin{array}{c}\frac{1}{n}{j}_{n-1}^T\\ -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right)\left(\begin{array}{cc}\frac{1}{n}{j}_{n-1}& -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right)\\ =\left(\begin{array}{cc}\frac{n-1}{n^2}& \frac{1}{n^2}{j}_{n-1}^T\\ \frac{1}{n^2}{j}_{n-1}& -\frac{n+1}{n^2}{J}_{n-1}+I_{n-1}\end{array}\right).\end{array}$

定理得证。

定理3.5给出了星图的拉普拉斯矩阵矩阵的Moore-Penrose广义逆的分块表示。

定理3.5 设 $G=K_{1,n-1}$ 是一个有n个顶点的无向星图， $\Gamma$ 是对G的每条边赋方向的有向星图，则G的拉普拉斯矩阵L的Moore-Penrose广义逆为

$L^{+}=\left(\begin{array}{cc}\frac{n-1}{n^2}& -\frac{1}{n^2}{j}_{n-1}^T\\ -\frac{1}{n^2}{j}_{n-1}& -\frac{n+1}{n^2}{J}_{n-1}+I_{n-1}\end{array}\right)$ .

证明：根据图1中 $\Gamma$ 的顶点及有向边标号，得图 $\Gamma$ 的关联矩阵H为

$H=\left(\begin{array}{cccc}-1& -1& \cdots & -1\\ 1& 0& \cdots & 0\\ 0& 1& \ddots & ⋮\\ ⋮& \ddots & \ddots & 0\\ 0& \cdots & 0& 1\end{array}\right)=\left(\begin{array}{c}-j_{n-1}^T\\ I_{n-1}\end{array}\right)$ .

易证H为列满秩矩阵，故其有左逆，且 $H_L^{-1}={\left(H^{T}H\right)}^{-1}{H}^{T}H$ 。又 $H^{+}=H_L^{-1}$ ，得

$\begin{array}{l}{H}^{+}={\left(H^{T}H\right)}^{-1}{H}^T={\left[\begin{array}{cc}\left(\begin{array}{cc}-j_{n-1}& I_{n-1}\end{array}\right)& \left(\begin{array}{c}-j_{n-1}^T\\ I_{n-1}\end{array}\right)\end{array}\right]}^{-1}\left(\begin{array}{cc}-j_{n-1}& I_{n-1}\end{array}\right)\\ ={\left(J_{n-1}+I_{n-1}\right)}^{-1}\left(\begin{array}{cc}-j_{n-1}& I_{n-1}\end{array}\right)\\ =\left(-\frac{1}{n}{J}_{n-1}+I_{n-1}\right)\left(\begin{array}{cc}-j_{n-1}& I_{n-1}\end{array}\right)=\left(\begin{array}{cc}-\frac{1}{n}{j}_{n-1}& -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right).\end{array}$

由引理2.2和引理2.5，得 $L=H{H}^T$ ， $L^{+}={\left(H^{+}\right)}^T{H}^{+}$ ，故有

$\begin{array}{l}{L}^{+}={\left(H^{+}\right)}^T{H}^{+}=\left(\begin{array}{c}-\frac{1}{n}{j}_{n-1}^T\\ -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right)\left(\begin{array}{cc}-\frac{1}{n}{j}_{n-1}& -\frac{1}{n}{J}_{n-1}+I_{n-1}\end{array}\right)\\ =\left(\begin{array}{cc}\frac{n-1}{n^2}& -\frac{1}{n^2}{j}_{n-1}^T\\ -\frac{1}{n^2}{j}_{n-1}& -\frac{n+1}{n^2}{J}_{n-1}+I_{n-1}\end{array}\right).\end{array}$

定理得证。

例3.1 如图2所示， $K_{1,7}$ 为8个顶点的无向星图， ${\Gamma }_{1,7}$ 是将 $K_{1,7}$ 每条边赋方向后的有向星图。

图2. (a) 无向星图 $K_{1,7}$ ；(b) 有向星图 ${\Gamma }_{1,7}$

由定理3.1~3.5，可以得到下表1结果：

表1. 星图 $K_{1,7}$ 的相关矩阵及其Moore-Penrose广义逆

4. 结语

图的相关矩阵对于研究图的代数性质有关键作用，本文借助分块矩阵给出了星图的邻接矩阵、关联矩阵、距离矩阵、拉普拉斯矩阵和无符号拉普拉斯矩阵的Moore-Penrose广义逆的具体结果，并给出了计算例子。后续将深入推广此方法，研究其他图类相关矩阵的Moore-Penrose广义逆。

文章引用

王玉浩. 星图相关矩阵的Moore-Penrose广义逆
Moore-Penrose Inverses of the Related Matrices of Star Graphs[J]. 运筹与模糊学, 2024, 14(02): 191-199. https://doi.org/10.12677/orf.2024.142125

参考文献