The Stochastic Matrix and Linear Programming

Abstract: We take a stochastic matrix (or Markov matrix) and place the matrix in a linear programming framework. The dual program is in a sense a novel “completion” of the stochastic matrix formulation. We identify the primal linear program (LP) as a “quantity” program (based on a key eigenvalue) and the dual program as a “price” program (turning on an eigenvalue of the transpose matrix). Our approach is to present detailed numerical examples, examples based on particular 3 x 3 stochastic matrices. We do not present new types of evolution “descending from” a stochastic matrix. The linear programming framework provides a novel way to envisage a stochastic matrix and its transpose.