Fourier decompositions of graphs with symmetries and equitable partitions
| Autor: | Darren Lund, Benjamin Webb, Joseph Drapeau |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Numerical Analysis
Algebra and Number Theory Similarity (geometry) 010102 general mathematics 010103 numerical & computational mathematics Directed graph 01 natural sciences Discrete Fourier transform Combinatorics Matrix (mathematics) symbols.namesake Fourier transform Computer Science::Discrete Mathematics symbols ComputingMilieux_COMPUTERSANDSOCIETY Discrete Mathematics and Combinatorics Partition (number theory) Geometry and Topology Adjacency matrix 0101 mathematics Eigenvalues and eigenvectors MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Linear Algebra and its Applications. 627:199-226 |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/j.laa.2021.05.019 |
| Popis: | 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) are the same as the eigenvalues of the original untransformed matrix (graph). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect