I have the following $2m \times 2m$ matrix
$$\tilde{P}((u,v), (x,y)) = \begin{cases} \frac{1}{d_v -1}, & \text{if } v=x ~\text{and}~ y\neq u \\ 0 & \text{otherwise } \end{cases}$$
This definition makes $\tilde{P}$ double stochastic which is shown in [Lemma 1, 1]:
$G=(V,E)$ denote a graph with vertex set $V$ ad edge set $E$ where $n=|V|$ and $m=|E|$. In addition, $D$ is a $n \times n$ diagonal matrix with rows and columns indexed by $V$ with $D(v,v)=d_v$, where $d_v$ denotes the degree of vertex $v$. I found hard to understand why the rows sum to one. Possibly I do not understand how I can take the sum over a row in $\tilde{P}$. I have not worked with this type of matrices before. The same question holds for the sum over the columns. I do not understand how the sum with the indexes $x \sim u$ and $x\neq v$ is unfolded. Could you please someone provide some more details? Any help is highly appreciated.
[1] Mark Kempton, Non-backtracking random walks and a weighted Ihara’s theorem
Taking the sum over a row means to fix the first edge $(u,v)$ and sum over all the possible edges $(x,y)$. The sum over a given row is $1$ because essentially $\tilde P$ was constructed as a probability matrix: given a directed edge $(u,v)$, there will be another $d_v-1$ directed edges going out from the vertex $v$ (excluding the directed edge $(v,u)$), so if $(x,y)$ is one of these edges (that is, $x=v$ and $y\neq u$), the probability is non-zero, otherwise it’s set to be zero. Taking this non-zero probability as $1/(d_v-1)$ ensures that the sum over all the non-zero probabilities is exactly $1$.
An analogous reasoning works for the sum over the columns, where you fix $(x,y)$ instead and sum over all the possible edges $(u,v)$.
Let me emphasize that in all of this, the pairs $(u,v)$ and $(x,y)$ are not arbitrary couples of vertices of the graph, but they are directed edges, so you assume that $u$ and $v$ are linked by an arch of the graph.