Page 107 - Matrices theory and applications

5. Nonnegative Matrices
90
we denote by O(x) the set of indices i such that x i =0, and by o(x)
its cardinality, in such a way that ∂K n comprises those points satisfying
o(x) ≥ 1. One always has m ij =0 for (i, j) ∈ O(Mx) × O(x) ,where I
denotes the complement of I in {1,... ,n}.
Proposition 5.5.1 Let x ∈ K n and M ∈ ∆ n be given. Then one has
o(Mx) ≤ o(x). c c
c
Moreover, if o(Mx)= o(x), one has m ij =0 for every (i, j) ∈ O(Mx) ×
O(x).
Proof
Let us compute
n n

o(x) − o(Mx)= m ij − m ij = m ij ≥ 0.
c
i=1 O(x) O(Mx) j=1 O(Mx) ×O(x)
The case of equality is immediate.
We could have obtained the first part of the proposition by applying
Theorem 5.5.2.
Corollary 5.5.2 Let I and J be two subsets of {1,... ,n} and let M ∈ ∆ n
c
be a matrix satisfying m ij =0 for every (i, j) ∈ I × J . Then one has
c
|J|≥ |I|. If, moreover, |I| = |J|,then m ij also vanishes for (i, j) ∈ I × J.
Proof
c
n
It is sufficient to choose x ∈ K with J = O(x)if J is nonempty. If J
is empty, the statement is obvious.
We shall denote by S∆ n (S for strict) the set of doubly stochastic matri-
ces M for which the conditions |I| = |J| and m ij =0 for every (i, j) ∈ I×J c
imply either I = ∅ or I = {1,... ,n}. These are also the matrices for which
x ∈ ∂K n implies o(Mx) <o(x). This set does not contain permutation
matrices P, since these satisfy o(Px)= o(x) for every x ∈ K n .
Let M ∈ ∆ n be given. A decomposition of M consists of two partitions
I 1 ∪ ··· ∪ I r and J 1 ∪ ··· ∪ J r of the set {1,... ,n} such that
(i ∈ I l ,j ∈ J m ,l = m)=⇒ m ij =0.
From Corollary 5.5.2, we have |I l | = |J l | for every l. Eliminating empty
parts if necessary, we can always assume that none of the I l ’s or J l ’s is
empty. A decomposition of M furnishes a block structure, in which each
row-block has only one nonzero block, and the same for the column-blocks.
The blocks of indices I l × J l are themselves stochastic matrices. A matrix
of S∆ n admits only the trivial decomposition r =1, I 1 = J 1 = {1,... ,n}.
If M admits two decompositions, one with the sets I l ,J l ,1 ≤ l ≤ r,the

other one with I ,J ,1 ≤ l ≤ s, let us form the partitions ∪ l,m I and
l l lm