# Eigenvalues of directed graph with one outward edge for each vertex

I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one entry equal to 1, and the rest are 0. Im not sure if these graphs have a name, but they could be called a deterministic Markov chain.

I think the eigenvalues of the adjacency matrix will always come from this set: 1,0 and roots of unity. Is this true, and if so, what ensures this?

• Rather than a deterministic Markov chain, I would say this is the digraph of a function $V\to V$. Commented Nov 9, 2022 at 1:40
• See this question: math.stackexchange.com/questions/3623784/… Commented Nov 9, 2022 at 6:01
• I think you’re describing a permutation matrix. Commented Nov 9, 2022 at 7:08
• @KrystalGuo One 1 per row, not necessarily per column. Commented Nov 9, 2022 at 7:33
• Yes, that other post is exactly what I wanted. Thank you! What should I do to this question then? Commented Nov 9, 2022 at 17:46

## 1 Answer

Here is an alternative (more combinatorial) proof to the one linked to in my comment.

Suppose that the digraph $$D$$ has a vertex of in-degree zero, which we may assume is vertex $$1$$. Then letting $$\varphi(D)$$ denote the characteristic polynomial of the adjacency matrix $$A(D)$$, we have

$$\varphi(D) = |xI - A(D)| = \left|\begin{array}{cc}x&*\\ 0&xI-A(D\backslash 1)\\\end{array} \right| = x \varphi(D\backslash 1).$$

Now $$A(D\backslash 1)$$ is a matrix with exactly one 1 per row and hence we can repeat the process.

In other words, the eigenvalues of $$D$$ are the eigenvalues of $$D \backslash 1$$ plus an extra $$0$$.

If there are no vertices of in-degree 0, then the graph is a disjoint union of directed cycles, and hence the matrix is a permutation matrix, and since $$A^k = I$$ for some $$k$$, all of its eigenvalues are roots of unity.

• Thank you! This is much more straightforward than the explanation in the link. Commented Nov 12, 2022 at 15:18