Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

up vote 2 down vote accepted
+50

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|improve this answer
    
+1 thanks...+3,...+10... –  draks ... Jan 29 '13 at 8:03
add comment

Your Answer

 
discard

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.