We show that equitable partitions, which are generalizations of graph symmetries, and Fourier transforms are fundamentally related. For a partition of a graph's vertices we define a Fourier similarity transform of the graph's adjacency matrix built from the matrices used to carryout discrete Fourier transformations. We show that the matrix (graph) decomposes into a number of smaller matrices (graphs) under this transformation if and only if the partition is an equitable partition. To extend this result to directed graphs we define two new types of equitable partitions, equitable receiving and equitable transmitting partitions, and show that if a partition of a directed graph is both, then the graph's adjacency matrix will similarly decomposes under this transformation. Since the transformation we use is a similarity transform the collective eigenvalues of the resulting matrices (graphs) is the same as the eigenvalues of the original untransformed matrix (graph).
College and Department
BYU ScholarsArchive Citation
Lund, Darren Scott, "Fourier Decompositions of Graphs with Symmetries and Equitable Partitions" (2021). Theses and Dissertations. 8925.
Discrete Fourier Transform, graph, network, Fourier Similarity Transform, equitable partition, graph similarity