上海理工大学理学院，上海

收稿日期：2024年1月20日；录用日期：2024年3月22日；发布日期：2024年3月29日

摘要

对n阶欧拉图G，考虑其对应的Q-道矩阵 $W_Q=\left(e,Qe,Q^{2}e,\cdots ,Q^{n-1}e\right)$ ，这里Q为图G的无符号拉普拉斯矩阵，e为n维全一列向量。本文给出当 $W_Q$ 的行列式满足 $det\left(W_Q\right)=\pm 2^{\lfloor \frac{5n-5}{2}\rfloor }b$ ，其中b为奇数且不含平方因子时， $W_Q$ 的Smith标准型为 $diag(\underset{\lceil \frac{n+1}{2}\rceil }{\underset{︸}{1,2^2,\cdots ,2^2}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2^3,2^3,\cdots ,2^{3}b}})$ 。

关键词

无符号拉普拉斯矩阵，道矩阵，Smith标准型，欧拉图

Properties of the Smith Normal Form of the Q-Walk Matrix in Euler Graphs

Jingyuan Wei, Sicheng Lyu

College of Science, University of Shanghai for Science and Technology, Shanghai

Received: Jan. 20^th, 2024; accepted: Mar. 22^nd, 2024; published: Mar. 29^th, 2024

ABSTRACT

Let G be an Euler Graph with n vertices. The Q-walk matrix $W_Q$ of G is the matrix $\left(e,Qe,Q^{2}e,\cdots ,Q^{n-1}e\right)$ , where Q is the Signless Laplacian matrix of G and e is the all-one vector. We show that determinant of $W_Q$ satisfies $det\left(W_Q\right)=\pm 2^{\lfloor \frac{5n-5}{2}\rfloor }b$ , where b is odd and square-free, then the Smith normal form of $W_Q$ is $diag(\underset{\lceil \frac{n+1}{2}\rceil }{\underset{︸}{1,2^2,\cdots ,2^2}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2^3,2^3,\cdots ,2^{3}b}})$ .

Keywords:Signless Laplacian Matrix, Walk Matrix, Smith Normal Form, Euler Graphs

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. 引言

图的谱包含了关于给定图的大量组合信息，可用于描述和分析各种复杂系统和结构，如网络、物理、生物等，因此长期以来一直是图谱理论中的一个有用工具。图谱领域中一个长期未解决的基本问题是：“哪些图是由它们的谱确定的？”事实表明，证明图是谱确定的比构造同谱图更具有挑战性。迄今为止，谱确定的许多证明都依赖于这些图的谱的一些特殊性质，因此不能推广到一般图上。关于这个问题的背景和一些已知的结果，可以参考文献 [1] [2] 。

当两个图同谱且补图也同谱时，则称它们为广义同谱图。当任何与G广义同谱的图都与G同构，则称图G是广义谱确定的。通过引入道矩阵(walk-matrix)这一重要工具，并研究其Smith标准型特征给出了判定一大类图广义谱确定的条件。其中图G的道矩阵定义为：

$W=\left(e,Ae,A^{2}e,\cdots ,A^{n-1}e\right)$ ,

其中e为n维全一列向量，A为图G对应的邻接矩阵 [2] 。

Smith标准型是整系数矩阵的一种对角化形式(具体详细求解可见文献 [3] )，根据文献 [4] ，它具有存在性和唯一性，且有如下定理。

定理1 [4] 设R为具有同一性的交换环，Smith标准型将有如下性质：

(1) 如果R上所有矩阵都有Smith标准型，那它则是Bézout环。

(2) 当且仅当R是Bézout环，R上所有对角矩阵都有Smith标准型。

定理2 [4] 令R为唯一因式分解域，其中任意两个元素都有最大公因数。假设A是R上的m × n矩阵M是的Smith标准型，其中A为主对角线为 $\left({\alpha }_1,\cdots ,{\alpha }_m\right)$ ，其余地方为0的矩阵。则当 $1\le k\le m$ 时， ${\alpha }_1{\alpha }_2\cdots {\alpha }_k$ 等于所有A的k × k子式的最大公因数。其中如果所有k × k子式都为0，则最大公因数亦为0。

由此可见Smith标准型在代数与图论中有重要意义与应用。

1736年欧拉解决了著名的哥尼斯堡七桥问题，并将其一般化，证明了如下定理：一个非空连通图当且仅当它的每个顶点的度数都是偶数时是欧拉图(Euler Graph) [5] 。

关于道矩阵的Smith标准型，由于欧拉图的特殊性质，文献 [6] 给出了欧拉图中道矩阵的Smith标准型在某些条件下与图的道矩阵的某些参数之间的关系，即定理3。

定理3 [6] 设图G为n阶欧拉图，W为图G对应的道矩阵，若 $\det \left(W\right)=\pm 2^{\lfloor \frac{3n-3}{2}\rfloor }b$ ，b为奇数且无平方因子，则W的Smith标准型为：

$S=\text{diag(}\underset{\lceil \frac{n+1}{2}\rceil }{\underset{︸}{1,2,\cdots ,2}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2^2,2^2,\cdots ,2^{2}b}})$ .

类似的，本文考虑图G对应的无符号拉普拉斯矩阵Q的Q-道矩阵，其定义如下：

$W_Q=\left(e,Qe,Q^{2}e,\cdots ,Q^{n-1}e\right)$ .

本文给出在某些条件下欧拉图的Q-道矩阵的Smith标准型与图的Q-道矩阵的某些参数之间存在关联，并给出如下定理。

定理4 设G为n阶欧拉图， $W_Q$ 为图G对应的Q-道矩阵，若 $\det \left(W_Q\right)=\pm 2^{\lfloor \frac{5n-5}{2}\rfloor }b$ ，b为奇数且无平方因子，则 $W_Q$ 的Smith标准型为：

$S=\text{diag(}\underset{\lceil \frac{n+1}{2}\rceil }{\underset{︸}{1,2^2,\cdots ,2^2}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2^3,2^3,\cdots ,2^{3}b}})$ .

结合文献 [7] ，本结论可简化对Smith标准型的Dynkin拓展矩阵 ${\tilde{D}}_n$ 求解。还可结合文献 [8] ，让多维系统的缩减和多元多项式的约简的步骤更为简洁。

以下本文将主要围绕此定理进行证明。

2. 定义引入

为了叙述方便，给出如下定义：

${\Sigma }_n=\left\{G为n阶欧拉图|\det \left(W_Q\right)=\pm 2^{\lfloor \frac{5n-5}{2}\rfloor }b,b为奇数且无平方因子\right\}$ .

其中n阶欧拉图是指n个顶点且具有欧拉回路的图，若为无向图，则各个顶点的度数皆为偶数；若为有向图，则各个顶点出度与入度相等。

设图G的度序列为d，令 $\hat{d}:=\frac{d}{2}={\left({\hat{d}}_1,{\hat{d}}_2,\cdots ,{\hat{d}}_n\right)}^{\text{T}}$ 。由在欧拉图中所有顶点的度都为偶数，易得 $\hat{d}$ 为整数列向量。因此引入矩阵：

${\bar{W}}_Q:=\left(e,\frac{Qe}{4},\frac{Q^{2}e}{4},\cdots ,\frac{Q^{n-1}e}{4}\right)$ .

由 $Qe=\left(A+D\right)e=2d=4\hat{d}$ 可知 ${\bar{W}}_Q$ 为整数矩阵。

定义5 [2] 对素数p，矩阵M在域F_p上的秩记为 $ran{k}_p\left(M\right)$ 。

引理6 [2] 设M为对称阵，u为任意向量。则：

(1) $u^{\text{T}}u\equiv e^{\text{T}}u\left(\mathrm{mod}2\right)$

(2) $u^{\text{T}}Mu\equiv {\xi }_M^{\text{T}}u\left(\mathrm{mod}2\right)$ 。

其中 ${\xi }_M$ 为矩阵M的主对角元构成的列向量。

引理7 对任意的整数矩阵M，存在幺模矩阵U、V，使得 $M=U\text{diag}\left(d_1\text{,}{d}_2\text{,}\cdots ,d_n\right)V$ ，其中 $d_i|d_{i+1}\left(i=1,2,\cdots ,n-1\right)$ 。其中 $d_i$ 称为矩阵M的不变因子， $\text{diag}\left(d_1\text{,}{d}_2\text{,}\cdots ,d_n\right)$ 称为矩阵M的Smith标准型。

3. 问题解决

为证明定理4，首先提出以下引理并对其证明。

引理8 设图G为欧拉图，其对应的无符号拉普拉斯矩阵为Q，则 $e^{\text{T}}{Q}^{2}e\equiv 0\left(\mathrm{mod}16\right)$ ，且对任意的整数 $k\ge 3$ ，有 $e^{\text{T}}{Q}^{k}e\equiv 0\left(\mathrm{mod}32\right)$ 。

证明：首先论证 $e^{\text{T}}{Q}^{2}e\equiv 0\left(\mathrm{mod}16\right)$ 成立。由 $Qe=\left(A+D\right)e=2d=4\hat{d}$ 可知 $e^{\text{T}}{Q}^{2}e={\left(Qe\right)}^{\text{T}}\left(Qe\right)=4d^{\text{T}}d=16{\hat{d}}^{\text{T}}\hat{d}\equiv 0\left(\mathrm{mod}16\right)$ 。

其次，证明对任意的整数 $k\ge 3$ ，有 $e^{\text{T}}{Q}^{k}e\equiv 0\left(\mathrm{mod}32\right)$ 。

其中 $e^{\text{T}}{Q}^{k}e={\left(Qe\right)}^{\text{T}}{Q}^{k-2}\left(Qe\right)=4d^{\text{T}}{Q}^{k-2}d=16{\hat{d}}^{\text{T}}{Q}^{k-2}\hat{d}$ ，令 $l=k-2$ ，则 $e^{\text{T}}{Q}^{k}e=16{\hat{d}}^{\text{T}}{Q}^l\hat{d}$ ，只需论证对任意的整数 $l\ge 1$ 有 ${\hat{d}}^{\text{T}}{Q}^l\hat{d}\equiv 0\left(\mathrm{mod}2\right)$ ，则引理得证。

再者，基于n的奇偶性进行分类讨论。

当n为偶数，则

${\hat{d}}^{\text{T}}{Q}^l\hat{d}={\left(Q^{\frac{l}{2}}\hat{d}\right)}^{\text{T}}\left(Q^{\frac{l}{2}}\hat{d}\right)\equiv {\hat{d}}^{\text{T}}{Q}^{\frac{l}{2}}e={\hat{d}}^{\text{T}}{Q}^{\frac{l}{2}-1}\left(Qe\right)=4{\hat{d}}^{\text{T}}{Q}^{\frac{l}{2}-1}\hat{d}\equiv 0\left(\mathrm{mod}4\right)$ ;

当n为奇数，则

${\hat{d}}^{\text{T}}{Q}^l\hat{d}={\left(Q^{\frac{l-1}{2}}\hat{d}\right)}^{\text{T}}Q\left(Q^{\frac{l-1}{2}}\hat{d}\right)\equiv {\xi }_Q^{\text{T}}\left(Q^{\frac{l-1}{2}}\hat{d}\right)=d^{\text{T}}\left(Q^{\frac{l-1}{2}}\hat{d}\right)=2{\hat{d}}^T\left(Q^{\frac{l-1}{2}}\hat{d}\right)\equiv 0\left(\mathrm{mod}2\right)$ ,

综上所述， ${\hat{d}}^{\text{T}}{Q}^l\hat{d}\equiv 0\left(\mathrm{mod}2\right)$ ，引理得证。

引理9 设G为欧拉图，其对应的无符号拉普拉斯矩阵为Q，则 $e^{\text{T}}Qe\equiv 0\left(\mathrm{mod}4\right)$ 。且当 $e^{\text{T}}Qe\equiv 0\left(\mathrm{mod}8\right)$ 时， $e^{\text{T}}{Q}^{2}e\equiv 0\left(\mathrm{mod}32\right)$ ；当 $e^{\text{T}}Qe\equiv 4\left(\mathrm{mod}8\right)$ 时， $e^{\text{T}}{Q}^{2}e\equiv 16\left(\mathrm{mod}32\right)$ 。

证明：基于 $e^{\text{T}}Qe$ 对8的余数进行分类讨论。

当 $e^{\text{T}}Qe=4e^{\text{T}}\hat{d}\equiv 0\left(\mathrm{mod}8\right)$ ，则 $e^{\text{T}}\hat{d}\equiv 0\left(\mathrm{mod}2\right)$ 。

又由 ${\hat{d}}^{\text{T}}\hat{d}\equiv e^{\text{T}}\hat{d}\left(\mathrm{mod}2\right)$ 可得当 $e^{\text{T}}\hat{d}\equiv 0\left(\mathrm{mod}2\right)$ 时，有 $e^{\text{T}}{Q}^{2}e={\left(Qe\right)}^{\text{T}}\left(Qe\right)=16{\hat{d}}^{\text{T}}\hat{d}\equiv 16e^{\text{T}}\hat{d}\equiv 0\left(\mathrm{mod}32\right)$ 。

同理，当 $e^{\text{T}}Qe=4e^{\text{T}}\hat{d}\equiv 4\left(\mathrm{mod}8\right)$ ，则 $e^{\text{T}}\hat{d}\equiv 1\left(\mathrm{mod}2\right)$ 。

再由 ${\hat{d}}^{\text{T}}\hat{d}\equiv e^{\text{T}}\hat{d}\equiv 1\left(\mathrm{mod}2\right)$ 可得 $e^{\text{T}}{Q}^{2}e={\left(Qe\right)}^{\text{T}}\left(Qe\right)=16{\hat{d}}^{\text{T}}\hat{d}\equiv 16e^{\text{T}}\hat{d}\equiv 16\left(\mathrm{mod}32\right)$ 。综上，引理得证。

引理10 设图G为n阶欧拉图，则 ${\text{rank}}_2\left({\bar{W}}_Q\right)\le \lceil \frac{n+1}{2}\rceil$ 。

证明：本定理基于n的奇偶性进行分类讨论。

当n为偶数，令 $W_1=\left(2e,\frac{Qe}{2},\frac{Q^{2}e}{4},\cdots ,\frac{Q^{n-1}e}{4}\right)$ ，由引理8可得：

$\begin{array}{c}{\bar{W}}_Q^{\text{T}}{\bar{W}}_1=\left(\begin{array}{ccccc}2e^{\text{T}}e& \frac{e^{\text{T}}Qe}{2}& \frac{e^{\text{T}}{Q}^{2}e}{4}& \cdots & \frac{e^{\text{T}}{Q}^{n-1}e}{4}\\ \frac{e^{\text{T}}Qe}{2}& \frac{e^{\text{T}}{Q}^{2}e}{8}& \frac{e^{\text{T}}{Q}^{3}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{n}e}{16}\\ \frac{e^{\text{T}}{Q}^{2}e}{2}& \frac{e^{\text{T}}{Q}^{3}e}{8}& \frac{e^{\text{T}}{Q}^{4}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{n+1}e}{16}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ \frac{e^{\text{T}}{Q}^{n-1}e}{2}& \frac{e^{\text{T}}{Q}^{n}e}{8}& \frac{e^{\text{T}}{Q}^{n+1}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{2n-2}e}{16}\end{array}\right)\\ \equiv \left(\begin{array}{ccccc}0& 0& 0& \cdots & 0\\ 0& 0& 0& \cdots & 0\\ 0& 0& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 0\end{array}\right)\left(\mathrm{mod}2\right)\end{array}$

由定义 $W_1$ 是由 ${\bar{W}}_Q$ 的前两列乘2得到的矩阵，因此 $ran{k}_2\left(W_1\right)\ge ran{k}_2\left({\bar{W}}_Q\right)-2$ ，再由 $ran{k}_2\left({\bar{W}}_Q^{\text{T}}\right)+ran{k}_2\left(W_1\right)\le ran{k}_2\left({\bar{W}}_Q^{\text{T}}{W}_1\right)+n=n$ 及 $ran{k}_2\left({\bar{W}}_Q\right)=ran{k}_2\left({\bar{W}}_Q^{\text{T}}\right)$ 可得

$ran{k}_2\left({\bar{W}}_Q\right)\le \frac{n+2}{2}=\lceil \frac{n+1}{2}\rceil$ .

当n为奇数，基于 $e^{\text{T}}Qe$ 对8的余数再度进行分类讨论：

若 $e^{\text{T}}Qe\equiv 0\left(\mathrm{mod}8\right)$ ，由引理9可知 $e^{\text{T}}{Q}^{2}e\equiv 0\left(\mathrm{mod}32\right)$ 。再由引理8可得：

$\begin{array}{c}{\bar{W}}_Q^{\text{T}}{\bar{W}}_Q=\left(\begin{array}{ccccc}{e}^{\text{T}}e& \frac{e^{\text{T}}Qe}{4}& \frac{e^{\text{T}}{Q}^{2}e}{4}& \cdots & \frac{e^{\text{T}}{Q}^{n-1}e}{4}\\ \frac{e^{\text{T}}Qe}{4}& \frac{e^{\text{T}}{Q}^{2}e}{16}& \frac{e^{\text{T}}{Q}^{3}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{n}e}{16}\\ \frac{e^{\text{T}}{Q}^{2}e}{4}& \frac{e^{\text{T}}{Q}^{3}e}{16}& \frac{e^{\text{T}}{Q}^{4}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{n+1}e}{16}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ \frac{e^{\text{T}}{Q}^{n-1}e}{4}& \frac{e^{\text{T}}{Q}^{n}e}{16}& \frac{e^{\text{T}}{Q}^{n+1}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{2n-2}e}{16}\end{array}\right)\\ \equiv \left(\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ 0& 0& 0& \cdots & 0\\ 0& 0& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 0\end{array}\right)\left(\mathrm{mod}2\right)\end{array}$

再由秩不等式可得 $2ran{k}_2\left({\bar{W}}_Q\right)\le n+1$ ，即 $ran{k}_2\left({\bar{W}}_Q\right)\le \frac{n+1}{2}=\lceil \frac{n+1}{2}\rceil$ 。

若 $e^{\text{T}}Qe\equiv 4\left(\mathrm{mod}8\right)$ ，由引理9可知 $e^{\text{T}}{Q}^{2}e\equiv 16\left(\mathrm{mod}32\right)$ 。再由引理8可得：

$\begin{array}{c}{\bar{W}}_Q^{\text{T}}{\bar{W}}_Q=\left(\begin{array}{ccccc}{e}^{\text{T}}e& \frac{e^{\text{T}}Qe}{4}& \frac{e^{\text{T}}{Q}^{2}e}{4}& \cdots & \frac{e^{\text{T}}{Q}^{n-1}e}{4}\\ \frac{e^{\text{T}}Qe}{4}& \frac{e^{\text{T}}{Q}^{2}e}{16}& \frac{e^{\text{T}}{Q}^{3}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{n}e}{16}\\ \frac{e^{\text{T}}{Q}^{2}e}{4}& \frac{e^{\text{T}}{Q}^{3}e}{16}& \frac{e^{\text{T}}{Q}^{4}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{n+1}e}{16}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ \frac{e^{\text{T}}{Q}^{n-1}e}{4}& \frac{e^{\text{T}}{Q}^{n}e}{16}& \frac{e^{\text{T}}{Q}^{n+1}e}{16}& \cdots & \frac{e^{\text{T}}{Q}^{2n-2}e}{16}\end{array}\right)\\ \equiv \left(\begin{array}{ccccc}1& 1& 0& \cdots & 0\\ 1& 1& 0& \cdots & 0\\ 0& 0& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 0\end{array}\right)\left(\mathrm{mod}2\right)\end{array}$

同理，由秩不等式可得 $2ran{k}_2\left({\bar{W}}_Q\right)\le n+1$ ，即 $ran{k}_2\left({\bar{W}}_Q\right)\le \frac{n+1}{2}=\lceil \frac{n+1}{2}\rceil$ 。综上所述，命题得证。

引理11 设图G为n阶欧拉图，则 $2^{\lfloor \frac{5n-5}{2}\rfloor }|\det \left(W_Q\right)$ 。

证明：因为 $ran{k}_2\left({\bar{W}}_Q\right)\le \lceil \frac{n+1}{2}\rceil$ ，所以 ${\bar{W}}_Q$ 对角线上的偶元素至少为 $n-\lceil \frac{n+1}{2}\rceil =\lfloor \frac{n-1}{2}\rfloor$ 个，由此可得 $2^{\lfloor \frac{n-1}{2}\rfloor }|\det \left({\bar{W}}_Q\right)$ 。再由 ${\bar{W}}_Q$ 的定义可知 $2^{\lfloor \frac{5n-5}{2}\rfloor }|\det \left(W_Q\right)$ 。

定理12 设图 $G\in {\Sigma }_n$ ，则 $ran{k}_2\left({\bar{W}}_Q\right)=\lceil \frac{n+1}{2}\rceil$ ，且 ${\bar{W}}_Q$ 的Smith标准型为：

$S=\text{diag(}\underset{\lceil \frac{n+1}{2}\rceil }{\underset{︸}{1,1,\cdots ,1}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2,2,\cdots ,2b}})$ .

证明：因 $G\in {\Sigma }_n$ ，所以 $2^{-\lfloor \frac{n-1}{2}\rfloor }·\det \left({\bar{W}}_Q\right)$ 为奇数且无平方因子。设 $\det \left({\bar{W}}_Q\right)=\pm 2^{\lfloor \frac{n-1}{2}\rfloor }{p}_1{p}_2\cdots p_s$ ，其中 $p_i\left(i=1,2,\cdots ,s\right)$ 为互不相同的奇素数。

假设 ${\bar{W}}_Q$ 的Smith标准型为 $S=\text{diag}\left(1,1,\cdots ,1,2^{l_1},2^{l_2},\cdots ,2^{l_t}b\right)$ ，其中 $l_1\le l_2\le \cdots \le l_t$ ， $b=p_1{p}_2\cdots p_s$ 为奇数且无平方因子。

由引理10可知 $ran{k}_2\left({\bar{W}}_Q\right)\le \lceil \frac{n+1}{2}\rceil$ ，即 $n-t\le \lceil \frac{n+1}{2}\rceil$ 。

因此有 $t\ge n-\lceil \frac{n+1}{2}\rceil =\lfloor \frac{n-1}{2}\rfloor$ 。

此外，由于 $l_1+l_2+\cdots +l_t=\lfloor \frac{n-1}{2}\rfloor$ 且 $\det \left({\bar{W}}_Q\right)=\pm \det \left(S\right)$ ，可得 $l_1=l_2=\cdots =l_t=1$ 及 $t=\lfloor \frac{n-1}{2}\rfloor$ 。

命题得证。

以下将对定理4进行证明：

证明：由定义 $W_Q=\left(e,Qe,Q^{2}e,\cdots ,Q^{n-1}e\right)$ ， $Q^{i}e\equiv 0\left(\mathrm{mod}4\right)$ ， $\left(i=1,2,\cdots ,n-1\right)$ ， $G\in {\Sigma }_n$ ，可得不失一般性设 $W_Q$ 的Smith标准型为 $S=\text{diag}\left(1,2^{2+m_1},2^{2+m_2},\cdots ,2^{2+m_{n-1}}b\right)$ ，其中b为奇数且无平方因子。

因此存在幺模矩阵U、V，使得 $W_Q=U\text{diag}\left(1,2^{2+m_1},2^{2+m_2},\cdots ,2^{2+m_{n-1}}b\right)V$ ，其中 $1\le m_1\le m_2\le \cdots \le m_{n-1}$ 。即：

$\begin{array}{c}{U}^{-1}{W}_Q=\left(U^{-1}e,U^{-1}Qe,U^{-1}{Q}^{2}e,\cdots ,U^{-1}{Q}^{n-1}e\right)\\ =\text{diag}\left(1,2^{2+m_1},2^{2+m_2},\cdots ,2^{2+m_{n-1}}b\right)V\\ =\left(\begin{array}{cc}1& 0\\ 0& 4\Lambda \end{array}\right)\left(\begin{array}{cc}a& {\alpha }^{\text{T}}\\ \beta & V_1\end{array}\right)\\ =\left(\begin{array}{cc}a& {\alpha }^{\text{T}}\\ 4\Lambda \beta & 4\Lambda V_1\end{array}\right)\end{array}$

其中， $\Lambda =\text{diag}\left(2^{m_1},2^{m_2},\cdots ,2^{m_{n-1}}b\right)$ ， $V=\left(\begin{array}{cc}a& {\alpha }^{\text{T}}\\ \beta & V_1\end{array}\right)$ ，且a为一个整数， $\alpha$ 和 $\beta$ 为 $n-1$ 维列向量， $V_1$ 为 $n-1$ 阶方阵。

由 $\left(U^{-1}e,U^{-1}Qe,\cdots ,U^{-1}{Q}^{n-1}e\right)=\left(\begin{array}{cc}a& {\alpha }^{\text{T}}\\ 4\Lambda \beta & 4\Lambda V_1\end{array}\right)$ 可得：

$\left(U^{-1}e,U^{-1}\frac{Qe}{4},\cdots ,U^{-1}\frac{Q^{n-1}e}{4}\right)=\left(\begin{array}{cc}a& \frac{{\alpha }^{\text{T}}}{4}\\ 4\Lambda \beta & \Lambda V_1\end{array}\right)$ ,

即：

${\bar{W}}_Q=U\left(\begin{array}{cc}a& \frac{{\alpha }^{\text{T}}}{4}\\ 4\Lambda \beta & \text{Λ}{V}_1\end{array}\right)=U\left(\begin{array}{cc}1& 0\\ 0& \Lambda \end{array}\right)\left(\begin{array}{cc}a& \frac{{\alpha }^{\text{T}}}{4}\\ 4\beta & V_1\end{array}\right)=U\left(\begin{array}{cc}1& 0\\ 0& \Lambda \end{array}\right)V^{\prime }$ (1)

其中 $V^{\prime }:=\left(\begin{array}{cc}a& \frac{{\alpha }^{\text{T}}}{4}\\ 4\beta & V_1\end{array}\right)$ 为整数矩阵。

注意 $\det V^{\prime }\equiv \left(\begin{array}{cc}a& \frac{{\alpha }^{\text{T}}}{4}\\ 0& V_1\end{array}\right)\equiv a\det V_1\left(\mathrm{mod}4\right)$ ，此外有 $\det V\equiv \left(\begin{array}{cc}a& {\alpha }^{\text{T}}\\ \beta & V_1\end{array}\right)\equiv \left(\begin{array}{cc}a& 0\\ \beta & V_1\end{array}\right)\equiv a\det V_1=\pm 1\left(\mathrm{mod}4\right)$ 。

对(1)两边同时取行列式可得 $\det {\bar{W}}_Q=2^{\lfloor \frac{n-1}{2}\rfloor }b=\pm 2^{{\displaystyle \underset{i=1}{\overset{n-1}{\sum }}{m}_i}}b\det V^{\prime }$ 。由上式可知 $\det V^{\prime }$ 为奇数，因此等式成立当且仅当 $2^{\lfloor \frac{n-1}{2}\rfloor }=2^{{\displaystyle \underset{i=1}{\overset{n-1}{\sum }}{m}_i}}$ 且 $\det V^{\prime }=\pm 1$ ，即 $V^{\prime }$ 为幺模矩阵。

由引理7可知 $\left(\begin{array}{cc}1& 0\\ 0& \Lambda \end{array}\right)$ 为 ${\bar{W}}_Q$ 的Smith标准型。再由引理12可知：

$\Lambda =\text{diag(}\underset{\lceil \frac{n+1}{2}\rceil -1}{\underset{︸}{1,1,\cdots ,1}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2,2,\cdots ,2b}})$ .

由上述等式及 ${\bar{W}}_Q$ 的定义可知 $W_Q$ 的Smith标准型为 $S=\text{diag(}\underset{\lceil \frac{n+1}{2}\rceil }{\underset{︸}{1,2^2,\cdots ,2^2}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2^3,2^3,\cdots ,2^{3}b}})$ ，定理4得证。

4. 结论

本文对极端条件下n阶欧拉图的无符号拉普拉斯矩阵的道矩阵 $W_Q$ 的Smith标准型进行刻画，并给出如下结论：

当 $W_Q$ 的行列式满足 $\det \left(W_Q\right)=\pm 2^{\lfloor \frac{5n-5}{2}\rfloor }b$ ，其中b为奇数且无平方因子时， $W_Q$ 的Smith标准型为 $\text{diag(}\underset{\lceil \frac{n+1}{2}\rceil }{\underset{︸}{1,2^2,\cdots ,2^2}},\underset{\lfloor \frac{n-1}{2}\rfloor }{\underset{︸}{2^3,2^3,\cdots ,2^{3}b}})$ 。

又因Smith标准型是图论中一个极为常用的工具，本结论可在相关领域中简化研究过程。例如，结合文献 [9] ，可更为快速计算非奇异整数矩阵的Smith标准型的乘子。

文章引用

魏靖园,吕思澄. 有关欧拉图Q-道矩阵Smith标准型的性质研究
Properties of the Smith Normal Form of the Q-Walk Matrix in Euler Graphs[J]. 理论数学, 2024, 14(03): 252-259. https://doi.org/10.12677/pm.2024.143103

参考文献