With a random walk problem, A is the adjacency matrix of a directed weighted graph where, 0 Saij S1 is the probability of a move from the vertex v to the vertex v;. Vvi: = 1 , where N is the number of vertices. You know that B = A represents the probabilities of moves with length two. In other words, bij is the probability of starting from v; and reaching to v; after two steps. N bis = probability of vi vv; = { > Vk { = di,kakj = a' A = k=1 = B = AXA = A2 But it is a forward problem. Now the matrix B is given to you. It is desired to decompose it into two equal matrices B = A x A. The matrix B may be an incorrect adjacency matrix (BA: A x A = B), however the probability constraints are held: 0