Editing Markov chain (section)

==== Index of primitivity ====
The ''index of primitivity'', or ''exponent'', of a regular matrix, is the smallest <math>k</math> such that all entries of <math>M^k</math> are positive. The exponent is purely a graph-theoretic property, since it depends only on whether each entry of <math>M</math> is zero or positive, and therefore can be found on a directed graph with <math>\mathrm{sign}(M)</math> as its adjacency matrix. 

There are several combinatorial results about the exponent when there are finitely many states. Let <math>n</math> be the number of states, then<ref>{{Cite book |last=Seneta |first=E. (Eugene) |url=http://archive.org/details/nonnegativematri00esen_0 |title=Non-negative matrices; an introduction to theory and applications |date=1973 |publisher=New York, Wiley |others=Internet Archive |isbn=978-0-470-77605-6 |chapter=2.4. Combinatorial properties}}</ref>

* The exponent is <math> \leq (n-1)^2 + 1 </math>. The only case where it is an equality is when the graph of <math>M</math> goes like <math>1 \to 2 \to \dots \to n \to 1 \text{ and } 2</math>.
* If <math>M</math> has <math>k \geq 1</math> diagonal entries, then its exponent is <math>\leq 2n-k-1</math>.
* If <math>\mathrm{sign}(M)</math> is symmetric, then <math>M^2</math> has positive diagonal entries, which by previous proposition means its exponent is <math>\leq 2n-2</math>.
* (Dulmage-Mendelsohn theorem) The exponent is <math>\leq n+s(n-2)</math> where <math>s</math> is the [[Girth (graph theory)|girth of the graph]]. It can be improved to <math>\leq (d+1)+s(d+1-2)</math>, where <math>d</math> is the [[Diameter (graph theory)|diameter of the graph]].<ref>{{Cite journal |last=Shen |first=Jian |date=1996-10-15 |title=An improvement of the Dulmage-Mendelsohn theorem |journal=Discrete Mathematics |volume=158 |issue=1 |pages=295–297 |doi=10.1016/0012-365X(95)00060-A |doi-access=free }}</ref>