Transition matrix

A transition matrix (or stochastic matrix) is a square matrix whose rows sum to 1, encoding the probabilities of moving from one state to another in a discrete-time dynamical system. It is the mathematical engine of Markov chains, where it governs the evolution of probability distributions over states, and of network diffusion models, where it determines how information or influence propagates through a graph.

The spectral properties of a transition matrix determine the long-term behavior of the system it describes. A transition matrix with a unique stationary distribution — guaranteed when the underlying process is ergodic — drives any initial distribution toward that fixed point. This convergence is not just a statistical phenomenon; it is a consequence of the Perron-Frobenius theorem, which states that the largest eigenvalue of a positive matrix is real, simple, and associated with a strictly positive eigenvector.

In the context of matrix algebra and dynamical systems, the transition matrix reveals how local rules produce global structure. A random walk on a network, a belief propagation algorithm, and a PageRank computation are all instances of transition-matrix dynamics operating on different state spaces.