Doubly substochastic matrix with fixed integer sum of entries

127 Views Asked by At

The Birkhoff-von Neumann theorem states that the set of $n \times n$ doubly stochastic matrices (i.e., non-negative entries with row and column sums equal to 1) is the convex hull of all $n \times n$ permutation matrices (subset with all entries 0-1 valued). A related classical result is that the set of $n \times n$ doubly substochastic matrices (i.e., non-negative entries with row and column sums at most 1) is the convex hull of all $n \times n$ partial permutation matrices (again, the subset with all entries 0-1 valued).

Is the set of substochastic matrices whose entries sum to a fixed integer $k \in \mathbb{N}$ the convex hull of the set of $n \times n$ partial permutation matrices whose entries sum to $k$? Clearly, the convex hull of these points is contained in this set, but I'm unsure about the reverse inclusion. My motivation is a problem where I'm seeking a certain matching with $k$ edges on a balanced bipartite graph with $2n$ nodes. These matchings can be identified with partial permutation matrices whose entries sum to $k$, and the set of interest appears in a linear programming relaxation.

2

There are 2 best solutions below

1
On

The answer is positive, see Theorem 4.1 of this paper.

0
On

Let $A$ be a $k$-doubly stochastic. Then, $\frac1kA$ is a usual doubly stochastic matrix. Now, write this as a convex combination of usual permutation matrices. Multiply with $k$ to finish the job.