1
$\begingroup$

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.

$\endgroup$

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.