A Minimal Completion of Doubly Substochastic Matrix
Linear and Multilinear Algebra
Doubly stochastic matrices, Doubly substochastic matrices, Birkhoff's theorem, Permutation matrices
Let B be an n x n doubly substochastic matrix and let s be the sum of all entries of B. In this paper, we show that B has a sub-defect of k, which can be computed by taking the ceiling of n - s, if and only if there exists an (n + k) x (n + k) doubly stochastic extension containing B as a submatrix and k minimal. We also propose a procedure constructing a minimal completion of B, and then express it as a convex combination of partial permutation matrices.
Cao, Lei; Koyuncu, Selcuk; and Parmer, Timmothy, "A Minimal Completion of Doubly Substochastic Matrix" (2016). Mathematics Faculty Articles. 270.