Skip to main content
deleted 5 characters in body
Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

$\def\CC{\mathbb{C}}$The specturm is integral.

The following trick is very useful in computing spectra of highly symmetric graphs. Let $G$ be a finite graph, let $\Gamma$ be a group of symmetries of $G$, and let $V$ be the set of vertices of $G$. Let $A$ be the adjacency matrix, so $A : \CC^V \to \CC^V$. Then $A$ commutes with the action of $\Gamma$ on $\CC^V$. Therefore, if $\CC^V = \bigoplus W_i$ is the decomposition of $\CC^V$ into irreducible componentsisotypic summands, then the spectrum of $A$ is the disjoint union of the spectra of $A$ restricted to the $W_i$.

In our case, we'll take $\Gamma = (\mathbb{Z}/k)^n$. For $(g_1, \ldots, g_n) \in \Gamma$ and $(x_1, \ldots, x_n)$ in $G_{n,k}$, we have $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = 0$ if $x_j=0$ and $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = g_j+x_j \bmod k$ if $x_j \neq 0$.

Let $\chi: (g_1, \ldots, g_n) \mapsto \exp(\frac{2 \pi i}{k} \sum g_i c_i)$ be a character of $\Gamma$, where the $c_i$ in $\mathbb{Z}/k$. We will compute the action of $A$ on the corresponding eigenspace of $\CC^V$.

Reorder the coordinates so that $c_1=c_2=\cdots=c_j=0$ and the other $c_i$ are not $0$. The corresponding eigenspace has dimension $j$: For $1 \leq r \leq j$, there is a one dimensional space of functions in $\CC^V$ which transform by this character and have the $0$ entry in position $r$.

I get that $A$ acts on this $j$ dimensional eigenspace by the matrix whose diagonal entries are $(j-1) (k-1) + (n-j) (-1)= jk -k-n+1$ and whose off diagonal entries are $k$. This matrix has one eigenvalue of $2jk - 2k+n+1$ and all the others are $jk-2k+n+1$. In particular, they are integers.

$\def\CC{\mathbb{C}}$The specturm is integral.

The following trick is very useful in computing spectra of highly symmetric graphs. Let $G$ be a finite graph, let $\Gamma$ be a group of symmetries of $G$, and let $V$ be the set of vertices of $G$. Let $A$ be the adjacency matrix, so $A : \CC^V \to \CC^V$. Then $A$ commutes with the action of $\Gamma$ on $\CC^V$. Therefore, if $\CC^V = \bigoplus W_i$ is the decomposition of $\CC^V$ into irreducible components, then the spectrum of $A$ is the disjoint union of the spectra of $A$ restricted to the $W_i$.

In our case, we'll take $\Gamma = (\mathbb{Z}/k)^n$. For $(g_1, \ldots, g_n) \in \Gamma$ and $(x_1, \ldots, x_n)$ in $G_{n,k}$, we have $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = 0$ if $x_j=0$ and $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = g_j+x_j \bmod k$ if $x_j \neq 0$.

Let $\chi: (g_1, \ldots, g_n) \mapsto \exp(\frac{2 \pi i}{k} \sum g_i c_i)$ be a character of $\Gamma$, where the $c_i$ in $\mathbb{Z}/k$. We will compute the action of $A$ on the corresponding eigenspace of $\CC^V$.

Reorder the coordinates so that $c_1=c_2=\cdots=c_j=0$ and the other $c_i$ are not $0$. The corresponding eigenspace has dimension $j$: For $1 \leq r \leq j$, there is a one dimensional space of functions in $\CC^V$ which transform by this character and have the $0$ entry in position $r$.

I get that $A$ acts on this $j$ dimensional eigenspace by the matrix whose diagonal entries are $(j-1) (k-1) + (n-j) (-1)= jk -k-n+1$ and whose off diagonal entries are $k$. This matrix has one eigenvalue of $2jk - 2k+n+1$ and all the others are $jk-2k+n+1$. In particular, they are integers.

$\def\CC{\mathbb{C}}$The specturm is integral.

The following trick is very useful in computing spectra of highly symmetric graphs. Let $G$ be a finite graph, let $\Gamma$ be a group of symmetries of $G$, and let $V$ be the set of vertices of $G$. Let $A$ be the adjacency matrix, so $A : \CC^V \to \CC^V$. Then $A$ commutes with the action of $\Gamma$ on $\CC^V$. Therefore, if $\CC^V = \bigoplus W_i$ is the decomposition of $\CC^V$ into isotypic summands, then the spectrum of $A$ is the disjoint union of the spectra of $A$ restricted to the $W_i$.

In our case, we'll take $\Gamma = (\mathbb{Z}/k)^n$. For $(g_1, \ldots, g_n) \in \Gamma$ and $(x_1, \ldots, x_n)$ in $G_{n,k}$, we have $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = 0$ if $x_j=0$ and $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = g_j+x_j \bmod k$ if $x_j \neq 0$.

Let $\chi: (g_1, \ldots, g_n) \mapsto \exp(\frac{2 \pi i}{k} \sum g_i c_i)$ be a character of $\Gamma$, where the $c_i$ in $\mathbb{Z}/k$. We will compute the action of $A$ on the corresponding eigenspace of $\CC^V$.

Reorder the coordinates so that $c_1=c_2=\cdots=c_j=0$ and the other $c_i$ are not $0$. The corresponding eigenspace has dimension $j$: For $1 \leq r \leq j$, there is a one dimensional space of functions in $\CC^V$ which transform by this character and have the $0$ entry in position $r$.

I get that $A$ acts on this $j$ dimensional eigenspace by the matrix whose diagonal entries are $(j-1) (k-1) + (n-j) (-1)= jk -k-n+1$ and whose off diagonal entries are $k$. This matrix has one eigenvalue of $2jk - 2k+n+1$ and all the others are $jk-2k+n+1$. In particular, they are integers.

Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

$\def\CC{\mathbb{C}}$The specturm is integral.

The following trick is very useful in computing spectra of highly symmetric graphs. Let $G$ be a finite graph, let $\Gamma$ be a group of symmetries of $G$, and let $V$ be the set of vertices of $G$. Let $A$ be the adjacency matrix, so $A : \CC^V \to \CC^V$. Then $A$ commutes with the action of $\Gamma$ on $\CC^V$. Therefore, if $\CC^V = \bigoplus W_i$ is the decomposition of $\CC^V$ into irreducible components, then the spectrum of $A$ is the disjoint union of the spectra of $A$ restricted to the $W_i$.

In our case, we'll take $\Gamma = (\mathbb{Z}/k)^n$. For $(g_1, \ldots, g_n) \in \Gamma$ and $(x_1, \ldots, x_n)$ in $G_{n,k}$, we have $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = 0$ if $x_j=0$ and $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = g_j+x_j \bmod k$ if $x_j \neq 0$.

Let $\chi: (g_1, \ldots, g_n) \mapsto \exp(\frac{2 \pi i}{k} \sum g_i c_i)$ be a character of $\Gamma$, where the $c_i$ in $\mathbb{Z}/k$. We will compute the action of $A$ on the corresponding eigenspace of $\CC^V$.

Reorder the coordinates so that $c_1=c_2=\cdots=c_j=0$ and the other $c_i$ are not $0$. The corresponding eigenspace has dimension $j$: For $1 \leq r \leq j$, there is a one dimensional space of functions in $\CC^V$ which transform by this character and have the $0$ entry in position $r$.

I get that $A$ acts on this $j$ dimensional eigenspace by the matrix whose diagonal entries are $(j-1) (k-1) + (n-j) (-1)= jk -k-n+1$ and whose off diagonal entries are $k$. This matrix has one eigenvalue of $2jk - 2k+n+1$ and all the others are $jk-2k+n+1$. In particular, they are integers.