On Birkhoff's theorem for doubly stochastic completely positive maps of matrix algebras

by L. J. Landau and R. F. Streater, J. Linear Alg. and Appl., 193, 107-127, 1993.

ABSTRACT

A study is made of the extreme points of the convex set of doubly stochastic completely positive maps of the matrix algebra M_n. If n = 2, the extreme points are precisely the unitary conjugations, but if n > 2, there are nonunitary extreme points, examples of which are exhibited. A tilde operation is defined on the linear maps of M_n and used to give an elementary derivation of a result of Kuemmerer and Maassen. A transparent proof of Choi's theorem (that every n-positive map on M_n is completely positive) is given.

REMARKS

A doubly stochastic, or bistochastic, matrix is a square matrix with non-negative entries, and such that the sum of the entries in each row, and in each column, is unity. The set of bistochastic matrices form a convex set K under the convex structure of element-wise addition and scalar multiplication. Birkhoff's theorem states that any doubly stochastic matrix is a mixture of permutation matrices. This is quite hard to prove. It follows from the Krein-Milman theorem if we know that the extreme points of K make up the set of permutation matrices. It is not hard to show that every permutation matrix is an extreme point; the hard part is to show that there are no other extreme points.