Sunday, December 17, 2017

Useful Matrix

Transition Matrix (Used in Markov Chain, might expand the topic to markov chain later)


For the ith row in the matrix, it represents how other vertices will be pointed to the ith vertex.
e.g. the first row represents the A vertex in this graph, and the 0 represents there is no cycle pointing back to itself, the 1/2 represents there is 1/2 pointing to A from B, the 1 represents there is 1 pointing to A from C.

One important note is that the entries in each column will add up to one. It is one of the characteristic of transition matrix must have.

Another characteristic is that when the transition matrix has an eigenvalue of one, it represents that the transition matrix has a steady state, and that steady state is the eigenvector when eigenvalue is one; however, it is not necessarily true.

Finally, transition matrix only works on directed graph.

$A \vec{x} = \lambda \vec{x} $
when lambda = 1, the eigenvector will be steady state vector.