Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
$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
up vote 2 down vote accepted

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.

share|cite|improve this answer
+1 thanks...+3,...+10... – draks ... Jan 29 '13 at 8:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.