Adjacency graphs and eigenvalues

Question

I am currently reading this paper and this related paper (can also be found here), which explore the connection between Jordan normal forms and adjacency graphs.

Theorem 6 in the first paper reads

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function. Let $\Gamma_n$ be the directed graph associated with $f$ for the natural number $n$, and let $A_n$ be its adjacency matrix. Suppose $$ P = \{Z_1, \ldots, Z_r, C_1, \ldots, C_s\} $$ is a proper partition of $\Gamma_n$, where $Z_1, \ldots, Z_r$ are the cycles and $C_1, \ldots, C_s$ are the chains. Write the lengths of the cycles and chains as $$ \text{len } Z_j = \ell_j \quad (1 \leq j \leq r) \quad \text{and} \quad \text{len } C_j = m_j \quad (1 \leq j \leq s). $$ Let $\omega_j = \exp(2\pi i/\ell_j)$ be a primitive $\ell_j$th root of unity. The Jordan decomposition of $A_n$ contains the following $1 \times 1$ Jordan blocks for the eigenvalues which are roots of unity: $$ J_1(\omega_j^k) \quad \text{for } 1 \leq j \leq r \text{ and } 1 \leq k \leq \ell_j. $$ The Jordan decomposition contains the following blocks associated with the eigenvalue $0$: $$ J_{m_1}(0), J_{m_2}(0), \ldots, J_{m_s}(0). $$

They have also provided further examples to demonstrate how this works in practice. I am trying to better understand their findings with my own examples. But I did not get consistent results. Here is an example with matrix $A$ given by $$ A= \begin{pmatrix} -x & 0 & 1 \\ 0 & x & -1 \\ -1 & -1 & 0 \end{pmatrix} $$ with $x\in {\mathbb R}$ being a parameter. The graph associated with the matrix is with two 2-cycles and 2 self-loops. Possibible partitions that I can come up with are $\{2\}, \{3\}, \{1\}$, or $\{2,3\},\{1\}$ or $\{1,3\}, \{2\}$. From the first partitioning, the theorem implies that eigenvalues are $x,-x,0$, from the second partitioning, I get $-x$ and $\lambda (\lambda-x)=1$, and from the third partitioning I obtain $x$ and $\lambda (x+\lambda)+1=0$ with $\lambda$ being eigenvalues.

On the other hand, from linear algebra we know that A can be written in Jordan form (by similarity transformation) as $$ J(A)= \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2x & x^2 & 0 \end{pmatrix} $$ where $\det[A]=2x$ and $\operatorname{tr}[A^2]/2=x^2$.The adjacency graph for $J(A)$ then becomes

with a 3-cycle. The eigenvalues then reads $\lambda \propto e^{2i\pi j/3}\sqrt[3]{2x}$ with $j=0,1,2$. While this solution is correct, what I have obtained from applying the theorem to partitions of $A$ is incorrect. In most of such failing examples, the issue arises from the size of cycles when a self-loop and an n-cycle are present in $A$, whereas in the Jordan form $J(A)$, an $(n+1)$-cycle appears.

The theory merely talks about roots of unity, which I have generalized, but what further changes should I consider in the above theorem so that I can get the correct eigenvalues of A in my example just by looking at its adjacency graph?

Answer 1

The cited paper assumes all the entries of the matrix are from $\{0,1\}.$ Yet your example has as a matrix entry a real number $x$ and its negative. Is that difference significant?

Answer 2

I figured I should synthesize the short discussion in the comments into an answer.

The short answer is that the theorems in the linked papers do not apply to digraphs (like the OP's example) in which some vertices have out-degree $>1$. Moreover, generalizing their results does not seem at all straightforward. Let me elaborate.

---

Each partial function $f$ from $[n] = \{1,\dots,n\}$ to itself is naturally associated with a directed graph $\Gamma$ on $[n]$ (possibly with loops) having the edge $(i,j)$ if and only if $f(i)=j$. Let $A$ be the $n\times n$ adjacency matrix of $\Gamma$.

The main result of the first paper (Theorem 6, quoted in the question above) provides a way of describing the Jordan normal form of $A$ in terms of the graph-theoretic properties of $\Gamma$. The followup paper generalizes this by allowing non-zero complex edge weights on $\Gamma$ (data extraneous to $f$) whose values appear as the corresponding entries of $A$.

Because $f$ is a (partial) function, the out-degree of each vertex of $\Gamma$ is at most 1 and, equivalently, each column of $A$ has at most one non-zero entry. This fact is absolutely crucial to the authors' arguments. Many of their results are false or not even sensible for more general digraphs.

Perhaps the most important consequence of this basic fact is that the cycles of $\Gamma$ are disjoint. Digraphs which have overlapping cycles do not even admit what the authors call a proper partition and so Theorem 6 does not apply apply to such digraphs. The disjointness of cycles in $\Gamma$ suffuses the reasoning in both papers and most of the proofs do not even get off the ground in more general settings.

---

It's not clear to me what the analogue of Theorem 6 (or Theorem 2.3 in the followup) would even be for arbitrary (weighted) digraphs on $[n]$. That being said, I like the idea of analyzing the Jordan normal form of a zero-one (resp., complex-valued) matrix $A$ in terms of the associated digraph (resp., weighted digraph) $\Gamma$. Perhaps something like a basis for the cycle space of $\Gamma$ could play the role of the cycles in a proper partition more generally (although these would still not be disjoint) but it's not at all trivial to foresee how such a generalization might go.