Eigenvalues of the Laplacian of the directed De Bruijn graph

Question

We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ if and only if $\sigma_i=\tau_{i+1}$ for every $i=1,\dots,n-1$.

We would like to calculate the spectrum of the Laplacian matrix of $DB(n,k)$. Note that since $DB(n,k)$ is $k$-regular, then $\lambda \in Spec(L_{DB(n,k)})$ if and only if $k-\lambda \in Spec(A_{DB(n,k)})$, so we can calculate the eigenvalues of the Laplacian matrix from the eigenvalues of the Adjacency matrix.

We found the following article on the subject, but it only calculates the spectrum of the underlining undirected graph of the De Bruijn graph:

https://core.ac.uk/download/pdf/82810454.pdf

Thanks!

Answer 1

The computation for $k=2$ appears (among other places) on pp. 158--159 of my book Algebraic Combinatorics, second edition. The computation for arbitrary $k$ is completely analogous. Dima Pasechnik is correct that there is one eigenvalue equal to 0, and all the others are equal to $k$.

Answer 2

I believe that for $p$ prime $DB(m,p)$ has one 0 eigenvalue (this is easy to check), and the other eigenvalues are all equal to $p$. This is something that we observed while working on https://arxiv.org/abs/1405.0113, but didn't try to prove (should not be too hard I guess, using a decription of $DB(m,p)$ as the line graph of $DB(m-1,p)$, and then induction).

Answer 3

A bit late but here's a solution.

(1) If $\Gamma$ is any directed graph with $n$ vertices where for every $v,w$ in the vertex set there is a unique $v \leadsto w$ path of length $h$ for some fixed $h$, then $n = k^h$ for some $k$ and $\Gamma$ is $k$-regular (in- and out-degree).

This is seen because if $A$ is the adjacency matrix of $\Gamma$ then $A^h = J$, where $J$ is the all-ones matrix, and so $A$ has algebraic spectrum $\sqrt[h]{n}$ with mult. 1 and $0$ with mult. $n-1$.

Further, $\mathbf 1$, the all-ones vector, is a left and right eigenvector of $A$. Then we use this to compute $$ (A\mathbf 1)_v = \#~\text{edges leaving node $v$} = \sqrt[h]{n} $$ and similarly using $\mathbf 1$ as a left eigenvector we compute that the number of edges entering $v$ is $\sqrt[h]{n}$. This applies for every $v$, so that setting $k = \sqrt[h]{n}$ we get the desired conclusion.

(2) With the notation above, $DB(n,k)$ clearly satisfies this property with $h = n$. Since there are $k^n$ vertices of $DB(n,k)$, we see that the spectrum is $k$ with multiplicity 1 and $0$ with multiplicity $k^n - 1$.

Now since $DB(n,k)$ is $k$-regular, the Laplace matrix $L = kI - A$ and so has eigenvalue $0$ with mult. 1 and $k$ with mult. $k^n - 1$.