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?



Eigenvalues of directed graph with one outward edge for each vertex
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.


