Two permutation matrices generate the doubly stochastic spectral boundary
Let $\mathcal{D}_n$ be the set of real $n \times n$ doubly stochastic matrices, and let $$D_n = \{z \in \mathbb{C} : z \in \sigma(A) \text{ for some } A \in \mathcal{D}_n\}$$ be the set of their eigenvalues, with boundary $\partial D_n$ in $\mathbb{C}$. For every $k \le n$, $D_n$ contains the convex hull $\Pi_k$ of the $k$-th roots of unity, and $D_n = \Pi_1 \cup \dots \cup \Pi_n$ for $n \le 3$ (Perfect and Mirsky) and $n = 4$ (Levick, Pereira and Kribs), but not for $n = 5$ (Mashreghi and Rivard). Harlev, Johnson and Lim observe that the statement below holds whenever $D_n = \Pi_1 \cup \dots \cup \Pi_n$, so for $n \le 4$.
Problem. For every $n \ge 1$ and every $z \in \partial D_n$, are there $n \times n$ permutation matrices $P$ and $Q$, possibly equal, and $t \in [0, 1]$ with $$\det\bigl(zI - tP - (1 - t)Q\bigr) = 0?$$
Source: Harlev, Johnson and Lim (2022; arXiv 2019), Conjecture 2.7, the Boundary Conjecture (Conjecture 2.8 in arXiv v1).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CO, SP
- Keywords
- doubly stochastic matrices, inverse eigenvalue problems, OpenProblemsInNLA, permutation matrices
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@article{harlev2022,
author = {Harlev, Amit and Johnson, Charles R. and Lim, Derek},
title = {The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach},
journal = {Exp. Math.},
volume = {31},
number = {3},
year = {2022},
pages = {936--945},
doi = {10.1080/10586458.2020.1727799},
eprint = {1908.03647},
archivePrefix = {arXiv},
}
@article{perfect1965,
author = {Perfect, Hazel and Mirsky, L.},
title = {Spectral properties of doubly-stochastic matrices},
journal = {Monatsh. Math.},
volume = {69},
number = {1},
year = {1965},
pages = {35--57},
doi = {10.1007/BF01313442},
}
@article{levick2015,
author = {Levick, Jeremy and Pereira, Rajesh and Kribs, David W.},
title = {The four-dimensional {P}erfect-{M}irsky {C}onjecture},
journal = {Proc. Amer. Math. Soc.},
volume = {143},
number = {5},
year = {2015},
pages = {1951--1956},
doi = {10.1090/S0002-9939-2014-12412-9},
}
@article{mashreghi2007,
author = {Mashreghi, Javad and Rivard, Roland},
title = {On a conjecture about the eigenvalues of doubly stochastic matrices},
journal = {Linear Multilinear Algebra},
volume = {55},
number = {5},
year = {2007},
pages = {491--498},
doi = {10.1080/03081080600899296},
}
@misc{openproblemsinnla-is01,
author = {Townsend, Alex},
title = {{IS-01}: Two permutation matrices generate the doubly stochastic spectral boundary},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/IS-01/README.md},
note = {Read at commit 7336302, 2026-10-06},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00148, "Two permutation matrices generate the doubly stochastic spectral boundary", clopen.solutions.