Paseos de longitud uniforme en un gráfico bipartito

Question

Dado un paseo aleatorio sobre un simple $d$ -grafo bipartito regular $G$ . La matriz de adyacencia $A'$ de $G$ puede dividirse en bloques $$ A'=\pmatrix{ 0 &A^T\\ A&0 }, $$

El operador de propagación $M=A'/d$ se utiliza para los paseos aleatorios en dicho gráfico. Describe dónde se puede llegar (y la probabilidad) en un paso, partiendo de un vértice determinado.

Ahora $M^2$ describe dónde se encuentra con dos pasos y tiene la siguiente forma $$ M^2=d^{-2}\pmatrix{ A^TA&0\\ 0&AA^T }. $$

Creo que puedo interpretar $A^TA$ como la matriz de adyacencia de a $d^2$ -regular, no necesariamente de gráfico simple, $\phantom{(EDIT2:)}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!$ ya que tendrá $d$ bucles propios para cada vértice gráfico, así que mi pregunta es:

¿Puedo utilizar $\phantom{(EDIT:)}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!$ uno de los bloques de $M^2$ como operador de propagación, cuando restrinjo un problema dado a paseos de longitud par?

Me parece que estoy perdiendo algo de información porque el gráfico que $\phantom{(EDIT:)}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!$ uno de los bloques de $M^2$ actúa sobre tiene sólo la mitad de los vértices de $G$ . ¿Está esto relacionado con un cierto tipo de base adaptada a la simetría?

Answer 1

Sí, porque $M^2$ es diagonal en bloque, por lo que $$ M^{2k}=(M^2)^k=d^{-2k}\pmatrix{ A^TA&0\\ 0&AA^T }^k = d^{-2k}\pmatrix{ (A^TA)^k&0\\ 0&(AA^T)^k }. $$ Para decirlo de una manera más combinatoria, cada paseo de longitud par en $G$ consiste en $2k$ pasos, por lo que se puede dividir en $k$ bistecs. Un bistep se desplaza desde un conjunto de particiones de $G$ a la otra y luego de vuelta, por lo que termina permaneciendo dentro del mismo conjunto de partitas. La matriz $A^T A$ te dice de cuántas maneras se puede tomar un bistep de un vértice a otro, dentro de uno de los conjuntos de partitas, y $A A^T$ hace lo mismo para el otro conjunto de partos.