I'm currently reading this article (1) and I want to verify equation (4) and (5). I will reproduce the claim here.
Let $P$ be a transition matrix and $\phi_0$ be the stationary distribution of $P$. The left and right eigenvectors are
$$\phi_j^T P = \lambda_j \phi_j^T \quad \text{and} \quad P\psi_j = \lambda_j \psi_j. $$
The authors claim that the left and right eigenvectors are related in the following way (eq 4)
$$ \psi_l(x) = \frac{\phi_l(x)}{\phi_0(x)} \tag{1} $$
and that we can normalize the left eigenvectors of $P$ with respect to $1/\phi_0$ to get (eq 5)
$$ ||\phi_l ||_{1/\phi_0}^2 = \sum_x \frac{\phi_l^2(x)}{\phi_0(x)} = 1. $$
However, I was not able to prove these claims. I tested the second equation empirically and it does not seem to hold, which makes me think the eigenvectors are already implicitly normalized in some way.
Any help deriving these two expressions are greatly appreciated.
(1) In case the link dies, article name is: Diffusion Maps and Coarse-Graining: A Unified Framework for Dimensionality Reduction, Graph Partitioning and Data Set Parameterization by Lafon and Lee.
EDIT: I have studied this problem further and came up with the following.
The problem is about a random walk on a graph. Let $A$ be the adjacency matrix of that graph and $D$ be the diagonal degree matrix. Then $P = D^{-1}A$. We note that $P$ is not symmetric but we can write
$$ P = D^{-1}A = D^{-1/2} \left( D^{-1/2} A D^{-1/2} \right) D^{1/2} \tag{2} $$
and the inner matrix $S = D^{-1/2} A D^{-1/2}$ is symmetric. Suppose
$$ Sv_j = \lambda_j v_j. $$
That is, $(\lambda_j, v_j)$ is an eigenpair for $S$ for $j = 1,...,n$. Meaning that the eigendecomposition is, $S = V \Lambda V^T$. Putting this into (2) gives us
$$ P = D^{-1/2} V \Lambda V^T D^{1/2} $$
Now let $\Phi = D^{-1/2} V$ and $\Psi = D^{1/2} V $ then clearly
$$ P = \Phi \Lambda \Psi. $$
This is a bi-orthogonal system. We get $\phi_j = D^{-1/2}v_j$ and $\psi = D^{1/2} v_j$. Since this is a random walk on a graph we know that the stationary distribution is
$$ \phi_0 = \frac{D}{\text{vol}(D)} $$ i.e., the degree of a node divided by the total volume of the graph.
Combining this with the expression for $\phi_j$ and $\psi_j$ we almost get (1). We are only missing the $\text{vol}(D)$ part.
Where does this come from?
$\def\eqdef{\stackrel{\text{def}}{=}}$ According to the definitions given on p.$4$ of the paper you cite, $\ P\ $ has the form $$ P=D^{-1}W $$ where $$ D=\text{diag}\big(d(x_1),d(x_2),\dots,d(x_n)\big) $$ and $\ W\ $ is symmetric. Therefore, if $\ \psi_j\ $ is a right eigenvector of $\ P\ $ corresponding to eigenvalue $\ \lambda_j\ $, then \begin{align} \lambda_j\psi_j&=P\psi_j\\ &=D^{-1}WD^{-1}D\psi_j \end{align} Therefore $$ \lambda_jD\psi_j=WD^{-1}D\psi_j\ , $$ and transposing both sides of this equation gives \begin{align} \lambda_j\psi_j^TD&=\psi_j^TDD^{-1}W\\ &=\psi_j^TDP\ . \end{align} Therefore $\ \psi_j^TD\ $ is a right eigenvector of $\ P\ $ corresponding to the same eigenvalue. The paper takes $\ \psi_0\ $ to be the right eigenvector all of whose entries are $\ 1\ $ (corresponding to the eigenvalue $\ 1\ $). It also appears to be taking $\ \phi_j\eqdef D\psi_j\ $, which it can certainly do, but is being a little sloppy in failing to say so explicitly. With that definition, you have $\ \phi_0(x)=$$\,d(x)\ $ and $\ \psi_j(x)=\frac{\phi_j(x)}{d(x)}=\frac{\phi_j(x)}{\phi_0(x)}\ $.
Normalisation
For the "normalised" eigenvectors, you can take \begin{align} \bar{\phi}_0(x)&\eqdef\frac{d(x)}{\sum_\limits{x}d(x)}\\ \bar{\phi}_j(x)&\eqdef\frac{\phi_j(x)}{\sqrt{\sum_\limits{x}\frac{\phi_j(x)^2}{\bar{\phi}_0(x)}}}\ \ \ \text{ for }\ \ j>0 \\ \bar{\psi}_j(x)&=\frac{\bar{\phi}_j(x)}{\bar{\phi}_0(x)}\\ &=\frac{\psi_j(x)\sum_\limits{x}d(x)}{\sqrt{\sum_\limits{x}\frac{\phi_j(x)^2}{\bar{\phi}_0(x)}}}\ . \end{align} Then $\ \bar{\psi}_j\ $ and $\ \bar{\phi}_j\ $ are still eigenvectors of $\ P\ $ corresponding to the eigenvalue $\ \lambda_j\ $, being non-zero scalar multiples of the original, and satisfy the equations \begin{align} 1&=\sum_x\frac{\bar{\phi}_j(x)^2}{\bar{\phi}_0(x)}\\ &=\sum_x\bar{\psi}_j(x)^2\bar{\phi_0}(x) \end{align}