Binary X-rays of doubly stochastic matrices

Abstract

The X-ray of a permutation is a sequence of sums along each diagonal of the associated permutation matrix. They satisfy certain necessary constraints on distribution of the values, which are conjectured to be sufficient when the sequence is binary. By re-expressing the constraints in a form that allows for real-valued relaxations, we prove that these binary sequences are always X-rays of doubly stochastic matrices.