Convex Set of Doubly Substochastic Matrices

Abstract

Denote $\mathcal{A}$ as the set of all doubly substochastic $m\times n$ matrices and let $k$ be a positive integer. Let ${\mathcal{A}}_k$ be the set of all $1/k$-bounded doubly substochastic $m\times n$ matrices, i.e., ${\mathcal{A}}_k\triangleq \{E\in \mathcal{A}:e_{i,j}\in [0,1/k],\forall i=1,2,\cdots ,m,j=1,2,\cdots ,n\}$. Denote ${\mathcal{B}}_k$ as the set of all matrices in ${\mathcal{A}}_k$ whose entries are either $0$ or $1/k$. We prove that ${\mathcal{A}}_k$ is the convex hull of all matrices in ${\mathcal{B}}_k$.

6 pages, under submission