基于傅里叶相似变换的图距离矩阵分解研究

doi:10.12677/orf.2025.152059

期刊菜单

基于傅里叶相似变换的图距离矩阵分解研究
Research on Graph Distance Matrix Decomposition Based on Fourier Similarity Transformation

DOI: 10.12677/orf.2025.152059, PDF, HTML, XML,
作者: 闫晓静：长安大学理学院，陕西西安
关键词: 傅里叶相似变换；图距离矩阵；矩阵分解；距离公平划分；Fourier Similarity Transformation； Graph Distance Matrix； Matrix Decomposition； Distance Equitable Partition

摘要: 本文考虑图距离矩阵的分解问题。给定一个图，根据其顶点集的划分，我们定义了图距离矩阵的傅里叶相似变换。该变换由用于执行离散傅里叶变换的矩阵乘以图距离矩阵实现。我们证明了图距离矩阵在傅里叶相似变换下能够分解成多个较小矩阵的直和，当且仅当该图的顶点划分是距离公平划分。

Abstract: This paper considers the problem of decomposition of graph distance matrix. Given a graph, we define a Fourier similarity transform of its graph distance matrix based on the vertex partition, which is implemented by multiplying the matrices used to perform the Discrete Fourier transformation. We show that graph distance matrices can be decomposed into many smaller matrices under Fourier similarity transformation, if and only if the vertex partition of the graph is a distance equitable partition.

文章引用：闫晓静. 基于傅里叶相似变换的图距离矩阵分解研究[J]. 运筹与模糊学, 2025, 15(2): 1-7. https://doi.org/10.12677/orf.2025.152059

1. 引言

本文考虑简单无向图。设图 $G = (V (G), E (G))$ ，其中，顶点集 $V (G) = {1, 2, \cdot \cdot \cdot, n}$ ，边集 $E (G) = {e_{1}, e_{2}, \cdot \cdot \cdot, e_{m}}$ ；对 $V (G)$ 中的任意两个顶点 $i, j$ ，将顶点相邻记为 $i ~ j$ 。图 $G$ 的邻接矩阵 $A = A (G)$ 是一个对称的 $(0, 1)$ 矩阵，当顶点 $i ~ j$ 时，其元素为1，否则为0；邻接矩阵的特征值和特征向量定义为图的特征值与特征向量。对任意的 $i, j \in V (G)$ ，从 $i$ 到 $j$ 的具有最小长度的路称为 $i$ 到 $j$ 的最短路，其长度称为 $i$ 到 $j$ 的距离，记为 $d_{i j}$ ，以 $d_{i j}$ 为元素的矩阵定义为任意图 $G$ 的距离矩阵，记为 $D = {(d_{i j})}_{n \times n}$ 。

傅里叶变换在多个领域中具有广泛的应用。在数字信号处理中，它用于频域分析和信号滤波，帮助提取信号的频率特征，从而实现信号的压缩和增强。在图像处理领域，该变换可被用于图像去噪以及边缘检测，能够有效去除噪声并增强图像细节。在物理学中，矩阵傅里叶变换用于解决波动方程和热传导问题，提供频域分析工具来研究物理场的传播特性。在工程学中，该方法被应用于系统频域分析和信号处理，简化了复杂系统的响应分析[1] [2]。此外，在代数图论中，矩阵傅里叶变换被用于图谱分析，帮助揭示图的结构特性，如节点分布和网络流。这些应用展示了该变换在跨学科研究中的重要性。1965年，Cooley和Tukey [3]首次提出离散傅里叶变换用于分析和减少电话信号中的噪音干扰。它主要用来将信号从时域转换为频域，便于分析和处理频率成分，从而在通信系统中有效地去除噪声和干扰。这一工具的开发为现代信号处理奠定了基础，推动了多个领域的技术发展。S Winograd在[4]中探讨了离散傅里叶变换的新算法，该算法基于复杂度理论中的最新结果，能够推导出高效的卷积算法，进而用于获得新的离散傅里叶变换算法。Ivan Selesnick等人在[5]中讨论了图信号处理中的离散傅里叶变换及其在谱分解中的应用。Haemers等人在[6]中介绍了特征值的交错性质及其在图谱分解中的应用，为理解和优化复杂网络提供了理论依据。然而由于图和矩阵都是静态的对象，离散傅里叶变换尚未用于分解图形或矩阵，直到2021年，D. Lund、J. Drapeau和B. Webb在文献[7]中给出傅里叶相似变换的概念，建立起图的公平划分与傅里叶相似变换之间的关系，这一研究结果实现了图和其邻接矩阵的分解，即将一个图分解成较小图的集合，对应在图的邻接矩阵上得到了两个较小矩阵的直和。

考虑到关于图距离矩阵分解的研究内容较少，受D. Lund、J. Drapeau和B. Webb的启发，本文考虑图距离矩阵在傅里叶相似变换下分解的情况。首先给出距离公平划分和距离傅里叶相似变换矩阵的定义，接着进一步证明了距离矩阵在傅里叶相似变换下分解成两个矩阵的直和，这对于研究图距离矩阵的代数性质有着极大的帮助，从分解的矩阵直和中能够更容易计算矩阵的特征值、特征向量、零度以及矩阵的秩等数值，同时，将矩阵分解与傅里叶变换联系起来，给许多领域的实际应用提供了理论参考。

2. 预备知识

公平划分是图谱理论中一个非常有用的工具，它的商图展示了图的特征值与特征向量。首先给出距离公平划分的定义。

定义2.1 (距离公平划分)设图 $G$ ，顶点集为 $V (G) = {1, 2, \cdot \cdot \cdot, n}$ ，顶点划分设为 $π = {V_{1}, V_{2}, \cdot \cdot \cdot, V_{k}}$ ，其中，对任意的 $i, j \in {1, 2, \cdot \cdot \cdot, k}$ ，顶点集 $V_{i}$ 与 $V_{j}$ 不相交。设 $D$ 是图 $G$ 的距离矩阵，根据顶点划分 $π$ ，将 $D$ 写作

$D = [\begin{matrix} D [1, 1] & D [1, 2] & \dots & D [1, k] \\ D [2, 1] & D [2, 2] & \dots & D [2, k] \\ ⋮ & ⋮ & ⋮ \\ D [k, 1] & D [k, 2] & \dots & D [k, k] \end{matrix}]$ ，

对应的特征矩阵 $C = {(c_{i j})}_{n \times k}$ 可表示为 $c_{i j} = {\begin{cases} 1, i \in V_{j} \\ 0, 其他 \end{cases}$ 。那么距离商矩阵 $D_{π}$ 的元素就是矩阵 $D$ 对应块矩阵的平均行和，即有 ${(D_{π})}_{i j} = \frac{1}{| V_{i} |} j^{T} D [i, j] j = \frac{1}{| V_{i} |} {(C^{T} D C)}_{i j}$ ，其中， $j$ 是元素全为1的列向量，这就是说，如果矩阵 $D$ 的每个块矩阵 $D [i, j]$ 的行和是 ${(D_{π})}_{i j}$ ，或者有 $D C = C D_{π}$ ，那么就称 $π$ 是一个距离公平划分。

下面给出图距离矩阵的傅里叶相似变换矩阵，它的定义如下。

定义2.2 设图 $G$ ，顶点划分设为 $π = {V_{1}, V_{2}, \dots, V_{k}}$ ， $| V_{i} | = n_{i}$ ， $i = 1, 2, \dots, k$ ， $ω_{n} = e^{\frac{2 π}{n} i}$ 是 $n$ 次单位根，对于图距离矩阵 $D$ ，它的傅里叶相似变换矩阵为 $F S T_{π} (D) = W_{π}^{- 1} D W_{π}$ ，其中， $W_{n}$ 是如下块对角矩阵

$W_{π} = W_{n_{1}} \oplus W_{n_{2}} \oplus \dots \oplus W_{n_{k}} = [\begin{matrix} W_{n_{1}} \\ W_{n_{2}} \\ ⋱ \\ W_{n_{k}} \end{matrix}]$ ，

这里 $W_{n} = {[w_{i j}]}_{n \times n}$ ， $w_{i j} = ω_{n}^{(i - 1) (j - 1)}$ 。容易验证 $W_{n}^{- 1} = \frac{1}{n} W_{n}^{*}$ ，其中 $W_{n}^{*}$ 是 $W$ 的共轭转置矩阵。

在文献[7]中，D. Lund, J. Drapeau 和 B. Webb得到了无向图的邻接矩阵在傅里叶相似变换下的分解条件，具体如下。

定理2.1 对于一个图 $G = G (V, E)$ ，它的一个顶点划分为 $π = {V_{1}, V_{2}, \dots, V_{k}}$ 。根据此划分构造一个置换矩阵 $P$ 定义如下

$P = [e_{1}, e_{1 + n_{1}}, e_{1 + n_{1} + n_{2}}, \dots, e_{1 + \sum_{i = 1}^{k - 1} n_{i}}, e_{2}, e_{3}, \dots, e_{n_{1}}, e_{n_{1} + 2}, \dots, e_{n}]$ ，

这里 $e_{i}$ 表示单位矩阵 $I_{n}$ 的第 $i$ 列。那么邻接矩阵 $A$ 在置换的傅里叶相似变换下分解为矩阵的直和，即 $P^{- 1} F S T_{π} (A) P = A_{π} \oplus B \in ℂ^{n \times n}$ ，当且仅当 $π$ 是图 $G$ 的一个公平划分。

3. 图距离矩阵的傅里叶相似变换分解

多年来，矩阵分解是图谱理论中的一个热点研究问题，将矩阵分解为形式比较简单或具有某种特性的一些矩阵不仅能够明显反映出原矩阵的某些数值特征，这些分解的方法与过程也提供了某些有效的数值计算方法和理论分析根据。D. Lund, J. Drapeau和B. Webb在[7]中将图的公平划分与傅里叶相似变换结合起来，得到了图的邻接矩阵经过傅里叶相似变换分解为较小矩阵的直和，相当于图分解为较小的图的集合，且保留了图的谱。在这一节中，我们将此方法推广到图的距离矩阵，得到它们的分解矩阵。

定理3.1 设图 $G$ ，顶点划分设为 $π = {V_{1}, V_{2}, \cdot \cdot \cdot, V_{k}}$ ， $| V_{i} | = n_{i}$ ， $i = 1, 2, \cdot \cdot \cdot, k$ 。设 $D$ 是图 $G$ 的距离矩阵，根据给定的顶点划分构造一个置换矩阵 $P = [e_{1}, e_{1 + n_{1}}, e_{1 + n_{1} + n_{2}}, \cdot \cdot \cdot, e_{1 + \sum_{i = 1}^{k - 1} n_{i}}, e_{2}, e_{3}, \cdot \cdot \cdot, e_{n_{1}}, e_{n_{1} + 2}, \cdot \cdot \cdot, e_{n}]$ ，其中， $e_{i}$ 表示单位矩阵 $I_{n}$ 的第 $i$ 列，那么矩阵 $D$ 经过置换的傅里叶相似变换能够分解成两个矩阵的直和，即 $P^{- 1} F S T_{π} (D) P = D_{π} \oplus B \in ℂ^{n \times n}$ ，当且仅当 $π$ 是图 $G$ 的一个距离公平划分。

证明:一般地，对于图 $G$ 的顶点划分 $π = {V_{1}, V_{2}, \dots, V_{k}}$ ，假设顶点标号满足对 $1 \leq i < j \leq k$ ， $v_{x} \in V_{i}, v_{y} \in V_{j}$ 有 $1 \leq x < y \leq n$ 。根据顶点划分 $π$ 将矩阵 $D$ 记作

$D = [\begin{matrix} D [1, 1] & D [1, 2] & \dots & D [1, k] \\ D [2, 1] & D [2, 2] & \dots & D [2, k] \\ ⋮ & ⋮ & ⋮ \\ D [k, 1] & D [k, 2] & \dots & D [k, k] \end{matrix}]$ ，

则有

$F S T_{π} (D) = W_{π}^{- 1} D W_{π} = [\begin{matrix} \frac{1}{n_{1}} W_{n_{1}}^{*} D [1, 1] W_{n_{1}} & \frac{1}{n_{1}} W_{n_{1}}^{*} D [1, 2] W_{n_{2}} & \dots & \frac{1}{n_{1}} W_{n_{1}}^{*} D [1, k] W_{n_{k}} \\ \frac{1}{n_{2}} W_{n_{2}}^{*} D [2, 1] W_{n_{1}} & \frac{1}{n_{2}} W_{n_{2}}^{*} D [2, 2] W_{n_{2}} & \dots & \frac{1}{n_{2}} W_{n_{2}}^{*} D [2, k] W_{n_{k}} \\ ⋮ & ⋮ & ⋮ \\ \frac{1}{n_{k}} W_{n_{k}}^{*} D [k, 1] W_{n_{1}} & \frac{1}{n_{k}} W_{n_{k}}^{*} D [k, 2] W_{n_{2}} & \dots & \frac{1}{n_{k}} W_{n_{k}}^{*} D [k, k] W_{n_{k}} \end{matrix}]$ 。

由于置换矩阵将每个块矩阵 $\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}$ 的一行一列元素移到第 $i$ 行 $j$ 列位置，因此， $P^{- 1} F S T_{π} (D) P = D_{π} \oplus B \in ℂ^{n \times n}$ 相当于是说，对于每个块矩阵 $\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}$ ，它的左上角元素是某个常数，而其余一行一列元素均为0，也就是 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{x y} = {\begin{cases} {\tilde{d}}_{i j}, x = y = 1 \\ 0, 其他 \end{cases}$ ， ${\tilde{d}}_{i j}$ 是依赖于 $i$ ， $j$ 取值的占位符值。我们的目标是证明 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{x y} = {\begin{cases} {\tilde{d}}_{i j}, x = y = 1 \\ 0, 其他 \end{cases}$ 成立当且仅当 $π$ 是一个距离公平划分。

首先假设 $π$ 是一个距离公平划分，记 ${(D [i, j])}_{a b} = d_{a b}$ ，那么对 $\forall 1 \leq a \leq n_{i}$ ，有矩阵的行和 $\sum_{b = 1}^{n_{j}} d_{a b} = T_{i j}$ 是一个常数，因此有 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{x y} = \frac{1}{n_{i}} \sum_{a = 1}^{n_{i}} \sum_{b = 1}^{n_{j}} d_{a b} {\bar{ω}}_{n_{i}}^{(x - 1) (a - 1)} ω_{n_{j}}^{(y - 1) (b - 1)}$ 。

如果 $x = y = 1$ ，

${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{11} = \frac{1}{n_{i}} \sum_{a = 1}^{n_{i}} \sum_{b = 1}^{n_{j}} d_{a b} {\bar{ω}}_{n_{i}}^{0} ω_{n_{j}}^{0} = T_{i j}$ ，

由此可见， $x = y = 1$ 时，式子成立。

当 $x \neq 1, y = 1$ 时有

${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{x 1} = \frac{1}{n_{i}} \sum_{a = 1}^{n_{i}} \sum_{b = 1}^{n_{j}} d_{a b} {\bar{ω}}_{n_{i}}^{(x - 1) (a - 1)} ω_{n_{j}}^{0} = \frac{1}{n_{i}} \sum_{b = 1}^{n_{j}} d_{a b} (\sum_{a = 1}^{n_{i}} {\bar{ω}}_{n_{i}}^{(x - 1) (a - 1)}) = 0$ ，

同样地， $x = 1, y \neq 1$ 时有

${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{1 y} = \frac{1}{n_{i}} \sum_{a = 1}^{n_{i}} \sum_{b = 1}^{n_{j}} d_{a b} {\bar{ω}}_{n_{i}}^{0} ω_{n_{j}}^{(y - 1) (b - 1)} = \frac{1}{n_{i}} \sum_{a = 1}^{n_{i}} d_{a b} (\sum_{b = 1}^{n_{j}} ω_{n_{j}}^{(y - 1) (b - 1)}) = 0$ ，

因此可证得式子 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{x y} = {\begin{cases} {\tilde{d}}_{i j}, x = y = 1 \\ 0, 其他 \end{cases}$ 成立。

反过来，对图 $G$ 的顶点划分 $π$ ，若有 $P^{- 1} F S T_{π} (D) P = D_{π} \oplus B$ ，即相当于式子 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{x y} = {\begin{cases} {\tilde{d}}_{i j}, x = y = 1 \\ 0, 其他 \end{cases}$ 成立，由此证明 $π$ 是一个距离公平划分，即想要证得按照顶点划分 $π$ 得到的 $D$ 的分块矩阵的平均行和 $\sum_{b = 1}^{n_{j}} d_{a b}$ 是常数。由于

$F S T_{π} (D) = [\begin{matrix} \frac{1}{n_{1}} W_{n_{1}}^{*} D [1, 1] W_{n_{1}} & \frac{1}{n_{1}} W_{n_{1}}^{*} D [1, 2] W_{n_{2}} & \dots & \frac{1}{n_{1}} W_{n_{1}}^{*} D [1, k] W_{n_{k}} \\ \frac{1}{n_{2}} W_{n_{2}}^{*} D [2, 1] W_{n_{1}} & \frac{1}{n_{2}} W_{n_{2}}^{*} D [2, 2] W_{n_{2}} & \dots & \frac{1}{n_{2}} W_{n_{2}}^{*} D [2, k] W_{n_{k}} \\ ⋮ & ⋮ & ⋮ \\ \frac{1}{n_{k}} W_{n_{k}}^{*} D [k, 1] W_{n_{1}} & \frac{1}{n_{k}} W_{n_{k}}^{*} D [k, 2] W_{n_{2}} & \dots & \frac{1}{n_{k}} W_{n_{k}}^{*} D [k, k] W_{n_{k}} \end{matrix}]$ ，

且 $W_{n_{j}}$ 的第一列元素全是 $1$ ，考虑块矩阵 $\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}$ 的第一列，即 $\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] Ι_{n_{j}}$ ，其中 $Ι_{n_{j}}$ 是长度为 $n_{j}$ 的全 $1$ 列向量。记矩阵 $W_{n_{i}}^{*} D [i, j] = K$ ，那么矩阵 $\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] Ι_{n_{j}}$ 相当于是标量 $\frac{1}{n_{i}}$ 乘上矩阵 $K$ 的行和。将矩阵 $K$ 的元素表示成 $K_{x y} = \sum_{a = 1}^{n_{i}} d_{a y} ω^{- (x - 1) (a - 1)}$ ，那么矩阵 $K$ 的第 $x$ 行行和可以表示成

$\sum_{b = 1}^{n_{j}} \sum_{a = 1}^{n_{i}} d_{a b} ω_{n_{i}}^{- (x - 1) (a - 1)} = \sum_{a = 1}^{n_{i}} ω_{n_{i}}^{- (x - 1) (a - 1)} (\sum_{b = 1}^{n_{j}} d_{a b})$ 。

由式子 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] W_{n_{j}}]}_{x y} = {\begin{cases} {\tilde{d}}_{i j}, x = y = 1 \\ 0, 其他 \end{cases}$ 可以知道，当 $x \geq 2$ 时，有 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] Ι_{n_{j}}]}_{x 1} = 0$ 成立，则 ${[\frac{1}{n_{i}} W_{n_{i}}^{*} D [i, j] Ι_{n_{j}}]}_{x 1} = \frac{1}{n_{i}} \sum_{a = 1}^{n_{i}} ω_{n_{i}}^{- (x - 1) (a - 1)} (\sum_{b = 1}^{n_{j}} d_{a b}) = 0$ ，记 $R_{a} = \sum_{b = 1}^{n_{j}} d_{a b}$ ，这相当于 $\sum_{a = 1}^{n_{i}} ω_{n_{i}}^{- (x - 1) (a - 1)} R_{a} = 0$ ，用矩阵表示出来有

$[\begin{matrix} 1 & ω_{n_{i}}^{- 1} & \dots & ω_{n_{i}}^{- (n_{i} - 1)} \\ 1 & ω_{n_{i}}^{- 2} & \dots & ω_{n_{i}}^{- 2 (n_{i} - 1)} \\ ⋮ & ⋮ & ⋮ \\ 1 & ω_{n_{i}}^{- (n_{i} - 1)} & \dots & ω_{n_{i}}^{- {(n_{i} - 1)}^{2}} \end{matrix}] [\begin{matrix} R_{1} \\ R_{2} \\ ⋮ \\ R_{n_{i}} \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}]$ ，

由于矩阵 $[\begin{matrix} 1 & ω_{n_{i}}^{- 1} & \dots & ω_{n_{i}}^{- (n_{i} - 1)} \\ 1 & ω_{n_{i}}^{- 2} & \dots & ω_{n_{i}}^{- 2 (n_{i} - 1)} \\ ⋮ & ⋮ & ⋮ \\ 1 & ω_{n_{i}}^{- (n_{i} - 1)} & \dots & ω_{n_{i}}^{- {(n_{i} - 1)}^{2}} \end{matrix}]$ 是离散傅里叶变换矩阵 $W_{n_{i}}$ 的逆矩阵去掉了第一行元素，所以维数是 $n_{i} - 1$ ，由此可知其零空间的维数是1，由于对任意的 $k = 1, 2, \dots, n_{i} - 1$ ，有 $\sum_{s = 0}^{n_{i} - 1} ω_{n_{i}}^{\pm k s} = 0$ ，所以 $Ι_{n_{i}}$ 在零空间中，则有 $R_{a} = R_{b}, 1 \leq a, b \leq n_{i}$ ，那么可以知道 $R_{a} = \sum_{b = 1}^{n_{j}} d_{a b}$ 是一个常数，因此证得 $π$ 是一个距离公平划分。

考虑特殊图类星图，具有 $n$ 个顶点的星图记为 $S_{n}$ ，其距离矩阵经过傅里叶相似变换能够分解成距离商矩阵和一个对角矩阵的直和，且对角矩阵的元素能够清晰地刻画出来，我们用以下定理说明。

定理3.2 设星图 $S_{n}$ ，距离矩阵为 $D$ ，假设顶点划分 $π : V = {V_{1}, V_{2}}$ ，其中， $| V_{1} | = 1$ ， $| V_{2} | = n - 1$ ，则可以得到， $P^{- 1} F S T_{π} (D) P = D_{π} \oplus Λ$ ，其中 $D_{π}$ 是2阶距离商矩阵， $Λ$ 是 $n - 2$ 阶对角矩阵。

证明:由 $π : V = {V_{1}, V_{2}}$ 可知，它也是一个距离公平划分，将距离矩阵分块表示为形式

$D = (\begin{matrix} 0 & j^{T} \\ j & \overset{⌢}{D} \end{matrix})$ ，

其中， $j$ 是 $n - 1$ 维全1列向量， $\overset{⌢}{D}$ 是 $n - 1$ 阶循环矩阵，且

${FST}_{π} (D) = (\begin{matrix} 0 & W_{1}^{- 1} j^{T} W_{n - 1} \\ W_{n - 1}^{- 1} j W_{1} & W_{n - 1}^{- 1} \overset{⌢}{D} W_{n - 1} \end{matrix})$ ，

记 ${\overset{⌢}{d}}_{1}, {\overset{⌢}{d}}_{2}, \dots, {\overset{⌢}{d}}_{n - 1}$ 为 $\overset{⌢}{D}$ 的第一行元素，将 $W_{n - 1}$ 按列向量分块写成 $W_{n - 1} = (w_{1}, w_{2}, \dots, w_{n - 1})$ ，定义 $E = (e_{n - 1}, e_{1}, e_{2}, \dots, e_{n - 2})$ 为循环置换矩阵， $e_{i}$ 表示第 $i$ 个元素为 $1$ ，其余元素为 $0$ 的单位向量，由于 $\overset{⌢}{D}$ 可以由矩阵 $E^{0} = I, E, \dots, E^{n - 2}$ 的线性组合表出，即 $\overset{⌢}{D} = \sum_{i = 1}^{n - 1} {\overset{⌢}{d}}_{i} E^{i - 1}$ ，我们可以看到 $\overset{⌢}{D} w_{i} = \sum_{i = 1}^{n - 1} {\overset{⌢}{d}}_{i} ω_{n - 1}^{i - 1} w_{i}$ ，因此对任意的 $i = 1, 2, \dots, n - 1$ ， $w_{i}$ 是矩阵 $\overset{⌢}{D}$ 对应于特征值 ${\overset{⌢}{λ}}_{i} = \sum_{i = 1}^{n - 1} {\overset{⌢}{d}}_{i} ω_{n - 1}^{i - 1}$ 的特征向量，所以有 $\overset{⌢}{D} W_{n - 1} = W_{n - 1} Λ$ ，这相当于 $W_{n - 1}^{- 1} \overset{⌢}{D} W_{n - 1} = Λ$ ，即 $W_{n - 1}^{- 1} \overset{⌢}{D} W_{n - 1}$ 是一个对角矩阵，对角元为 ${\overset{⌢}{λ}}_{i} = \sum_{i = 1}^{n - 1} {\overset{⌢}{d}}_{i} ω_{n - 1}^{i - 1}$ ，那么 ${\overset{⌢}{λ}}_{1} = \sum_{i = 1}^{n - 1} {\overset{⌢}{d}}_{i} ω_{n - 1}^{1 - 1} = 2 (n - 2)$ ，因此可以得到

${FST}_{π} (D) = (\begin{matrix} 0 & n - 1 & 0 & \dots & 0 \\ 1 & 2 (n - 2) & 0 & \dots & 0 \\ 0 & 0 & {\overset{⌢}{λ}}_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & {\overset{⌢}{λ}}_{n - 1} \end{matrix}) = (\begin{matrix} D_{π} & 0 \\ 0 & Λ \end{matrix})$ ，

其中 $D_{π} = (\begin{matrix} 0 & n - 1 \\ 1 & 2 (n - 2) \end{matrix})$ ， $Λ = diag ({\overset{⌢}{λ}}_{2}, {\overset{⌢}{λ}}_{3}, \dots, {\overset{⌢}{λ}}_{n - 2})$ ，即 $P^{- 1} F S T_{π} (D) P = D_{π} \oplus Λ$ ，定理得证。

下面举一个一般图类的例子说明以上定理。

Figure 1. Equitable partition graph of the distances of the 8 vertices

图1. 8个顶点的距离公平划分图

例3.1 在图1中，顶点划分 $π = {V_{1}, V_{2}, V_{3}}$ ， $V_{1} = {1, 2}, V_{2} = {3, 4}, V_{3} = {5, 6, 7, 8}$ ，根据定义可知它是一个距离公平划分，可以得到它经过傅里叶相似变换后的分解结果。

$D = [\begin{matrix} 0 & 4 & 1 & 5 & 1 & 2 & 3 & 2 \\ 4 & 0 & 5 & 1 & 3 & 2 & 1 & 2 \\ 1 & 5 & 0 & 6 & 2 & 3 & 4 & 3 \\ 5 & 1 & 6 & 0 & 4 & 3 & 2 & 3 \\ 1 & 3 & 2 & 4 & 0 & 1 & 2 & 1 \\ 2 & 2 & 3 & 3 & 1 & 0 & 1 & 2 \\ 3 & 1 & 4 & 2 & 2 & 1 & 0 & 1 \\ 2 & 2 & 3 & 3 & 1 & 2 & 1 & 0 \end{matrix}]$ ， $P^{- 1} F S T_{π} (D) P = [\begin{matrix} 4 & 6 & 8 & 0 & 0 & 0 & 0 & 0 \\ 6 & 6 & 12 & 0 & 0 & 0 & 0 & 0 \\ 4 & 6 & 4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 4 & - 4 & - 2 & 0 & - 2 \\ 0 & 0 & 0 & - 4 & - 6 & - 2 & 0 & - 2 \\ 0 & 0 & 0 & - 1 & - 1 & - 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & - 1 & 0 & 0 & - 2 \end{matrix}]$ 。

从分解结果看，相比于距离矩阵 $D$ ， $P^{- 1} F S T_{π} (D) P$ 能够更清晰地看出矩阵的秩、零度等代数性质，这极大地简化了计算矩阵的特征值、特征向量等的运算过程，能够帮助我们更好地研究图的距离矩阵，在实际应用中也能提高运算效率。并且经过Mathematica软件编程搜索验证，我们找到一类图，将它的顶点划分为3个部分，当顶点集 $V_{3}$ 中的顶点数为 $2 n$ $(n 为正整数)$ 个，且上下顶点数和边数都对应相等时，其距离矩阵都能通过傅里叶相似变换分解成两个矩阵的直和。

4. 结语

矩阵分解在矩阵理论的研究与应用中有着十分重要的作用，与常用的一些矩阵分解如矩阵的三角分解、QR分解、满秩分解以及奇异值分解等分解形式相比，本文引入傅里叶相似变换矩阵，通过它的特殊结构与性质，建立起图的距离矩阵在傅里叶相似变换下分解成两个较小矩阵的直和的条件，在代数方面，它能更直观地反映出原矩阵的秩、行列式、特征值、零度等数值特征，简化了运算过程；同时，在实际应用中，结合傅里叶变换也为图像压缩处理、信号分解等许多领域提供了新的数值计算方法以及理论依据。鉴于图的距离矩阵的相关研究较少，后续将深入研究推广此方法，找到能够通过此方法进行距离矩阵分解的更多图类。

参考文献

[1]	Petrou, M. and Petrou, C. (2010). Image Processing: The Fundamentals. John Wiley & Sons. https://doi.org/10.1002/9781119994398
[2]	Wedeen, V.J., Hagmann, P., Tseng, W.I., Reese, T.G. and Weisskoff, R.M. (2005) Mapping Complex Tissue Architecture with Diffusion Spectrum Magnetic Resonance Imaging. Magnetic Resonance in Medicine, 54, 1377-1386. https://doi.org/10.1002/mrm.20642
[3]	Cooley, J.W. and Tukey, J.W. (1965) An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 19, 297-301. https://doi.org/10.1090/s0025-5718-1965-0178586-1
[4]	Winograd, S. (1976) On Computing the Discrete Fourier Transform. Proceedings of the National Academy of Sciences, 73, 1005-1006. https://doi.org/10.1073/pnas.73.4.1005
[5]	Ortega, A., Frossard, P., Kovačević, J., Moura, J.M.F. and Vandergheynst, P. (2018) Graph Signal Processing: Overview, Challenges, and Applications. Proceedings of the IEEE, 106, 808-828. https://doi.org/10.1109/jproc.2018.2820126
[6]	Haemers, W.H. (1995) Interlacing Eigenvalues and Graphs. Linear Algebra and Its Applications, 226, 593-616. https://doi.org/10.1016/0024-3795(95)00199-2
[7]	Lund, D., Drapeau, J. and Webb, B. (2021) Fourier Decompositions of Graphs with Symmetries and Equitable Partiti. Linear Algebra and Its Applications, 627, 199-226. https://doi.org/10.1016/j.laa.2021.05.019

为你推荐

友情链接