I am given adjacency matrix $A$ of directed graph. $A(x,y)$ counts the number of edges from $x$ to $y$. I want to show that if $A$ has constant outdegree $d$:

(i) For any eigenvalue $\lambda$, we have $|\lambda| \le d$

(ii) If the directed graph is strongly connected, then the eigenvalue $d$ of $A$ has geometric multiplicity 1.

For (i) I have $x = \left( \begin{array}{cccc} 1 & 1 & \dots & 1 \end{array} \right)^T$. If we take: \begin{align*} Ax & = \left( \begin{array}{c} \sum \limits_{j=1}^n a_{1j} \cdot 1 \\ \vdots \\ \sum \limits_{j=1}^n a_{ij} \cdot 1 \\ \vdots \\ \sum \limits_{j=1}^n a_{nj} \cdot 1 \end{array} \right) = dx \end{align*} This is because each row has total sum $d$ (constant out degree but columns dont necessarily have this property). So then $d$ is an eigenvalue but how do I show all other EV have magnitude less than this?

EDIT: I have just solved (i). I just need some help with (ii)

(ii) To do this, do I want to show that kernel of first eigenspace is spanned by one vector? So $\dim(\ker(A-dI))=1$? Not sure how I would use fact that its strongly connected.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.