A square real matrix is doubly stochastic if its entries are nonnegative and every row and column sums to . Its positive-entry support satisfies the condition of the Hall marriage theorem: for a row subset , by summing column capacities. Consequently its support contains a permutation matrix.
Every doubly stochastic matrix is a convex combination of permutation matrices. Equivalently, the extreme points of the doubly stochastic convex polytope are exactly the permutation matrices. The extreme-point assertion follows from an alternating-cycle perturbation of a doubly stochastic matrix; the convex-hull assertion follows because a bounded finite-dimensional polytope is the convex hull of its vertices. Permutation matrices are extreme since their zero entries force the same zeros in every convex decomposition.
For a doubly stochastic matrix, the Hall marriage theorem supplies a perfect matching in its positive-entry support. Subtract the smallest matched entry times the corresponding permutation matrix. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a convex combination of permutation matrices. With initially positive entries, there are at most terms, since a positive-mass residual has at least positive entries. Elementary augmenting-path matching gives arithmetic operations.
For a doubly stochastic matrix with a fractional entry, form the row-column bipartite graph of entries strictly between zero and one. Every incident vertex has degree at least two, so there is an even cycle. A matrix supported on that cycle with alternating entries has zero row and column sums. A sufficiently small positive multiple can be both added and subtracted while preserving entry bounds. The original matrix is then the midpoint of two distinct doubly stochastic matrices, so it is not an extreme point.
Articles by others on the same topic
A **doubly stochastic matrix** is a special type of square matrix that has non-negative entries and each row and each column sums to 1. In other words, for a matrix \( A \) of size \( n \times n \), the following conditions must hold: 1. \( a_{ij} \geq 0 \) for all \( i, j \) (all entries are non-negative).