The doubly stochastic versus permutation binary X-ray conjecture

Let DD be a doubly stochastic matrix of order nn, meaning that it has nonnegative real entries and every row and column sums to 11. Its binary diagonal X-ray is the vector d(D)=(d1,d2,,d2n1)d(D)=(d_1,d_2,\dots,d_{2n-1}) whose entries record which diagonals contain nonzero mass; for a permutation πSn\pi \in S_n, write d(π)d(\pi) for the analogous X-ray. The doubly stochastic versus permutation binary X-ray conjecture. There is a doubly stochastic matrix DD of order nn with binary diagonal X-ray

d(D)=(d1,d2,,d2n1)d(D)=(d_1,d_2,\dots,d_{2n-1})

if and only if there is a permutation πSn\pi \in S_n with binary diagonal X-ray

d(π)=(d1,d2,,d2n1).d(\pi)=(d_1,d_2,\dots,d_{2n-1}).

The forward implication asserts that every binary diagonal pattern feasible for a doubly stochastic matrix is already feasible for a permutation matrix. The density conditions are necessary by the Birkhoff decomposition, while sufficiency remains conjectural.

Sources & referencesView supporting material

Primary source

Gustav Nordh, “A note on X-rays of permutations and a problem of Brualdi and Fritscher”, arXiv:1707.03928 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.