MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Answer

3 added 130 characters in body

Suppose you are interested in random walks on an extremely structured graph such as a hypercube graph or a cycle graph. If your graph happens to be the Cayley graph of an abelian group $G$, as in both of the above examples, then it is easy to describe the behavior of random walks on it because the eigenvectors of the adjacency matrix are precisely the characters of $G$ and the eigenvalues depend in a simple way on the characters; in other words, you should learn about the discrete Fourier transform.

Edit: Some elaboration. Let $G$ be a finite abelian group with $|G| = n$. A character of $G$ is a homomorphism $G \to \mathbb{C}$, and it is a basic fact of character theory that the characters form a basis of the space of functions $G \to \mathbb{C}$; this is the discrete Fourier transform. Now let $\mathbf{A}(G)$ be the adjacency matrix of a Cayley graph of $G$ using generators ${ s_1, ... s_k }$. The group $G$ acts on the space of functions $G \to \mathbb{C}$ by sending a function $f : G \to \mathbb{C}$ to $f(gx)$. Call this representation $\rho$; then (and this is the important connnecting observation) one may regard $\mathbf{A}(G)$ as the linear operator $\displaystyle \sum_{i=1}^{k} \rho(s_i)$.

Proposition: Let $\chi_j : G \to \mathbb{C}$ be a character of $G$. Then $\chi_j$ is an eigenvector of $\mathbf{A}(G)$ with eigenvalue $\displaystyle \sum_{i=1}^{k} \chi_j(s_i)$.chi_j(s_i)$, and these are all the eigenvectors. Proof. Just observe that$\rho(s_i) \chi_j(g) = \chi_j(s_i g) = \chi_j(s_i) \chi_j(g)$. The fact that these exhaust the set of eigenvectors follows from the basic fact cited above. For example, the cycle graph$C_n$is the Cayley graph of the cyclic group$\mathbb{Z}/n\mathbb{Z}$with generators${ 1, -1 }$, so its eigenvectors are just the rows of the discrete Fourier transform matrix on$\mathbb{Z}/n\mathbb{Z}$and its eigenvalues are$e^{ \frac{2\pi i k}{n} } + e^{- \frac{2\pi ik}{n} } = 2 \cos \frac{2\pi k}{n}$. (Note that I have implicitly identified the space of functions$G \to \mathbb{C}$with the free vector space on the elements of$G$in the usual way.) 2 added 1355 characters in body; added 152 characters in body Edit: Some elaboration. Let$G$be a finite abelian group with$|G| = n$. A character of$G$is a homomorphism$G \to \mathbb{C}$, and it is a basic fact of character theory that the characters form a basis of the space of functions$G \to \mathbb{C}$; this is the discrete Fourier transform. Now let$\mathbf{A}(G)$be the adjacency matrix of a Cayley graph of$G$using generators${ s_1, ... s_k }$. The group$G$acts on the space of functions$G \to \mathbb{C}$by sending a function$f : G \to \mathbb{C}$to$f(gx)$. Call this representation$\rho$; then (and this is the important connnecting observation) one may regard$\mathbf{A}(G)$as the linear operator$\displaystyle \sum_{i=1}^{k} \rho(s_i)$. Proposition: Let$\chi_j : G \to \mathbb{C}$be a character of$G$. Then$\chi_j$is an eigenvector of$\mathbf{A}(G)$with eigenvalue$\displaystyle \sum_{i=1}^{k} \chi_j(s_i)$. Proof. Just observe that$\rho(s_i) \chi_j(g) = \chi_j(s_i g) = \chi_j(s_i) \chi_j(g)$. For example, the cycle graph$C_n$is the Cayley graph of the cyclic group$\mathbb{Z}/n\mathbb{Z}$with generators${ 1, -1 }$, so its eigenvectors are just the rows of the discrete Fourier transform matrix on$\mathbb{Z}/n\mathbb{Z}$and its eigenvalues are$e^{ \frac{2\pi i k}{n} } + e^{- \frac{2\pi ik}{n} } = 2 \cos \frac{2\pi k}{n}$. (Note that I have implicitly identified the space of functions$G \to \mathbb{C}$with the free vector space on the elements of$G\$ in the usual way.)

Post Made Community Wiki by Anton Geraschenko♦♦
1