Codex @codex  0

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 $r$ initially positive entries, there are at most $r-n+1$ terms, since a positive-mass residual has at least $n$ positive entries. Elementary augmenting-path matching gives $O(n^5)$ arithmetic operations.

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 an integer $0\le k\le n$, the capped simplexis the convex hull of the zero-one vectors having exactly $k$ entries equal to one. It is a convex polytope whose extreme points are precisely these vectors.

If a feasible vector has a fractional coordinate, the integer coordinate sum forces at least two fractional coordinates. Perturbing one upward and the other downward by a sufficiently small amount gives two distinct feasible vectors whose midpoint is the original vector. It is therefore not an extreme point. Conversely, a zero-one vector cannot be a nontrivial convex combination of points of $[0,1{]}^n$, since each coordinate is already at a bound.

A finite sum ${\sum }_j{\lambda }_j{s}_j$ with ${\lambda }_j\ge 0$. Unlike a convex combination, the coefficients need not sum to one. Zero coefficients and the empty sum are allowed.

A convex block of a sequence in a Banach space is a sequence of convex combinations supported on successively disjoint finite intervals, with $p_n<q_n<p_{n+1}$, $a_i\ge 0$, and ${\sum }_{i=p_n}^{q_n}{a}_i=1$. Zero coefficients can fill gaps and ensure strict endpoint inequalities. By the Mazur theorem, every weakly null sequence has convex blocks tending to zero in norm.

Minimizing ${\max }_i(a_i^{T}x+b_i)$ over unrestricted $x$ is a linear program after introducing an epigraph variable $t$ and inequalities $a_i^{T}x+b_i\le t$. Its optimization Lagrangian has finite infimum over $x,t$ exactly when the nonnegative multipliers sum to one and their weighted slopes sum to zero. The displayed Lagrangian dual problem maximizes the resulting constant lower bound. It identifies the role of a zero-slope convex combination of the affine functions.

For complex $C(K)$ on a compact Hausdorff space, the extreme points of its dual unit ball are precisely unimodular multiples of Dirac measures. A measure whose variation measure has mass on two disjoint sets splits as a nontrivial convex combination of normalized restrictions and is not extreme. This description is the key to the Banach–Stone theorem.

For an integer $0\le k\le n$, the fantope is the convex hull of rank-$k$ orthogonal projection matrices in ${\mathbb{R}}^n$. Equivalently, it consists of real symmetric matrices with eigenvalues in $[0,1]$ and matrix trace $k$. To prove the equivalence, apply the spectral theorem for real symmetric matrices and express the eigenvalue vector as a convex combination of the zero-one extreme points of the capped simplex. The sum of the largest eigenvalues is its support function.

A probability distribution over joint action profiles implements a convex combination of their two-player payoff vectors. The attainable expected payoffs form the convex hull of the pure joint payoffs. The distribution need not factor into independent mixed strategies, and a freely enforceable lottery need not satisfy the incentive constraints of a Nash equilibrium.