Page 106 - Matrices theory and applications

89
5.5. Stochastic Matrices
Theorem 5.5.2 Amatrix A is bistochastic if and only if Ax x for every
n
x ∈ IR .
Proof
If A is bistochastic, then
Ax 1 ≤ A 1 x 1 = x 1 ,
T
since A is stochastic. Since A is stochastic, Ae = e. Applying this inequal-
ity to x − te, one therefore has Ax − te 1 ≤ x − te 1. Proposition 3.4.1
then shows that x ≺ Ax.
n
Conversely, let us assume that x ≺ Ax for every x ∈ IR .Choosing x as
j
j
j
the jth vector of the canonical basis, e , the inequality s 1 (e ) ≤ s 1 (Ae )
j
j
expresses that A is a nonnegative matrix, while s n (e )= s n (Ae ) yields
n

a ij =1. (5.2)
i=1
1
One then chooses x = e. The inequality s 1 (e) ≤ s 1 (Ae) expresses that
Ae ≥ e. Finally, s n (e)= s n (Ae)and Ae ≥ e give Ae = e. Hence, A is
bistochastic.
This statement is completed by the following.
n
Theorem 5.5.3 Let x, y ∈ IR .Then x ≺ y if and only if there exists a
bistochastic matrix A such that y = Ax.
Proof
From the previous theorem, it is enough to show that if x ≺ y,there exists
A, a bistochastic matrix, such that y = Ax. To do so, one applies Theorem
3.4.2: There exists a Hermitian matrix H whose diagonal and spectrum
are y and x, respectively. Let us diagonalize H by a unitary conjugation:
2
∗
H = U DU,with D =diag(x 1 ,... ,x n ). Then y = Ax,where a ij = |u ij | .
Since U is unitary, A is bistochastic. 2
An important aspect of stochastic matrices is their action on the simplex
! "
n
K n := x ∈ IR ; x ≥ 0and x i =1 .
i
It is clear that M T is stochastic if and only if M(K n) is contained in K n ;
M is bistochastic if, moreover, Me = e.

Considered as a part of the affine subspace whose equation is x i =1,
i
K n is a convex set with a nonempty interior. Its interior comprises those
points that satisfy x> 0. One denotes ∂K n the boundary of K n .If x ∈ K n ,
1
For another vector y, s 1(y) ≤ s 1(Ay)does notimply Ay ≥ y.
2
This kind of bistochastic matrix is called orthostochastic.