5
$\begingroup$

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?

  • 0
    @joriki although *[the resulting graph] will never be simple*, do you think my problem has a *simple* solution?2013-01-24

1 Answers 1

2

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.