Convexity, Schur convexity, and majorization theory - Signal Processing and Optimization for Transceiver Systems - page 722

stochastic (because some elements may be negative). In fact, the inverse
of a doubly stochastic matrix is doubly stochastic if and only if it is a
permutation matrix (see p. 48 of Marshall and Olkin [1979]).

Example 21.10: Stochastic matrices

The following matrices are doubly stochastic as can be verified by inspection.

⎡ ⎤ ⎡ ⎤

A 1 = cos 2 θ

,

111
111
111

110
101
011

sin 2 θ

A 2 = 1
3

A 3 = 1
2

⎣ ⎦ , ⎣ ⎦ .

sin 2 θ cos 2 θ

The first two matrices are also orthostochastic, though the third one is not.
Thus A 1 can be generated from the unitary matrix
cos θ

sin θ

− sin θ cos θ

by squaring its elements, and A 2 can be generated from the (normalized)

DFT matrix whose ( m, n ) element is e −j 2 πmn/ 3 / √ 3. The third matrix is
not orthostochastic because there cannot be a unitary matrix of the form
⎡

⎤

ab 0
c

⎣ ⎦ ,

0 d

0 ef

where a, b, c, d, e, and f are nonzero. For example, the inner product of the
first two columns is a ∗ b, which cannot be zero, as required for unitarity.
Another family of examples is obtained from circulant matrices (Appendix
D), e.g.,

⎡
⎣

⎤
⎦

c 0 c 1 c 2 c 3

c 3 c 0 c 1 c 2

A = .

c 2 c 3 c 0 c 1

c 1 c 2 c 3 c 0

0 such that k c k =1 . Circulants are doubly stochastic for any set of c k ≥

It can be shown (see p. 527 of Horn and Johnson [1985]) that A is doubly
stochastic if and only if it is a convex combination of permutation matrices, that
is,

K

A = α k P k ,

k =0

0with k α k =1 . This result is
called Birkhoff's theorem. The connection between majorization and stochastic
matrices is given by the following beautiful theorems [Marshall and Olkin, 1979]:

where P k are permutation matrices, and α k ≥