The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach

Abstract

The problem of determining DS_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, PM_n, is contained in DS_n and is known to be exactly DS_n for $n\le 4,$ but strictly contained within DS_n for n = 5. Here, we present a Boundary Conjecture that asserts that the boundary of DS_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 DS_n and obtain computational results that support the Boundary Conjecture. We also give evidence that DS_n is equal to PM_n for certain n > 5.

Keywords:

• Doubly stochastic matrix
• Eigenvalue
• Group representation
• Permutation matrix
• Single eigenvalue problem

2010 AMS Subject Classification:

• 15-04
• 15A18
• 15A29
• 15B51

Acknowledgments

We would like to thank the anonymous reviewer for his suggestions on the manuscript. We would also like to thank Jamie Barsotti for assistance with bringing our attention to the relevant theory on G-sets, and for assistance in deriving the algorithm to compute the inequivalent pairs. Moreover, we would like to thank John Wilkes, who carried out initial work on this problem in his honors thesis at the College of William and Mary advised by Charles R. Johnson [10].

This work was performed [in part] using computing facilities at the College of William and Mary, which were provided by contributions from the National Science Foundation, the Commonwealth of Virginia Equipment Trust Fund and the Office of Naval Research.

Declaration of Interest

No potential conflict of interest was reported by the author(s).

Correction Statement

This article has been republished with minor changes. These changes do not impact the academic content of the article.

Additional information

Funding

This work was supported by the National Science Foundation under Grant DMS #1757603.