Source-linked AI summary
Periodic Graphs
Chris Godsil
TL;DR
The paper extends earlier work by examining the relationship between graph periodicity and perfect state transfer. The construction yields a time t at which H(t) is a permutation matrix, giving perfect state transfer. Perfect state transfer at time τ implies periodicity at both vertices with period 2τ, and in a coherent algebra H(τ) is a scalar multiple of a fixed-point-free permutation matrix of order two.
Problem
The paper extends earlier work by examining the relationship between graph periodicity and perfect state transfer.
Source: §1 · p. 2Method
The construction yields a time t at which H(t) is a permutation matrix, giving perfect state transfer.
Source: §7 · p. 17Results
Takeaways & Limitations
Perfect state transfer models quantum-particle state transfer without information loss, and the paper exhibits a new infinite family of graphs with transfer.
Source: §7 · p. 17For walk-regular graphs, the authors give no reason to expect that perfect state transfer forces H(τ) to be a multiple of a permutation matrix, and they have no example.
Source: §5 · p. 12
Abstract
from arXiv · showhide
Let $X$ be a graph on $n$ vertices with with adjacency matrix $A$ and let $H(t)$ denote the matrix-valued function $\exp(iAt)$. If $u$ and $v$ are distinct vertices in $X$, we say perfect state transfer}from $u$ to $v$ occurs if there is a time $\tau$ such that $|H(\tau)_{u,v}|=1$. If $u\in V(X)$ and there is a time $\sg$ such that $|H(\sg)_{u,u}|=1$, we say $X$ is periodic at $u$ with period $\sg$. We show that if perfect state transfer from $u$ to $v$ occurs at time $\tau$, then $X$ is periodic at both $u$ and $v$ with period $2\tau$. We extend previous work by showing that a regular graph with at least four distinct eigenvalues is periodic with respect to some vertex if and only if its eigenvalues are integers. We show that, for a class of graphs $X$ including all vertex-transitive graphs, if perfect state transfer occurs at time $\tau$, then $H(\tau)$ is a scalar multiple of a permutation matrix of order two with no fixed points. Using certain Hadamard matrices, we construct a new infinite family of graphs on which perfect state transfer occurs.
1 Introduction
The introduction defines vertex-level and graph-level periodicity, then relates these notions to perfect state transfer. It previews spectral and structural results, including conditions that make vertexwise periodicity imply graph periodicity.
1 Introduction
- Graph periodicity means that H(τ) is diagonal, while periodicity relative to a vertex means its diagonal entry has modulus one at some time.The introduction also defines periodicity relative to a vector by requiring H(τ)z to be a unit-modulus scalar multiple of z.Source: §1 · p. 2
- If every basis vector is periodic, the graph is periodic with period dividing the product of their periods.This connects periodicity relative to individual vectors with periodicity of the whole graph.Source: §1 · p. 2
- Perfect state transfer models moving a quantum-particle state between vertices without information loss.The cited earlier work establishes transfer for certain paths and vertices in Cartesian powers of those paths.Source: §1 · p. 2
- The paper relates periodicity to perfect state transfer and previews results on regular-graph eigenvalues, permutation matrices, and an infinite graph family.For a broad class of regular graphs including vertex-transitive and distance-regular graphs, transfer implies a scalar multiple of a fixed-point-free involution matrix; the paper also presents antipodal distance-regular examples.Source: §1 · p. 2
2 Eigenvalues
Perfect state transfer entails periodicity at both participating vertices, and the section develops spectral tools for analyzing periodicity through eigenvalue support. It also derives a ratio condition for periodic circulant graphs.
2 Eigenvalues
- Perfect state transfer from u to v at time τ makes the graph periodic at both vertices with period 2τ.This establishes a direct link between transfer and vertex periodicity.Source: §2 · p. 3
- The spectral decomposition of a symmetric matrix is the paper's main tool for analyzing its functions and eigenspaces.For a graph adjacency matrix, the projections onto eigenspaces determine which eigenvalues belong to a vector's support.Source: §2 · p. 3
- The eigenvalue support of a vector consists of eigenvalues whose eigenspace projections of that vector are nonzero.The dual degree is one less than the size of this support.Source: §2 · p. 3
- If a vertex is periodic and two integer eigenvalues lie in its support, then every eigenvalue in that support is an integer.Source: §2 · p. 4
- Periodic circulant graphs satisfy the ratio condition because vertex transitivity makes each vertex support the full spectrum.The passage derives this condition from the paper's results.Source: §2 · p. 5
3 Periodicity
The section characterizes graph periodicity by rational ratios among nonzero eigenvalues. It also gives consequences for eigenvalue integrality and bipartiteness.
3 Periodicity
- Integer eigenvalues are a sufficient condition for graph periodicity.The section notes that integrality is sufficient but not necessary in general.Source: §3 · p. 6
- A graph is periodic if and only if the ratio of any two nonzero eigenvalues is rational.Source: §3 · p. 6
- When the ratios of nonzero eigenvalues are rational, the square of an eigenvalue is an integer.Source: §3 · p. 7
- If the eigenvalues satisfy the corollary's second alternative, the graph is bipartite.The supplied passage does not specify that alternative's full condition.Source: §3 · p. 7
4 Coherent Algebras
Coherent algebras provide a framework covering vertex-transitive and distance-regular graphs. Within this framework, perfect state transfer forces a fixed-point-free involution structure and an even number of vertices.
4 Coherent Algebras
- A coherent algebra contains the all-ones matrix and is closed under Schur multiplication, transpose, and complex conjugation; its 01-basis defines a coherent configuration.A graph in such an algebra has adjacency matrix equal to a sum of distinct basis matrices.Source: §4 · p. 8
- Homogeneous coherent algebras have constant diagonal and regular basis matrices, and include frameworks for vertex-transitive and distance-regular graphs.The commutant of a transitive permutation group is homogeneous; distance-regular graphs also have a homogeneous coherent algebra.Source: §4 · p. 8
- Perfect state transfer in a graph belonging to a coherent algebra makes H(τ) a scalar multiple of a fixed-point-free order-two permutation matrix central in the automorphism group.The proof uses that H(t) lies in the algebra and is symmetric, so its permutation matrix is symmetric and commutes with graph automorphisms.Source: §4 · p. 9
- Thus the graph has an even number of vertices, and its coherent algebra is imprimitive; this applies to vertex-transitive and distance-regular graphs.The corollary is stated for coherent-algebra graphs, including both classes.Source: §4 · p. 9
5 Walk-Regular Graphs
For walk-regular graphs, perfect state transfer constrains the spectrum of the transition matrix, while the multiplicity enumerator supplies a unit-circle test. A walk-regular example that is not vertex-transitive does not exhibit perfect state transfer.
5 Walk-Regular Graphs
- Walk-regularity is equivalent to constant diagonal entries in every nonnegative integer power of the adjacency matrix; connected regular graphs with at most four distinct eigenvalues are walk-regular.Graphs in coherent configurations are also walk-regular.Source: §5 · p. 10
- Perfect state transfer on a walk-regular graph makes H(2τ) a scalar matrix and gives H(τ) eigenvalues ±γ with equal multiplicities, so the graph has even order.The diagonal entries of H(τ) are zero, making its trace zero.Source: §5 · p. 11
- For a walk-regular graph with integer eigenvalues, perfect state transfer requires the multiplicity enumerator µ(z) to have an eigenvalue on the unit circle.Here µ(z) is defined using the graph's eigenvalue multiplicities.Source: §5 · p. 11
- The walk-regular graph in Figure 1 is not vertex-transitive, does not lie in a homogeneous coherent algebra, and exhibits no perfect state transfer.The stated reason is that its multiplicity-enumerator polynomial has no roots on the unit circle.Source: §5 · pp. 10–11
- The authors do not expect perfect state transfer on a walk-regular graph generally to force a scalar-multiple permutation matrix, though they have no example.This is presented as a qualification rather than a demonstrated counterexample.Source: §5 · p. 12
6 Hypercubes
The section relates perfect state transfer in distance-regular graphs to antipodal structure and illustrates the result with the n-cube. The cube has perfect state transfer at π/2 and is periodic with period π.
6 Hypercubes
- When the diameter-distance graph Xd is disconnected, its components are equal-sized complete graphs called antipodal classes; the n-cube's classes are pairs at distance n.Vertices in different pairs are at distance less than n.Source: §6 · p. 12
- Perfect state transfer in a distance-regular graph forces antipodal classes of size two and makes H(τ) equal to the diameter-distance adjacency matrix Xd.The result specializes the preceding coherent-algebra corollary.Source: §6 · p. 12
- The n-cube's distance graphs form a commutative coherent algebra, with their adjacency matrices as a basis and eigenspace projections as orthogonal idempotents.Adjacency matrices act on these idempotents by scheme eigenvalues, while the algebra basis also gives dual eigenvalues.Source: §6 · p. 13
- At time π/2, perfect state transfer occurs on the n-cube, which is periodic with period π.The n-cube is presented as a distance-regular graph and an early example of perfect state transfer.Source: §6 · pp. 12, 14
7 Hadamard Matrices
Special Hadamard matrices yield antipodal distance-regular graphs of diameter three with perfect state transfer. The section develops the graph and matrix conditions underlying this construction and notes that suitable inputs exist at infinitely many orders.
7 Hadamard Matrices
- Hadamard inputs exist at every power-of-four order, so the construction yields an infinite family of graphs with perfect state transfer.Source: §7 · pp. 14, 17
- The construction produces an antipodal distance-regular graph on 2n vertices, with valency n−1 and diameter three.Source: §7 · pp. 14–16
- The Hadamard inputs are symmetric, regular, and constant-diagonal; their order is a square and their row sum is ±√n.Source: §7 · pp. 14–15
- Kronecker products preserve the required Hadamard properties, and applying P to H⊗H^T also yields a regular symmetric Hadamard matrix with constant diagonal.Source: §7 · p. 15
- The graph's eigenvalues include n−1 and −1, together with the eigenvalues of H−I.Source: §7 · p. 16
8 Questions and Comments
The section identifies open questions about which vertex pairs admit perfect state transfer and how sparse a graph can be while transferring across a given distance. It also points to existing transfer examples in Cayley graphs, including cubes.
8 Questions and Comments
- Characterizing the vertex pairs where perfect state transfer occurs remains an open problem.Source: §8 · p. 17
- Examples with perfect state transfer but nonperiodic underlying graphs had already answered a question raised in an earlier version of the paper.Source: §8 · p. 17
- Certain Cayley graphs for Z_2^d, including n-cubes, exhibit perfect state transfer; a cited result gives a transfer condition in terms of the connection-set sum σ.Source: §8 · p. 17
- A useful estimate for the minimum number of edges needed for transfer between vertices at distance d remains an open question.Source: §8 · p. 17