Page 104 - Matrices theory and applications

5.5. Stochastic Matrices
87
One has thus d j = d k , provided that a jk =0. Since A is irreducible, one
can link any two indices j and k by a chain j 0 = j,... ,j r = k such that
=0 for every s. It follows that d j = d k for every j, k. But since one
a j s−1 ,j s
p
may choose Y 1 = X 1 ,that is, α 1 = 0, one also has d 1 = 1 and hence D =
I n .The α j are thus pth roots of unity. With a conjugation by a permutation
matrix we may limit ourselves to the case where D has the block-diagonal
form diag(J 0 ,ωJ 1 ,... ,ω p−1 J p−1 ), where the J l are identity matrices of
respective sizes n 0 ,... ,n p−1 . Decomposing A into blocks A lm of sizes n l ×
k
n m ,one obtains ω A jk = ω j+1 A jk directly from the conjugation identity.
Hence A jk = 0 except for the pairs (j, k)ofthe form (0, 1), (1, 2),... , (p −
2,p − 1), (p − 1, 0). This is the announced cyclic form.
5.5 Stochastic Matrices
Definition 5.5.1 Amatrix M ∈ M n (IR) is said to be stochastic if M ≥ 0
and if for every i =1,... ,n, one has
n

m ij =1.
j=1
One says that M is bistochastic (or doubly stochastic)if both M and M T
are stochastic.
n
Denoting by e ∈ IR the vector all of whose coordinates equal one, one
sees that M is stochastic if and only if M ≥ 0and Me = e.Moreover, M
T
T
is bistochastic if M ≥ 0, Me = e,and e M = e .If M is stochastic, one
n
has Mx ∞ ≤ x ∞ for every x ∈ CC , and therefore ρ(M) ≤ 1. But since
Me = e, one has in fact ρ(M)= 1.
The stochastic matrices play an important role in the study of Markov
chains. A special case of a bistochastic matrix is a permutation matrix P(σ)
(σ ∈ S n ), whose entries are
j
p ij = δ .
σ(i)
The following theorem explains the role of permutation matrices.
Theorem 5.5.1 (Birkhoff) Amatrix M ∈ M n(IR) is bistochastic if and
only if it is a center of mass (that is, a barycenter with nonnegative weights)
of permutation matrices.

The fact that a center of mass of permutation matrices is a doubly stochas-
tic matrix is obvious, since the set ∆ n of doubly stochastic matrices is
convex. The interest of the theorem lies in the statement that if M ∈ ∆ n ,
there exist permutation matrices P 1 ,... ,P r and positive real numbers
α 1 ,... ,α r with α 1 + ··· + α r =1 such that M = α 1 P 1 + ··· + α r P r .