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?
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)$.