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
    $M^2$ acts on all vertices of $G$ - even length walks stating on white vertices and even length walks starting on black vertices.2012-12-26
  • 0
    Why is $A^TA$ $d^2$-regular? Any number of the two-step paths may lead to the same vertices.2012-12-26
  • 0
    @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...2012-12-26
  • 0
    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.2012-12-26
  • 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.