A constructive decomposition and Fulkerson's characterization of permutation matrices

AbstractWe consider the set of n×n matrices X=(xij) for which ∑iϵI∑jϵJxij ⩾ |I|+|J|−n, for all I,J⊆ {1, 2,…, n}, with xij ⩾ 0 for all i, jϵ{1, 2,…, n}. It is shown that such matrices may be decomposed as X=S+N, where S is a doubly stochastic matrix and N is non-negative in all entries. The decomposition technique is constructive. This implies a result of Fulkerson that the matrices X, considered as lying in Rn2 form a convex polyhedron whose vertices are the permutation matrices. Finally, a subset of the inequalities of (1) is shown to be “essential”, as asserted by Fulkerson in [1] without proof