可交换图的一些注记

doi:10.3785/j.issn.1008-9497.2024.02.005

可交换图的一些注记

吴寒^,¹^,², 刘奋进^,^,¹, 尚凡琦¹^,³, 周艳红¹, 阮昊桐¹

1.长安大学理学院, 陕西西安 710064

2.南京大学数学系, 江苏南京 210093

3.哈尔滨工程大学青岛创新发展基地, 山东青岛 266000

A note on commutative graphs

WU Han^,¹^,², LIU Fenjin^,^,¹, SHANG Fanqi¹^,³, ZHOU Yanhong¹, RUAN Haotong¹

1.School of Science，Chang'an University，Xi'an 710064，China

2.Department of Mathematics，Nanjing University，Nanjing 210093，China

3.Qingdao Innovation and Development Base of Harbin Engineering University，Qingdao 266000，Shandong Province，China

通讯作者: ORCID：https：//orcid.org/0000-0001-8759-7695，E-mail：fenjinliu@chd.edu.cn.

收稿日期: 2022-05-09 修回日期: 2023-06-30 接受日期: 2023-07-10

基金资助:

陕西省自然科学基础研究计划项目. 2021JM-149
长安大学2020年大学生创新创业训练计划项目. S202010710247

Received: 2022-05-09 Revised: 2023-06-30 Accepted: 2023-07-10

作者简介 About authors

吴寒（2000—），ORCID：https：//orcid.org/0000-0002-4668-970X，女，本科生，主要从事图论及计算数学研究. 。

摘要

如果存在一种顶点标号，使得2个简单图的邻接矩阵可交换，则称2个简单图可交换。首先，从图的Perron向量、主特征值数量、正则性三方面给出了可交换图的必要条件。然后，借助矩阵的克罗内克积、图的笛卡尔积及循环矩阵，构造了新的可交换图。最后，将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式，给出了2种算法，并比较了二者的优劣。可交换图存在公共的特征向量，对图谱理论研究具有重要意义。

关键词： 可交换图 ; 正则图 ; 循环图 ; 克罗内克积 ; 笛卡尔积

Abstract

Two simple graphs are commutative if there exists a labelling of their vertices such that their adjacency matrices can commute. This paper gives three necessary conditions ensuring the commutativity of certain graphs from Perron vectors, the number of main eigenvalues, the regularity of graphs. Then we construct new commutative graphs by graph Kronecker product, Cartesian product and circulant matrix. Finally, for two commutative graphs, we provide two algorithms that can express one adjacency matrix as the matrix polynomial of another adjacency matrix with distinct eigenvalues, and compare their merits. Commutative graphs sharing common eigenvectors are essential to the study of spectral graph theory.

Keywords： commutative graph ; regular graph ; circulant graph ; Kronecker product ; Cartesian product

PDF (687KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

吴寒, 刘奋进, 尚凡琦, 周艳红, 阮昊桐. 可交换图的一些注记. 浙江大学学报(理学版)[J], 2024, 51(2): 172-177 doi:10.3785/j.issn.1008-9497.2024.02.005

WU Han, LIU Fenjin, SHANG Fanqi, ZHOU Yanhong, RUAN Haotong. A note on commutative graphs. Journal of Zhejiang University(Science Edition)[J], 2024, 51(2): 172-177 doi:10.3785/j.issn.1008-9497.2024.02.005

设 $G = (V, E)$ 为 $n$ 阶简单图， $V = {v_{1}, v_{2}, \dots, v_{n}}$ 为其顶点集， $A (G) = [a_{i j}]$ 为其邻接矩阵，如果 $v_{i} v_{j} \in E$ ，则 $a_{i j} = 1$ ，否则 $a_{i j} = 0$ 。将 $G$ 的特征值与特征向量分别定义为 $A (G)$ 的特征值与特征向量。如果G的特征子空间 $V_{λ} = {x | A x = λ x}$ 与全1向量 $j = {(1,1 ， \dots, 1)}^{T}$ 不正交，即至少存在1个特征向量 $x \in V_{λ}$ ，使得 $x^{T} j \neq 0$ ，则称 $G$ 的特征值 $λ$ 为主特征值^［1］。 $G$ 的谱 $S p e c (G)$ 定义为 $A (G)$ 的特征值的多重集。如果 $S p e c (G) = S p e c (H)$ ，则称图 $G$ 与图 $H$ 同谱。关于同谱图的构造及其性质，已有大量研究成果^［2-4］。

那么，具有相同特征向量的图有哪些？HORN等^［1］给出了方阵可交换的充要条件：2个可对角化的方阵可交换当且仅当它们存在一组公共的特征向量。由于图的邻接矩阵为实对称矩阵，所以2个公共特征向量的图其邻接矩阵可交换。如果存在一个置换矩阵 $P_{σ}$ ，使得 $A (G) [P_{σ}^{T} A (H) P_{σ}] = [P_{σ}^{T} A (H) P_{σ}] A (G)$ ，则称图 $G$ 与图 $H$ 可交换。有关可交换图的研究成果不多。HEINZE^［5］提出了可交换图的定义，并给出了可交换图的简单性质。BEEZER^［6］通过研究 $n$ 个顶点的路 $P_{n}$ 的邻接矩阵 $A (P_{n})$ 的矩阵多项式的 $(0,1)$ 位置特征，确定了所有与 $P_{n}$ 可交换的图。AKBARI等^［7］找到了所有可使完全二部图 $K_{n, n}$ 分解为可交换的完美匹配或哈密顿圈的整数 $n$ 。COLLINS等^［8］研究了具有相同主特征向量的图的道矩阵（walk matrix）之间的关系。

本文研究简单图邻接矩阵的可交换性，首先，从图的Perron向量、主特征值数量、正则性三方面给出可交换图的必要条件。然后，枚举所有具有6个点且主特征值数量不超过2的可交换图，并利用阶数较小的可交换图，通过矩阵的克罗内克积与图的笛卡尔积，构造新的阶数较大的可交换图，证明所有 $n$ 阶循环图是可交换的。最后，将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式，给出了2种算法，并比较其优劣。

下文将要用到的定义和符号。设 $G = (V, E)$ 是一个简单图，其补图为 $\bar{G} = (V, \bar{E})$ ，其中 $v_{1} v_{2} \in \bar{E}$ 当且仅当 $v_{1} v_{2} \in E$ 。给定2个图 $G_{1} = (V_{1}, E_{1})$ 与 $G_{2} = (V_{2}, E_{2})$ ，则 $G_{1}$ 与 $G_{2}$ 的笛卡尔积记为 $G = G_{1} □ G_{2}$ ，其顶点集为 $V (G) = {(u, v) | u \in V_{1}, v \in V_{2}}$ ，顶点 $(u_{1}, v_{1})$ 和 $(u_{2}, v_{2})$ 相连当且仅当 $u_{1} = u_{2}, v_{1} v_{2} \in E_{2}$ 或 $u_{1} u_{2} \in E_{1}, v_{1} = v_{2}$ 。

设 $A$ 是一个 $m \times n$ 矩阵， $B$ 是一个 $p \times q$ 矩阵，则矩阵 $A 与 B$ 的克罗内克积 $A \otimes B$ 为 $m p \times n q$ 的分块矩阵，表示为

$A ⊗ B = a 11 B ⋯ a 1 n B ⋮ ⋮ a m 1 B ⋯ a m n B 。$

$I, J$ 分别表示 $n$ 阶单位矩阵与全 $1$ 矩阵， $j$ 为 $n$ 维全 $1$ 向量。其他图论概念和符号可参见文献［9-11］。

1　预备知识

引理1^［1］设 $A, B$ 是2个可对角化的 $n$ 阶方阵，则以下命题等价：

（1） $A B = B A$ ；

（2） $A, B$ 可同时对角化；

（3） $A, B$ 存在一组公共特征向量。

引理2^［5］若 $λ$ 是图 $G$ 的 $q$ 重主特征值，则 $λ$ 的特征子空间存在一组标准正交基，使得其中只有一个特征向量与 $j$ 不正交，其余 $q - 1$ 个特征向量均与 $j$ 正交。

引理3（Perron-Frobenius定理）^［1］设 $A$ 是 $n$ 阶非负不可约方阵 $（ n \geq 2 ）$ ， $ρ (A)$ 为其谱半径，则

（1） $ρ (A) > 0$ ；

（2） $ρ (A)$ 是 $A$ 的最大特征值且代数重数为 $1$ ；

（3）存在唯一的正向量 $x = [x_{i}]$ ，使得 $A x = ρ (A) x$ 且 $x_{1} + x_{2} + \dots + x_{n} = 1$ ，则称 $x$ 为 $A$ 的Perron向量。

引理4^［10］设 $A, B$ 分别为 $m$ 阶图 $G$ 与 $n$ 阶图 $H$ 的邻接矩阵（ $m$ 可以与 $n$ 相等），则 $G$ 与 $H$ 的笛卡尔积的邻接矩阵为

A (G □ H) = I_{m} \otimes B + A \otimes I_{n}

。

引理5^［1，12］设 $A$ 是 $n$ 阶方阵且有 $n$ 个不同的特征值，若 $A B = B A$ ，则存在唯一次数小于 $n$ 的多项式 $f (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}$ ，使得 $B = f (A)$ 。

引理6^［13］图 $G$ 恰有1个主特征值当且仅当 $G$ 是正则图。

2　可交换图的必要条件

定理1 设 $G$ 与 $H$ 是可交换图，则

（1）若 $G$ 与 $H$ 连通，则 $ρ (A (G))$ 的Perron向量与 $ρ (A (H))$ 的相同；

（2）若 $G$ 和 $H$ 的主特征值都是单根，则它们的主特征值数量相同。

证明（1）不妨设 $A (G) A (H) = A (H) A (G)$ ，由引理1（3），知 $A (G)$ 与 $A (H)$ 存在一组公共特征向量 $x_{1}, x_{2}, \dots, x_{n}$ ，使得 $\oplus_{i = 1}^{n} s p a n (x_{i}) = R^{n}$ 。因为 $G$ 与 $H$ 连通， $A (G)$ 和 $A (H)$ 是非负不可约方阵，由Perron-Frobenius定理，可知 $A (G)$ 和 $A (H)$ 的谱半径 $ρ (G)$ 和 $ρ (H)$ 都是单根且对应的特征向量均为正向量，不妨设 $x_{1}, x_{2}, \dots, x_{n}$ 中的唯一正特征向量为 $x_{1}$ ，因此可以调整 $x_{1}$ 的模长使其为 $ρ (G)$ 与 $ρ (H)$ 的Perron向量。

（2）反证法，不妨设 $G$ 与 $H$ 的主特征值、不同特征值数量分别为 $r_{1}$ ， $r_{2}$ ； $S_{1}$ ， $S_{2}$ 且 $r_{1} > r_{2}$ 。记

V_{λ_{i}} = {ξ | A (G) ξ = λ_{i} ξ}, V_{μ_{i}} = {η | A (H) η = μ_{i} η}

为特征值 $λ_{i} (μ_{i})$ 的特征子空间。因为

R^{n} = V_{λ_{1}} \oplus \dots \oplus V_{λ_{r_{_{1}}}} \oplus \dots \oplus V_{λ_{s_{_{1}}}}

，（1）

结合引理2，可知 $x_{1}, x_{2}, \dots, x_{n}$ 中恰有 $r_{1}$ 个特征向量与 $j$ 不正交。又因为

R^{n} = V_{μ_{1}} \oplus \dots \oplus V_{μ_{r_{_{2}}}} \oplus \dots \oplus V_{μ_{s_{_{2}}}}

，（2）

所以 $x_{1}, x_{2}, \dots, x_{n}$ 中恰有 $r_{2}$ 个特征向量与 $j$ 不正交，矛盾。

注1 定理1中“图 $G$ 和 $H$ 的主特征值都是单根”条件不可去除，否则存在反例，如图1所示，其中可交换图 $K_{2,4}$ 和 $3 K_{2}$ 的主特征值数量分别为2和1。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 主特征值数量不同的可交换图

Fig.1 Commutative graphs with different number of main eigenvalues

定理2 设图 $G$ 的补图为 $\bar{G}$ ，则 $A (G) A (\bar{G}) = A (\bar{G}) A (G)$ 当且仅当 $G$ 为正则图。

证明因为 $A (\bar{G}) = J - I - A (G)$ ，设 $G$ 的度序列为 $A (G) j = [d_{1}, d_{2}, \dots, d_{n}]^{T}$ ，又

A (G) [J - I - A (G)] = A (G) J - A (G) I - A {(G)}^{2}

，

[J - I - A (G)] A (G) = J A (G) - I A (G) - A {(G)}^{2}

，

所以

A (G) J = J A (G)

，

即

[\begin{matrix} d_{1} & d_{1} & \dots & d_{1} \\ d_{2} & d_{2} & \dots & d_{2} \\ ⋮ & ⋮ & ⋮ \\ d_{n} & d_{n} & \dots & d_{n} \end{matrix}] = [\begin{matrix} d_{1} & d_{2} & \dots & d_{n} \\ d_{1} & d_{2} & \dots & d_{n} \\ ⋮ & ⋮ & ⋮ \\ d_{1} & d_{2} & \dots & d_{n} \end{matrix}]

。

因此 $d_{1} = d_{2} = \dots = d_{n}$ ，即 $G$ 为正则图。

反之，若 $G$ 为 $k$ 正则图，则

A (G) J = [\begin{matrix} k & \dots & k \\ ⋮ & ⋮ \\ k & \dots & k \end{matrix}] = J A (G)

，

于是

A (G) [J - I - A (G)] = [J - I - A (G)] A (G)

。

注2 在定理2中，若只要求图 $G$ 与其补图 $\bar{G}$ 可交换，则 $G$ 不一定是正则图，如图2所示。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 非正则可交换图 $G$ 与 $\bar{G}$

Fig.2 Non-regular commutative graphs $G$ and $\bar{G}$

定理3 图 $G_{1}$ 与正则图 $G_{2}$ 可交换当且仅当 ${\bar{G}}_{1}$ 与 $G_{2}$ 可交换。

证明必要性。不妨设

A (G_{1}) A (G_{2}) = A (G_{2})

A (G_{1})

，

则

\begin{array}{l} A ({\bar{G}}_{1}) A (G_{2}) = [J - I - A (G_{1})] A (G_{2}) = \\ J A (G_{2}) - A (G_{2}) - A (G_{1}) A (G_{2}) = \\ A (G_{2}) J - A (G_{2}) - A (G_{2}) A (G_{1}) = \\ A (G_{2}) [J - I - A (G_{1})] = \\ A (G_{2}) A ({\bar{G}}_{1}) 。 \end{array}

充分性。用 ${\bar{G}}_{1}$ 替换 $G_{1}$ 即可证得。

推论1 完全图 $K_{n}$ 与任意 $n$ 阶正则图可交换。

证明在定理3中，令 $G_{1} = n K_{1}$ ，因为 $A (n K_{1}) =$ $O_{n \times n}$ 与任意邻接矩阵可交换，所以图 $G_{1}$ 与任意正则图 $G_{2}$ 的邻接矩阵可交换。由定理3，知 $G_{2}$ 与 ${\bar{G}}_{1} = K_{n}$ 可交换。

经编程计算，枚举了所有主特征值数量小于3的连通图及与其可交换的连通图，如图3所示。其中， $G_{1} ~ G_{5}$ 为主特征值数量为1的六阶连通图，且均为循环图。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 主特征值数量小于3的六阶连通图

Fig.3 Connected graphs with 6 vertices and the number of main eigenvalues less than 3

表1列出了主特征值数量为2的18个六阶连通图及与其对应的可交换连通图。

表1 主特征值数量为2的六阶连通图及与其对应的可交换连通图

Table 1 Connected graphs with six vertices two main eigenvalues and their commutative graphs

图的序号	可交换图的序号
$G_{6}$	$G_{6}$
$G_{7}$	$G_{7}$ ， $G_{13}$
$G_{8}$	$G_{8}$
$G_{9}$	$G_{9}$ ， $G_{17}$ ， $G_{19}$ ， $G_{20}$
$G_{10}$	$G_{10}$ ， $G_{16}$
$G_{11}$	$G_{11}$
$G_{12}$	$G_{12}$
$G_{13}$	$G_{7}$ ， $G_{13}$
$G_{14}$	$G_{14}$
$G_{15}$	$G_{15}$
$G_{16}$	$G_{10}$ ， $G_{16}$
$G_{17}$	$G_{9}$ ， $G_{17}$ ， $G_{19}$ ， $G_{20}$
$G_{18}$	$G_{18}$
$G_{19}$	$G_{9}$ ， $G_{17}$ ， $G_{19}$
$G_{20}$	$G_{9}$ ， $G_{17}$ ， $G_{20}$
$G_{21}$	$G_{21}$
$G_{22}$	$G_{22}$
$G_{23}$	$G_{23}$

新窗口打开| 下载CSV

3　可交换图的构造

通过矩阵的克罗内克积、图的笛卡尔积及循环矩阵，构造可交换图。

3.1　矩阵的克罗内克积

定理4 设 $A$ ， $C$ 均为 $m$ 阶方阵， $B$ ， $D$ 均为 $n$ 阶方阵。若 $A C = C A$ ， $B D = D B$ ，则

(A \otimes B) (C \otimes D) = (C \otimes D) (A \otimes B)

。

证明 $(A \otimes B) (C \otimes D)$ 的 $(i, j)$ 元素为

\begin{matrix} \begin{array}{l} {([\begin{matrix} a_{11} B & \dots & a_{1 m} B \\ ⋮ & ⋮ \\ a_{m 1} B & \dots & a_{m m} B \end{matrix}] [\begin{matrix} c_{11} D & \dots & c_{1 m} D \\ ⋮ & ⋮ \\ c_{m 1} D & \dots & c_{m m} D \end{matrix}])}_{i j} = \\ \sum_{k = 1}^{m} a_{i k} c_{k j} B D = {(A C)}_{i j} (B D) ， \end{array} \end{matrix}

$(C \otimes D) (A \otimes B)$ 的 $(i, j)$ 元素为

\begin{matrix} \begin{array}{l} {([\begin{matrix} c_{11} D & \dots & c_{1 m} D \\ ⋮ & ⋮ \\ c_{m 1} D & \dots & c_{m m} D \end{matrix}] [\begin{matrix} a_{11} B & \dots & a_{1 m} B \\ ⋮ & ⋮ \\ a_{m 1} B & \dots & a_{m m} B \end{matrix}])}_{i j} = \\ \sum_{k = 1}^{m} c_{i k} a_{k j} D B = {(C A)}_{i j} \otimes (D B) 。 \end{array} \end{matrix}

因为 $A C = C A$ ，　 $B D = D B$ ，

{(A C)}_{i j} B D = {(C A)}_{i j} D B

，

所以 $(A \otimes B) (C \otimes D) = (C \otimes D) (A \otimes B)$ 。

将定理4应用于 $(0,1)$ 方阵，构造可交换图。

推论2 设 $A_{1}$ ， $A_{2}$ 为2个 $m$ 阶图的邻接矩阵， $B_{1}$ ， $B_{2}$ 为2个 $n$ 阶 $(0,1)$ 方阵（主对角线元素可为1）。若 $A_{1} A_{2} = A_{2} A_{1}$ ， $B_{1} B_{2} = B_{2} B_{1}$ ，则 $A_{1} \otimes B_{1}$ ， $A_{2} \otimes B_{2}$ 所对应的图可交换。

3.2　图的笛卡尔积

定理5 设 $A$ ， $C$ 均为 $m$ 阶图 $Γ_{1}, Γ_{2}$ 的邻接矩阵， $B$ ， $D$ 均为 $n$ 阶图 $Γ_{3}, Γ_{4}$ 的邻接矩阵。若 $A C = C A$ ， $B D = D B$ ，则图 $Γ_{1} □ Γ_{3}$ 与图 $Γ_{2} □ Γ_{4}$ 可交换。

证明根据引理4，可得

\begin{array}{l} (A □ B) (C □ D) = \\ (I_{m} \otimes B + A \otimes I_{n}) (I_{m} \otimes D + C \otimes I_{n}) = \\ (I_{m} \otimes B) (I_{m} \otimes D) + (I_{m} \otimes B) (C \otimes I_{n}) + \\ (A \otimes I_{n}) (I_{m} \otimes D) + (A \otimes I_{n}) (C \otimes I_{n}) = \\ (I_{m} \otimes B D) + (C \otimes B) + (A \otimes D) + (A C \otimes I_{n}) = \\ (I_{m} \otimes D B) + (A \otimes D) + (C \otimes B) + (C A \otimes I_{n}) = \\ (I_{m} \otimes D) (I_{m} \otimes B) + (I_{m} \otimes D) (A \otimes I_{n}) + \\ (C \otimes I_{n}) (I_{m} \otimes B) + (C \otimes I_{n}) (A \otimes I_{n}) = \\ (I_{m} \otimes D + C \otimes I_{n}) (I_{m} \otimes B + A \otimes I_{n}) = \\ (C □ D) (A □ B) 。 \end{array}

3.3　循环矩阵

循环矩阵是一种特殊的方阵，将上一行各元素依次右移一个位置得到下一行元素，上一行最后一个元素为下一行第一个元素。

定理6 任意2个 $n$ 阶循环矩阵可交换。

证明不妨设

A = [\begin{matrix} a_{1} & a_{2} & \dots & a_{n} \\ a_{n} & a_{1} & \dots & a_{n - 1} \\ ⋮ & ⋮ & ⋮ \\ a_{2} & a_{3} & \dots & a_{1} \end{matrix}]

，

B = [\begin{matrix} b_{1} & b_{2} & \dots & b_{n} \\ b_{n} & b_{1} & \dots & b_{n - 1} \\ ⋮ & ⋮ & ⋮ \\ b_{2} & b_{3} & \dots & b_{1} \end{matrix}]

。

令 $P$ 为循环矩阵，则

\begin{matrix} P = [\begin{matrix} 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & \dots & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & 0 & 1 \\ 1 & 0 & 0 & \dots & 0 & 0 \end{matrix}] : = \\ [e_{n}, e_{1}, e_{2}, \dots, e_{n - 2}, e_{n - 1}], \end{matrix}

其中， $e_{i}$ 表示第 $i$ 个分量为1，其余分量均为0的 $n$ 维列向量。由矩阵分块乘法，可得

P^{i} = [e_{n - i + 1}, e_{n - i + 2}, e_{n - i + 3}, \dots, e_{n - i - 1}, e_{n - i}]

，

其中， $P^{i}$ 的列向量下标模 $n$ 取余，于是

\begin{array}{l} A = a_{1} P^{0} + a_{2} P + \dots + a_{n} P^{n - 1}, \\ B = b_{1} P^{0} + b_{2} P + \dots + b_{n} P^{n - 1} 。 \end{array}

因为 $A, B$ 均为 $P$ 的矩阵多项式，故 $A B = B A$ 。

若一个图的邻接矩阵为循环矩阵，则称该图为循环图，从而有

推论3 任意同阶循环图的邻接矩阵可交换。

4　可交换图的矩阵多项式

设 $A_{1}$ 是 $n$ 阶图 $G_{1}$ 的邻接矩阵， $A_{1}$ 有 $n$ 个不同的特征值，由引理5，任何一个与 $A_{1}$ 可交换的图 $G_{2}$ 的邻接矩阵 $A_{2}$ 均能表示为 $A_{1}$ 的次数小于 $n$ 的多项式

f (x) = \sum_{i = 0}^{n - 1} c_{i} x^{i}

的矩阵多项式，即 $A_{2} = \sum_{i = 1}^{n} c_{i} {A_{1}}^{i}$ 。

下面给出矩阵多项式 $f (x)$ 的2种求解法，并比较其优劣。

4.1　线性方程组法

输入 $n$ 阶图 $G_{1}, G_{2}$ 的邻接矩阵 $A_{1}, A_{2}$ 。

Step 1 约定 $A_{1}^{0} = I_{n}$ ，依次求 $A_{1}$ 的各次幂 $A_{1}^{k} (k = 0,1 ， \dots, n - 1)$ 。

Step 2 构造线性方程组 $A x = B$ 的系数矩阵 $A$ ，则第 $k + 1$ 列为 $A_{1}^{k} (k = 0,1 ， \dots, n - 1)$ 按列压平而成的 $n^{2}$ 维列向量。

Step 3 令 $B$ 为 $A_{2}$ 按列压平而成的 $n^{2}$ 维列向量。

Step 4 对 $A x = B$ 两边左乘 $A$ 的左逆 $A_{l e f t}^{- 1}$ ，求解超定线性方程组的解 $x = A_{l e f t}^{- 1} B$ 。

输出 $x = (c_{0}, c_{1}, \dots, c_{n - 1})^{T}$ 。

4.2　拉格朗日插值法

输入 $n$ 阶图 $G_{1}, G_{2}$ 的邻接矩阵 $A_{1}, A_{2}$ 。

Step 1 求 $A_{1}, A_{2}$ 的谱：

S p e c (A_{1}) = {λ_{1} > λ_{2} > \dots > λ_{n}}

，

S p e c (A_{2}) = {μ_{1}^{m_{1}}, μ_{2}^{m_{2}}, \dots, μ_{s}^{m_{s}}}

，

其中，上标 $m_{i}$ 表示 $A_{2}$ 的特征值 $μ_{i} (1 \leq i \leq s)$ 的重数且满足 $\sum_{i = 1}^{s} m_{i} = n$ 。计算矩阵 $V_{1}$ ，其中 $V_{1}$ 的列向量为 $A_{1}$ 的全部标准正交特征向量。

Step 2 计算

\begin{matrix} \begin{array}{l} A_{2} V_{1} = [A_{2} x_{1}, A_{2} x_{2}, \dots, A_{2} x_{n}] = \\ [μ_{i_{1}} x_{1}, μ_{i_{2}} x_{2}, \dots, μ_{i_{n}} x_{n}] = \\ [x_{1}, x_{2}, \dots, x_{n}] [\begin{matrix} μ_{i_{1}} \\ μ_{i_{2}} \\ ⋱ \\ μ_{i_{n}} \end{matrix}] 。 \end{array} \end{matrix}

Step 3 计算 $μ_{i} V_{1}$ $(1 \leq i \leq s)$ ，并与 $A_{2} V_{1}$ 比较，找出所有相同的列，将其在 $A_{2} V_{1}$ 中的列标号记为 $j_{1}, j_{2}, \dots, j_{k}$ ，即 $λ_{j_{1}}, λ_{j_{2}}, \dots, λ_{j_{k}}$ 与 $μ_{i}$ 对应，其中 ${λ_{j_{1}}, λ_{j_{2}}, \dots, λ_{j_{k}}} \subset S p e c (A_{1})$ 。

Step 4 对得到的 $n$ 组对应特征值 $(λ_{i}, μ_{j}) (1 \leq i \leq n, 1 \leq j \leq s)$ ，采用拉格朗日插值法，得到多项式 $f (x)$ 。

输出 $f (x) = c_{0} + c_{1} x + \dots + c_{n - 1} x^{n - 1}$ 。

4.3　算例

设 $A$ 为图 $Γ_{1}$ 的邻接矩阵， $B$ 为路 $P_{10}$ 的邻接矩阵，如图4所示。

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 一对可互相表示为其邻接矩阵的矩阵多项式的可交换图

Fig.4 A pair of commutative graphs that can be expressed as matrix polynomial of their adjacency matrices

容易验证 $A B = B A$ ， $A$ 的谱为

\begin{array}{l} S p e c (A) = (\pm 3.513 0, \pm 1.204 0, \pm 0.763 5, \\ \pm 0.594 4, \pm 0.521 1) \end{array}

，

特征值互不相同，从而矩阵 $B$ 可表示为 $A$ 的多项式 $f (A)$ 。分别采用线性方程组法和拉格朗日插值法，可得

f (x) = - 48 x + 267 x^{3} - 431 x^{5} + 206 x^{7} - 14 x^{9} ，

2种方法所用时间分别为0.005 7 s和0.111 2 s。

4.4　2种方法的对比

理论上，采用线性方程组法可获得精确解，且与矩阵规模 $n$ 无关，但在实际计算中，由于受舍入误差、机器误差的影响，当图的顶点较多时，在计算矩阵伪逆时可能会产生较大的误差，因此对算例的选取有一定要求，本文算例使用了50个顶点的路的图，可得到准确结果。

拉格朗日插值法是一种数值近似方法，在计算无理特征值时会产生一定舍入误差。当算例较简单，即顶点较少（小于等于10个）时，可得到准确的插值多项式，但当顶点数超过10时，会产生较大误差，无法得到准确的数值解。

在计算时间上，如只计算矩阵的伪逆与拉格朗日插值多项式，当顶点较多时，拉格朗日插值法更快，但在实际计算过程中，拉格朗日插值法需先通过2个循环得到一一对应的特征值，再进行拉格朗日插值求解，而线性方程组法只需计算矩阵乘法与伪逆，所以线性方程组法更快。

http://dx.doi.org/10.3785/j.issn.1008-9497.2024.02.001

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

HORN

R A

， JOHNSON

C R

. Matrix Analysis［M］. 2nd ed. Cambridge / New York： Cambridge University Press， 2012.

[本文引用: 5]

[2]

GODSIL

C D

， MCKAY

B D

Constructing cospectral graphs

［J］. Aequationes Mathematicae， 1982， 25（1）： 257-268. DOI： 10.1007/BF02189621

[本文引用: 1]

[3]

LIU

F J

， WANG

， YU

， et al.

Generalized cospectral graphs with and without Hamiltonian cycles

［J］. Linear Algebra and Its Applications， 2020， 585： 199-208. DOI： 10.1016/j.laa.2019.10.001

[4]

Y Z

， GONG

S C

， WANG

Constructing cospectral bipartite graphs

［J］. Discrete Mathematics， 2020， 343（10）： 112020. DOI： 10.1016/j.disc.2020.112020

[本文引用: 1]

[5]

HEINZE

Applications of Schur Rings in Algebraic Combinatorics： Graphs， Partial Difference Sets and Cyclotomic Schemes

［D］. Oldenburg： Universität Oldenburg， 2001.

[本文引用: 2]

[6]

BEEZER

R A

On the polynomial of a path

［J］. Linear Algebra and Its Applications， 1984， 63： 221-225. DOI： 10.1016/0024-3795（84）90144-7

[本文引用: 1]

[7]

AKBARI

， MOAZAMI

， MOHAMMADIAN

Commutativity of the adjacency matrices of graphs

［J］. Discrete Mathematics， 2009， 309（3）： 595-600. DOI： 10.1016/j.disc.2008.09.006

[本文引用: 1]

[8]

COLLINS

， SCIRIHA

The walks and CDC of graphs with the same main eigenspace

［J］. Discussiones Mathematicae Graph Theory， 2023， 43 （2）： 507-532. DOI： 10.7151/dmgt.2386

[本文引用: 1]

[9]

GODSIL

， ROYLE

. Algebraic Graph Theory［M］. New York： Springer， 2001. doi:10.1007/978-1-4613-0163-9

[本文引用: 1]

[10]

CVETKOVIĆ

D M

， ROWLINSON

. An Introduction to the Theory of Graph Spectra： 48［M］. Cambridge： Cambridge University Press， 2010. doi:10.1017/cbo9780511801518

[本文引用: 1]

[11]

高随祥

. 图论与网络流理论［M］. 北京：高等教育出版社， 2009.

[本文引用: 1]

GAO

S X

. Graph Theory and Network Flow Theory［M］. Beijing： Higher Education Press， 2009.

[本文引用: 1]

[12]

丘维声

. 高等代数（下册）［M］. 北京：清华大学出版社， 2019.

[本文引用: 1]

QIU

W S

. Higher Algebra （Vol 2）［M］. Beijing： Tsinghua University Press， 2019.

[本文引用: 1]

[13]

DRAZIN

M P

Some generalizations of matrix commutativity

［J］. Proceedings of the London Mathematical Society， 1951， s3-1（1）： 222-231. DOI： 10.1112/plms/s3-1.1.222

[本文引用: 1]

2012

... 设

G = (V, E)

为

n

阶简单图，

V = {v_{1}, v_{2}, \dots, v_{n}}

为其顶点集，

A (G) = [a_{i j}]

为其邻接矩阵，如果

v_{i} v_{j} \in E

，则

a_{i j} = 1

，否则

a_{i j} = 0

.将

G

的特征值与特征向量分别定义为

A (G)

的特征值与特征向量.如果G的特征子空间

V_{λ} = {x | A x = λ x}

与全1向量

j = {(1,1 ， \dots, 1)}^{T}

不正交，即至少存在1个特征向量

x \in V_{λ}

，使得

x^{T} j \neq 0

，则称

G

的特征值

λ

为主特征值^［1］.

G

的谱

S p e c (G)

定义为

A (G)

的特征值的多重集.如果

S p e c (G) = S p e c (H)

，则称图

G

与图

H

同谱.关于同谱图的构造及其性质，已有大量研究成果^［2-4］. ...

... 那么，具有相同特征向量的图有哪些？HORN等^［1］给出了方阵可交换的充要条件：2个可对角化的方阵可交换当且仅当它们存在一组公共的特征向量.由于图的邻接矩阵为实对称矩阵，所以2个公共特征向量的图其邻接矩阵可交换.如果存在一个置换矩阵

P_{σ}

，使得

A (G) [P_{σ}^{T} A (H) P_{σ}] = [P_{σ}^{T} A (H) P_{σ}] A (G)

，则称图

G

与图

H

可交换.有关可交换图的研究成果不多.HEINZE^［5］提出了可交换图的定义，并给出了可交换图的简单性质.BEEZER^［6］通过研究

n

个顶点的路

P_{n}

的邻接矩阵

A (P_{n})

的矩阵多项式的

(0,1)

位置特征，确定了所有与

P_{n}

可交换的图.AKBARI等^［7］找到了所有可使完全二部图

K_{n, n}

分解为可交换的完美匹配或哈密顿圈的整数

n

.COLLINS等^［8］研究了具有相同主特征向量的图的道矩阵（walk matrix）之间的关系. ...

... 引理1^［1］设

A, B

是2个可对角化的

n

阶方阵，则以下命题等价： ...

... 引理3（Perron-Frobenius定理）^［1］设

A

是

n

阶非负不可约方阵

（ n \geq 2 ）

，

ρ (A)

为其谱半径，则 ...

... 引理5^［1，12］设

A

是

n

阶方阵且有

n

个不同的特征值，若

A B = B A

，则存在唯一次数小于

n

的多项式

f (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}

，使得

B = f (A)

. ...

Constructing cospectral graphs

1982

... 设

G = (V, E)

为

n

阶简单图，

V = {v_{1}, v_{2}, \dots, v_{n}}

为其顶点集，

A (G) = [a_{i j}]

为其邻接矩阵，如果

v_{i} v_{j} \in E

，则

a_{i j} = 1

，否则

a_{i j} = 0

.将

G

的特征值与特征向量分别定义为

A (G)

的特征值与特征向量.如果G的特征子空间

V_{λ} = {x | A x = λ x}

与全1向量

j = {(1,1 ， \dots, 1)}^{T}

不正交，即至少存在1个特征向量

x \in V_{λ}

，使得

x^{T} j \neq 0

，则称

G

的特征值

λ

为主特征值^［1］.

G

的谱

S p e c (G)

定义为

A (G)

的特征值的多重集.如果

S p e c (G) = S p e c (H)

，则称图

G

与图

H

同谱.关于同谱图的构造及其性质，已有大量研究成果^［2-4］. ...

Generalized cospectral graphs with and without Hamiltonian cycles

2020

Constructing cospectral bipartite graphs

2020

... 设

G = (V, E)

为

n

阶简单图，

V = {v_{1}, v_{2}, \dots, v_{n}}

为其顶点集，

A (G) = [a_{i j}]

为其邻接矩阵，如果

v_{i} v_{j} \in E

，则

a_{i j} = 1

，否则

a_{i j} = 0

.将

G

的特征值与特征向量分别定义为

A (G)

的特征值与特征向量.如果G的特征子空间

V_{λ} = {x | A x = λ x}

与全1向量

j = {(1,1 ， \dots, 1)}^{T}

不正交，即至少存在1个特征向量

x \in V_{λ}

，使得

x^{T} j \neq 0

，则称

G

的特征值

λ

为主特征值^［1］.

G

的谱

S p e c (G)

定义为

A (G)

的特征值的多重集.如果

S p e c (G) = S p e c (H)

，则称图

G

与图

H

同谱.关于同谱图的构造及其性质，已有大量研究成果^［2-4］. ...

Applications of Schur Rings in Algebraic Combinatorics： Graphs， Partial Difference Sets and Cyclotomic Schemes

2001

P_{σ}

，使得

A (G) [P_{σ}^{T} A (H) P_{σ}] = [P_{σ}^{T} A (H) P_{σ}] A (G)

，则称图

G

与图

H

可交换.有关可交换图的研究成果不多.HEINZE^［5］提出了可交换图的定义，并给出了可交换图的简单性质.BEEZER^［6］通过研究

n

个顶点的路

P_{n}

的邻接矩阵

A (P_{n})

的矩阵多项式的

(0,1)

位置特征，确定了所有与

P_{n}

可交换的图.AKBARI等^［7］找到了所有可使完全二部图

K_{n, n}

分解为可交换的完美匹配或哈密顿圈的整数

n

.COLLINS等^［8］研究了具有相同主特征向量的图的道矩阵（walk matrix）之间的关系. ...

... 引理2^［5］若

λ

是图

G

的

q

重主特征值，则

λ

的特征子空间存在一组标准正交基，使得其中只有一个特征向量与

j

不正交，其余

q - 1

个特征向量均与

j

正交. ...

On the polynomial of a path

1984

P_{σ}

，使得

A (G) [P_{σ}^{T} A (H) P_{σ}] = [P_{σ}^{T} A (H) P_{σ}] A (G)

，则称图

G

与图

H

可交换.有关可交换图的研究成果不多.HEINZE^［5］提出了可交换图的定义，并给出了可交换图的简单性质.BEEZER^［6］通过研究

n

个顶点的路

P_{n}

的邻接矩阵

A (P_{n})

的矩阵多项式的

(0,1)

位置特征，确定了所有与

P_{n}

可交换的图.AKBARI等^［7］找到了所有可使完全二部图

K_{n, n}

分解为可交换的完美匹配或哈密顿圈的整数

n

.COLLINS等^［8］研究了具有相同主特征向量的图的道矩阵（walk matrix）之间的关系. ...

Commutativity of the adjacency matrices of graphs

2009

P_{σ}

，使得

A (G) [P_{σ}^{T} A (H) P_{σ}] = [P_{σ}^{T} A (H) P_{σ}] A (G)

，则称图

G

与图

H

可交换.有关可交换图的研究成果不多.HEINZE^［5］提出了可交换图的定义，并给出了可交换图的简单性质.BEEZER^［6］通过研究

n

个顶点的路

P_{n}

的邻接矩阵

A (P_{n})

的矩阵多项式的

(0,1)

位置特征，确定了所有与

P_{n}

可交换的图.AKBARI等^［7］找到了所有可使完全二部图

K_{n, n}

分解为可交换的完美匹配或哈密顿圈的整数

n

.COLLINS等^［8］研究了具有相同主特征向量的图的道矩阵（walk matrix）之间的关系. ...

The walks and CDC of graphs with the same main eigenspace

2023

P_{σ}

，使得

A (G) [P_{σ}^{T} A (H) P_{σ}] = [P_{σ}^{T} A (H) P_{σ}] A (G)

，则称图

G

与图

H

可交换.有关可交换图的研究成果不多.HEINZE^［5］提出了可交换图的定义，并给出了可交换图的简单性质.BEEZER^［6］通过研究

n

个顶点的路

P_{n}

的邻接矩阵

A (P_{n})

的矩阵多项式的

(0,1)

位置特征，确定了所有与

P_{n}

可交换的图.AKBARI等^［7］找到了所有可使完全二部图

K_{n, n}

分解为可交换的完美匹配或哈密顿圈的整数

n

.COLLINS等^［8］研究了具有相同主特征向量的图的道矩阵（walk matrix）之间的关系. ...

2001

...

I, J

分别表示

n

阶单位矩阵与全

1

矩阵，

j

为

n

维全

1

向量.其他图论概念和符号可参见文献［9-11］. ...

2010

... 引理4^［10］设

A, B

分别为

m

阶图

G

与

n

阶图

H

的邻接矩阵（

m

可以与

n

相等），则

G

与

H

的笛卡尔积的邻接矩阵为 ...

2009

...

I, J

分别表示

n

阶单位矩阵与全

1

矩阵，

j

为

n

维全

1

向量.其他图论概念和符号可参见文献［9-11］. ...

2009

...

I, J

分别表示

n

阶单位矩阵与全

1

矩阵，

j

为

n

维全

1

向量.其他图论概念和符号可参见文献［9-11］. ...

2019

... 引理5^［1，12］设

A

是

n

阶方阵且有

n

个不同的特征值，若

A B = B A

，则存在唯一次数小于

n

的多项式

f (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}

，使得

B = f (A)

. ...

2019

... 引理5^［1，12］设

A

是

n

阶方阵且有

n

个不同的特征值，若

A B = B A

，则存在唯一次数小于

n

的多项式

f (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}

，使得

B = f (A)

. ...

Some generalizations of matrix commutativity

1951

... 引理6^［13］图

G

恰有1个主特征值当且仅当

G

是正则图. ...

〈

〉