I'm new to spectral graph theory and I just read Laplacians and the Cheeger inequality for directed graphs. In this paper, the author proposed transition probability matrix using Perron-Frobenius Theorem.

To understand what they say, I tried to compute the Perron vector with simple example. But there's one thing I don't understand.

Suppose we have irreducible matrix $A$, $$A=\begin{pmatrix} 0 &1 &0 &0 \\ 0 &0 &1 &0 \\ 0&0&0&1 \\ 1&0&0&0 \end{pmatrix}$$ then, the probability transition matrix $P$ of $A$ is $$P=\begin{pmatrix} 0 &1 &0 &0 \\ 0 &0 &1 &0 \\ 0&0&0&1 \\ 1&0&0&0 \end{pmatrix}$$ (same as $A$ in this case).

Then the eigenvalues of $P$ is $\lambda=1, -1, i, -i$. The Perron-Frobenius Theorem states that an irreducible matrix with non-negative entries has a unique left eigenvector with all entries positive. In this case, let $\rho$denote the eigenvalue of all positive eigenvector of $P$.

Then $P$ has a unique left eigenvector $\phi$ and $\phi P = \rho P$. In this case, $\rho =1$ and $\phi = \begin{pmatrix} 1&1& 1&1\end{pmatrix}$.

I don't understand from this step. Then we have to normalize and choose $\phi_{norm}$ so that $\sum_v \phi_{norm}(v)=1$.
What does "choose" actually mean and how should I compute this? I thought I should simply normalize $\phi$ and which will be $\phi_{norm}= \begin{pmatrix} \frac{1}{2}&\frac{1}{2}&\frac{ 1}{2}&\frac{1}{2}\end{pmatrix}$. Is this incorrect? Can someone explain this?


Then we have to normalize and choose $\phi_{norm}$ so that $\sum_v \phi_{norm}(v)=1$.

That means you have to scale $\phi$ so that its entries sum to $1$. That is, you are normalising $\phi$ with respect to the $1$-norm (rather than the $2$-norm). So, $\phi_{\text{norm}}=\frac14(1,1,1,1)$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.