I'm considering random walk on undirected graph $G$. At every time step, walker moves to a random neighbour, with all neighbours being equally likely.
With adjacency matrix $A$ the random walk Markov matrix will be $M = D^{-1}A$, where $D$ is diagonal matrix with $D_{i,i}$ being sum of $i$-th row of matrix $A$. Under which conditions on $G$ matrix $M$ will be normal?