# Walks of Even Length on a Bipartite Graph

Given a random walk on a simple $d$-regular bipartite graph $G$. The adjacency matrix $A'$ of $G$ may be split into blocks $$A'=\pmatrix{ 0 &A^T\\ A&0 },$$

The propagation operator $M=A'/d$ is used for random walks on such a graph. It describes where you can get (and the probality) in one step, starting from a given vertex.

Now $M^2$ describes where you get with two steps and has the following form $$M^2=d^{-2}\pmatrix{ A^TA&0\\ 0&AA^T }.$$

I think I may interpret $A^TA$ as the adjacency matrix of a $d^2$-regular, not necessarily simple graph, $\phantom{(EDIT2:)}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!$ since it will have $d$ self-loops for each vertex, graph, so my question is:

May I use $\phantom{(EDIT:)}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!$ one of the blocks of $M^2$ as propagation operator, when I restrict a given problem to walks of even length?

It feels to me that I'm loosing some information because the graph that $\phantom{(EDIT:)}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!$ one of the blocks of $M^2$ acts on has only half of the vertices of $G$. Is this related to a certain kind of symmetry adapted basis?

-
$M^2$ acts on all vertices of $G$ - even length walks stating on white vertices and even length walks starting on black vertices. –  Chris Godsil Dec 26 '12 at 22:22
Why is $A^TA$ $d^2$-regular? Any number of the two-step paths may lead to the same vertices. –  joriki Dec 26 '12 at 23:04
@joriki I tried some examples and was musing about the analogy between $d$-regular $\leftrightarrow A'/d$ and $d^2$-regular $\leftrightarrow (A')^2/d^2$. What do you want to tell me with Any number of the two-step... ? All in all the $d^2$-regularity is not the thing that I'd like to have the focus. The focus is on the blocks. Sorry if this is distracting... –  draks ... Dec 26 '12 at 23:27
Sorry, I'd missed what you meant by "not necessarily simple". In fact it will never be simple, since it will have $d$ self-loops for each vertex. –  joriki Dec 26 '12 at 23:56
@joriki although [the resulting graph] will never be simple, do you think my problem has a simple solution? –  draks ... Jan 24 '13 at 22:20

Yes, because $M^2$ is block diagonal, so $$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 }.$$ To put it in a more combinatorial way, each even-length walk on $G$ consists of $2k$ steps, so it can be split into $k$ bisteps. A bistep travels from one partite set of $G$ to the other and then back again, so ends up remaining within the same partite set. The matrix $A^T A$ tells you how many ways to take a bistep from one vertex to another, within one of the partite sets, and $A A^T$ does the same for the other partite set.