Page 105 - Matrices theory and applications

5. Nonnegative Matrices
88
Let us recall that a point a of a convex set C is an extreme point if the
equality x = θy +(1 − θ)z,with y, z ∈ C and θ ∈ (0, 1) implies y = z = x.
The Krein–Milman theorem (see [30], Theorem 3.23) says that a convex
compact subset of IR is the convex hull, that is, the set of centers of mass,
of its extreme points. Since ∆ n is closed and bounded, hence compact, it
is permissible to apply the Krein–Milman theorem.
Proof n
To begin with, it is immediate that the permutation matrices are ex-
treme points of ∆ n . From the Krein–Milman theorem, the proof amounts
to showing that there is no other extreme point in ∆ n .
Let M ∈ ∆ n be given. If M is not a permutation matrix, there exists
∈ (0, 1). Since M is stochastic, there also exists j 2 = j 1
an entry m i 1 j 1
∈ (0, 1). Since M T is stochastic, there exists i 2 = i 1
such that m i 1 j 2
∈ (0, 1). By this procedure one constructs a sequence
such that m i 2 j 2
∈ (0, 1). Since the
(j 1 ,i 1 ,j 2 ,i 2,... ) such that m i l j l ∈ (0, 1) and m i l−1 j l
set of indices is finite, it eventually happens that one of the indices (a row
index or a column index) is repeated.
Therefore, one can assume that the sequence (j 1 ,i 1 ,... ,j r ,i r ,j r+1 = j 1 )
=1,
has the above property. Let us define a matrix B ∈ M n (IR)by b i l j l
T
= −1, b ij = 0 otherwise. By construction, Be =0 and e B =0. If
b i l j l+1
T
T
α ∈ IR, one therefore has (M ± αB)e = e and e (M ± αB)= e .If α> 0
is small enough, M ± αB turns out to be nonnegative. Finally, M + αB
and M − αB are bistochastic, and
1 1
M = (M − αB)+ (M + αB).
2 2
Hence M is not an extreme point of ∆ n .
Here is a nontrivial consequence (Stoer and Witzgall [32]):
n
Corollary 5.5.1 Let · be a norm on IR , invariant under permutation
of the coordinates. Then M =1 for every bistochastic matrix (where by
abuse of notation we have used · for the induced norm on M n (IR)).
Proof
To begin with, P = 1 for every permutation matrix, by assumption.
Since the induced norm is convex (true for every norm), one deduces
from Birkhoff’s theorem that M ≤ 1 for every bistochastic matrix.
Furthermore, Me = e implies M ≥ Me / e =1.
This result applies, for instance, to the norm · p , providing a nontrivial
convex set on which the map 1/p → log M p is constant (compare with
Theorem 4.3.1).
The bistochastic matrices are intimately related to the relation ≺ (see
Section 3.4). In fact, we have the following theorem.