In a paper by Lovász (see reference at the end), there is the derivation of a spectral formula for the hitting time, which is the expected number of steps to get to a node t, starting at s, in a random walk on the graph.
It starts with the equation:
(1) $H(i,j) = 1 + \frac{1}{d(i)} \sum_{v \in \Gamma(i)} H(v,j) \ \ i \ne j$
I tried transforming this equation to a matrix equation and got to:
$H = J + MH$
(I'm not sure that what is above is correct)
After (1), the author just straight says that the matrix F is
(2) F = J + MH - H
And that F is diagonalizable.
That's where I got stuck. Where did this matrix F come from? How can he know that it's diagonalizable?
Note that:
$J$ is the matrix of all ones. ($J_{ij} = 1$ for any i,j)
$M$ is the matrix of transition probabilities. $M_{ij} = \frac{1}{degree(i)}$
$H_{ij}$ = the expected number of steps in a random walk from i to j.
Could someone help me with the steps of this proof? I couldn't also make much sense of what comes later.
Any help is appreciated, thanks.
Source of Lovász paper: https://cs.yale.edu/publications/techreports/tr1029.pdf
Equation (1) says that for $i \ne j$, $$H_{ij} = J_{ij} + \sum_v M_{iv} H_{vj}.$$ (I am writing $J_{ij}$ for the mysterious quantity otherwise known as the number $1$, and writing $M_{iv}$ in the sum both stands in for $\frac1{\deg(i)}$ and lets us extend the sum over all $v$.) In other words, for $i \ne j$, $H_{ij} = J_{ij} + (MH)_{ij}$.
However, we cannot write $H = J + MH$ from here, because of that pesky qualifier "for $i \ne j$". In other words, the matrices $H$ and $J+MH$ agree in their off-diagonal entries, but not in their diagonal entries.
This is exactly the same as saying that if we define a matrix $F$ to be $(J + MH) - H$, then $F$ is... not just diagonalizable, but diagonal. For $i \ne j$, we have $F_{ij} = J_{ij} + (MH)_{ij} - H_{ij}$, which is $0$ by equation (1). Therefore only the diagonal of $F$ can have nonzero entries.
In the next step, Lovász brings in the stationary distribution $\pi$, which is defined by the property $\pi^{\mathsf T}M = \pi^{\mathsf T}$. Therefore if we multiply the definition of $F$ on the left by $\pi^{\mathsf T}$, we get $$\pi^{\mathsf T}F = \pi^{\mathsf T}J + \pi^{\mathsf T}MH - \pi^{\mathsf T}H = \pi^{\mathsf T}J + \pi^{\mathsf T}H - \pi^{\mathsf T}H = \pi^{\mathsf T}J.$$ Now, comparing the two sides: on the left, $\pi^{\mathsf T}F$ is a row vector whose $i^{\text{th}}$ entry is $\pi_i F_{ii}$. On the right, $\pi^{\mathsf T}J$ is a row vector whose $i^{\text{th}}$ entry is $\pi_1 + \pi_2 + \dots + \pi_n = 1$. Therefore $\pi_i F_{ii} = 1$, which tells us what the diagonal entries of $F$ are: they are the reciprocals of the stationary probabilities $\pi$.