Periodic Vertices

Spectrum

The behaviour of a quantum walk is closedly related to the spectrum of the graph. Let \[ H = \sum_r \theta_r E_r \] be the spectral decomposition of $H$. The eigenvalue support of a vertex $v$, denoted $S(v)$, is the set of eigenvalues $\theta_r$ such that $E_re_v \ne 0$, or equivalently, \[ S(v) = \{\theta_r: (E_r)_{vv}\ne 0\}. \] The following theorem in [1] characterizes the periodicity of a vertex in terms of its eigenvalue support.

(Characterizing periodicity): Suppose $X$ is a weighted graph with at least two vertices. Then $X$ is periodic at the vertex $v$ if and only if either:
  1. The eigenvalues in $S(v)$ are integers.
  2. There is a square-free integer $\Delta$, such that the eigenvalues in $S(v)$ are quadratic integers in $\rats\left(\sqrt{\Delta}\right)$, and the difference of any two eigenvalues in $S(v)$ is an integer multiple of $\sqrt{\Delta}$.

Thus it suffices to compute the eigenvalue support of $v$. Consider two characteristic polynomials \[ \phi(t) = \det(tI-H) \] and \[ \phi_v(t) = \det(tI-H(v:v)) \] where $H(v:v)$ is obtained from $H$ by removing the $v$-th row and the $v$-th column. Using the spectral decomposition of $H$, the ratio of $\phi(t)$ to $\phi_v(t)$ can be neatly expressed as \[ \frac{\phi_v(t)}{\phi(t)} = \sum_r \frac{1}{t-\theta_r} (E_r)_{vv}. \] If we let \[ g_v(t) = \gcd(\phi(t), \phi_v(t)) \] and \[ \psi_v(t) = \frac{\phi(t)}{g_v(t)} \] then the zeros of $\psi_v(t)$ are precisely the eigenvalue support of $v$.

Now suppose we have found a periodic vertex $v$. How do we determine its minimum period $\tau$? Let \[ U(\tau)_{vv}=\gamma \] for some phase factor $\gamma$. Spectral decomposition tells us that \[ e^{i\tau\theta_r} (E_r)_{vv} = \gamma (E_r)_{vv}. \] where $\theta_r$ is any eigenvalue in the eigenvalue support of $v$. For such an eigenvalue, the entry $(E_r)_{vv}$ is never zero, so it follows that \[ e^{i\tau\theta_r} = \gamma \] for all $\theta_r \in S(v)$. If the graph is connected, then $\left| S(v) \right|\ge 2$. Fixing any eigenvalue $\theta_0$ in $S(v)$, we see that $\theta_r-\theta_0$ divides $2\pi$ for the remaining eigenvalues $\theta_r$ in $S(v)$.

(Determining the period): Let $v$ be a periodic vertex of a connected graph with at least two vertices. Let \[ g = \gcd\{\theta_r-\theta_0: \theta_r\in S(v)\}. \] Then the minimum period of $v$ is $\tau = 2\pi/g$.

Bibliography

[1] Chris Godsil, Periodic Graphs , arXiv:0806.2074 (2008).
Home