The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach

Abstract

The problem of determining $D{S}_n$, the complex numbers that occur as an eigenvalue of an $n$-by-$n$ doubly stochastic matrix, has been a target of study for some time. The Perfect-Mirsky region, $P{M}_n$, is contained in $D{S}_n$, and is known to be exactly $D{S}_n$ for $n\le 4$, but strictly contained within $D{S}_n$ for $n=5$. Here, we present a Boundary Conjecture that asserts that the boundary of $D{S}_n$ is achieved by eigenvalues of convex combinations of pairs of (or single) permutation matrices. We present a method to efficiently compute a portion of $D{S}_n$, and obtain computational results that support the Boundary Conjecture. We also give evidence that $D{S}_n$ is equal to $P{M}_n$ for certain $n>5$.