REVIEW 2 major objections 4 minor 18 references
The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Pairing two permutation matrices may determine the whole boundary of the doubly stochastic eigenvalue region.
desk verdict A genuinely useful computational paper with honest conjectures; the n=5 classification and pair-reduction are real contributions, but the n=6–11 Perfect-Mirsky evidence is finite sampling and should be framed as such. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the standard representation of the symmetric group: after conjugating by a fixed deflating matrix, each n-by-n permutation matrix becomes a block matrix whose lower right (n-1)-by-(n-1) block carries all eigenvalues except the common eigenvalue 1. The set of these blocks is an irreducible representation of S_n, and DS_n is the eigenvalue region of its convex hull. The computational reduction then uses double cosets of centralizers, via Mackey's formula, to pick one representative from each equivalence class of permutation pairs under uniform permutation similarity, cutting the number of pairs from O((n!)^2) to O(n!). Along each pair, eigenvalues are computed on a mesh of convex coefficients, and each point is tested against the polygons Π_k whose union is PM_n.
What would settle it
For any n in {6,7,8,9,10,11}, run an adaptive search over all inequivalent pairs that refines the mesh near the boundary of PM_n and find a single eigenvalue outside PM_n; or find a convex combination of three permutation matrices with an eigenvalue outside the region generated by all pairs. Either observation would refute the paper's main conjectures.
Extended reading notes
Core claim
The central claim is that pairs determine the boundary: for every boundary point z of DS_n there are permutation matrices P and Q, possibly equal, and a coefficient t in [0,1] such that z is an eigenvalue of tP + (1-t)Q. The paper does not prove this claim, but it provides the first systematic computational test of it. Using a deflation that removes the common eigenvalue 1 and a group-theoretic reduction to inequivalent pairs, the authors compute eigenpaths for all representative pairs for n up to 11 and find no counterexample to the Perfect-Mirsky conjecture for n = 6 through 11. For n = 5, they locate the known exceptional eigenpath and show it is the only one, up to uniform permutation similarity, among all pairs of that cycle-type pairing.
Load-bearing premise
The conclusion rests on the assumption that the finite mesh of convex coefficients used for each pair of permutations is fine enough to catch every interval where an eigenpath leaves PM_n; for n = 11 the mesh is 1/200, and no bound ties that spacing to the size of a possible excursion.
Editorial extensions
If this is right
- If the Boundary Conjecture holds, then because DS_n is star-shaped from the interval [0,1], every point of DS_n is an eigenvalue of a convex combination of at most three permutation matrices.
- For n = 6 through 11, the pair computations combined with the Boundary Conjecture would settle the Perfect-Mirsky conjecture for those dimensions, giving DS_n = PM_n.
- The pair-reduction method makes the doubly stochastic single eigenvalue problem computationally feasible to high precision for moderate n, since only O(n!) representative pairs need checking rather than all convex combinations.
- The n = 5 exception would be understood as a single isolated phenomenon among inequivalent pairs, giving a clear target for future theoretical explanation.
Reading between the lines
- A natural testable extension is to replace fixed meshes with adaptive refinement near the boundary of PM_n for n = 6 and 7; if an excursion narrower than the 1/10000 mesh exists, it would surface there.
- The authors' observation that the alternating groups A4 and A5 in the standard representation violate the analogous pair-boundary property suggests the Boundary Conjecture for S_n depends on the full symmetric group and its star-shaped convex hull, not on a general fact about matrix-group hull spectra.
- If the Boundary Conjecture is correct, double-coset enumeration could serve as a general tool for finding extremal eigenpaths in other spectral sets defined by convex hulls of group orbits.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the set DS_n of complex numbers occurring as eigenvalues of n-by-n doubly stochastic matrices. It states the Boundary Conjecture (Conjecture 2.7) that every boundary point of DS_n is an eigenvalue of a convex combination of at most two permutation matrices, and it develops a computational method, based on group-theoretic reduction to inequivalent pairs of permutations, to search for eigenvalues outside the Perfect-Mirsky region PM_n. The paper reports that no counterexamples to the Perfect-Mirsky conjecture were found for n = 6 through 11, leading to Conjecture 7.1 that DS_n = PM_n for those n, and it analyzes the exceptional n = 5 case in detail, including the observation that only one inequivalent pair generates an eigenvalue outside PM_5. The authors also report that for the standard representations of A_4 and A_5, the analogous pair-boundary property fails, and they acknowledge the finite-mesh limitations of their evidence.
Significance. If the Boundary Conjecture is correct, the doubly stochastic single eigenvalue problem reduces on the boundary to one-parameter families of convex combinations of two permutation matrices, making numerical exploration tractable and potentially leading to a proof of Perfect-Mirsky for small n. The paper's rigorous lemmas (e.g., Lemma 2.3 and Corollary 2.4 on star-shapedness), the group-theoretic reduction to inequivalent pairs (Algorithm 1 and Table 1), and the reproducible code repository are genuine strengths. The explicit discussion of the A_4 and A_5 counterexamples to the pair-boundary property is honest and important. However, the central evidence for both Conjecture 2.7 and Conjecture 7.1 is finite sampling without certified error bounds, so the conjectures should be regarded as heuristic rather than established.
major comments (2)
- [§5, Conjecture 7.1] The evidence for DS_n = PM_n for n = 6,...,11 rests on finite mesh searches with m = 10000 for n = 6-9, m = 1000 for n = 10, and m = 200 for n = 11, and no bound is given that relates the mesh size to the minimum distance by which an eigenpath could leave PM_n between sample points. The paper itself notes in Section 5 that finer meshes may be necessary for larger n because exceptional excursions might be smaller. Without a certified numerical method (for example, interval arithmetic applied to the characteristic polynomials, or Lipschitz estimates for eigenvalues as functions of the convex parameter t), the computations cannot rule out a narrow excursion, and the statement of Conjecture 7.1 as unqualified is stronger than the evidence supports. The authors should either supply such a certificate or explicitly label the conjecture as heuristic and conditional on the mesh resolution.
- [§6, Figs. 7-8] The pair-only search for counterexamples to the Perfect-Mirsky conjecture is justified by the Boundary Conjecture (Conjecture 2.7), but Section 6 shows that for the standard representations of A_4 and A_5, pairs do not determine the boundary of the hull spectrum and triples produce eigenvalues outside the pair region. Since these groups are closely related to S_4 and S_5, this is a concrete warning that the boundary of DS_n might require convex combinations of more than two permutations for some n. Consequently, the computational evidence for DS_n = PM_n is conditional on the very conjecture under test. The authors should either provide a direct certified search over triples (and, where feasible, higher combinations) for n = 6,...,11, or qualify Conjecture 7.1 as contingent on the Boundary Conjecture.
minor comments (4)
- [Abstract / §1] The abstract states that PM_n = DS_n is known for n ≤ 4, while the introduction says 'for n < 4'; these statements should be made consistent (the cited result [12] proves the n = 4 case).
- [§4, Fig. 2] The text says the exceptional curve 'leaves PM 5 near the intersection of Π3 with Π4 and barely stays within PM 5 near the intersection of Π4 and Π5,' but the caption of Figure 2 says it 'leaves PM 5 above the intersection of Π3 and Π5'; the inconsistency should be resolved.
- [§4, Observation 4.1] Observation 4.1 is stated as a definitive claim ('There is only one inequivalent pair ... that generates an eigenvalue outside PM 5'), but it is a computational observation. The authors should explicitly state the mesh size and numerical precision used for the eigenpath scan, and ideally indicate whether the claim is certified or merely supported by sampling.
- [§7] The phrase 'we have spent much CPU time (> 2 years) on searching' is informal; a quantitative description of the computational resources (e.g., core-hours) would be more appropriate for a formal paper.
Circularity Check
Minor self-citation in the supporting evidence; the central computational derivation is self-contained and not circular.
-
self citation load bearing
[Section 6, paragraph beginning 'In [7]']
"In [7], the authors consider the so-called hull spectra of matrix groups, defined for a matrix group G as HS(G) := {λ : λ ∈ σ(A), A ∈ Co(G)} ... In all of the cases in which the groups under consideration were finite, the boundary of the hull spectrum was achieved by eigenvalues from convex combinations of pairs of group elements."
The cited general pattern is exactly the Boundary Conjecture (pairs determine the boundary), and reference [7] includes two authors of the present paper (Johnson and Lim). If this citation were the sole or load-bearing evidence, it would create a self-citation loop. However, the paper immediately acknowledges A4 and A5 as exceptions and relies primarily on new direct computations, so the self-citation is minor and non-load-bearing.
full rationale
The main computational derivation is self-contained: eigenpaths are computed directly for convex combinations of pairs of permutation matrices, and membership in PM_n is checked against an externally defined benchmark region. No parameter is fitted to force the target conclusion, and the mesh sizes are heuristically chosen rather than calibrated to produce a desired result. The n=5 exceptional curve is detected by the same method that finds no exceptions for n=6-11, giving the computation independent discriminating power. The secondary conjecture DS_n = PM_n for n=6,...,11 is explicitly conditional on the Boundary Conjecture for the exhaustiveness of pair-only scans; the paper states, 'If the Boundary Conjecture is true, there would be little doubt in our conjecture due to the fine mesh sizes to which we have computed pairs.' This is a transparent dependency rather than a hidden circular reduction, and the paper also reports triple computations that do not rely on the Boundary Conjecture. The absence of a rigorous mesh-size-to-gap bound is a correctness risk, not a circularity. The only noteworthy circularity-adjacent element is the citation to the authors' own prior work [7] as supporting evidence that pairs determine hull-spectrum boundaries. This is not load-bearing because the paper immediately reports counterexamples for A4 and A5 in the standard representation and bases its case on the new computations. Accordingly, the overall circularity score is 2: one minor self-citation, with the central claim retaining independent computational content.
Assumptions & free parameters
free parameters (1)
- mesh_size_m_for_pairs =
m=10000 for n=6-9; m=1000 for n=10; m=200 for n=11
assumptions (5)
- standard math Birkhoff's theorem: every doubly stochastic matrix is a convex combination of permutation matrices.
- standard math Mackey's formula for G-sets and orbit-stabilizer structure.
- domain assumption Correctness of GAP double-coset enumeration and centralizer routines.
- ad hoc to paper Boundary Conjecture, Conjecture 2.7.
- ad hoc to paper Sufficient mesh resolution.
Cite this review
Pith. "Pith review of The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach." pith.science (2026). https://pith.science/paper/DSHA7VOA
@misc{pith2026190803647,
author = {Pith},
title = {Pith review of: The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach},
year = {2026},
howpublished = {\url{https://pith.science/paper/DSHA7VOA}},
note = {Machine review of arXiv:1908.03647}
}
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 \leq 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$.
Figures
Figures from the paper (10 more)
Reference graph
Works this paper leans on
-
[1]
Birkhoff , Three Observations on Linear Algebra (Spanish) , Univ
G. Birkhoff , Three Observations on Linear Algebra (Spanish) , Univ. Nac. Tu- cum´ an. Revista A., 5 (1946), pp. 147–151
work page 1946
-
[2]
Bouc, Burnside rings , in Handbook of Algebra, vol
S. Bouc, Burnside rings , in Handbook of Algebra, vol. 2, North-Holland, Amster- dam, The Netherlands, 2000, pp. 739–804
work page 2000
-
[3]
N. A. Dmitriev and E. Dynkin , On characteristic roots of stochastic matrices , Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 10 (1946), pp. 167– 184
work page 1946
-
[4]
The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.10.2 , 2019
work page 2019
-
[5]
R. A. Horn and C. R. Johnson , Matrix Analysis, Cambridge University Press, New York, NY, second ed., 2013
work page 2013
-
[6]
H. Ito, A new statement about the theorem determining the region of eigenvalues of stochastic matrices, Linear Algebra and its Applications, 267 (1997), pp. 241 – 246
work page 1997
-
[7]
E. Jankowski, C. R. Johnson, and D. Lim , Spectra of convex hulls of matrix groups, Linear Algebra and its Applications, 593 (2020), pp. 74 – 89
work page 2020
-
[8]
C. R. Johnson, C. Mariju ´an, P. Paparella, and M. Pisonero , The NIEP , in Operator Theory, Operator Algebras, and Matrix Theory, Springer International Publishing, Cham, Switzerland, 2018, pp. 199–220
work page 2018
Show all 18 references
-
[9]
C. R. Johnson and P. Paparella , A matricial view of the Karpeleviˇ c theorem, Linear Algebra and its Applications, 520 (2017), pp. 1 – 15
2017
-
[10]
C. R. Johnson and J. Wilkes, The Doubly Stochastic Single Eigenvalue Problem: An Empirical Approach . https://scholarworks.wm.edu/honorstheses/1258/,
-
[11]
F. I. Karpelevich , On the characteristic roots of matrices with nonnegative el- ements, Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 15 (1951), pp. 361–383. 17
1951
-
[12]
Levick, R
J. Levick, R. Pereira, and D. W. Kribs , The four-dimensional Perfect-Mirsky Conjecture, in Proceedings of the American Mathematical Society, vol. 143, 2014, pp. 1951–1956
2014
-
[13]
Marcus and R
M. Marcus and R. Ree , Diagonals of doubly stochastic matrices , The Quarterly Journal of Mathematics, 10 (1959), pp. 296–302
1959
-
[14]
Mashreghi and R
J. Mashreghi and R. Rivard , On a conjecture about the eigenvalues of doubly stochastic matrices, Linear and Multilinear Algebra, 55 (2007), pp. 491–498
2007
-
[15]
https://oeis.org/ A110143, 2019
OEIS, The On-Line Encyclopedia of Integer Sequences . https://oeis.org/ A110143, 2019. [Online; accessed 8-August-2019]
2019
-
[16]
Perfect and L
H. Perfect and L. Mirsky , Spectral properties of doubly-stochastic matrices , Monatshefte f¨ ur Mathematik, 69 (1965), pp. 35–57
1965
-
[17]
Swift, The location of characteristic roots of stochastic matrices, Master’s thesis, McGill University, 1972
J. Swift, The location of characteristic roots of stochastic matrices, Master’s thesis, McGill University, 1972. Appendices A Supplementary Figures Figure 12: Inequivalent pairs for DS8. Inscribed circle omitted. 18 Figure 13: Inequivalent pairs for DS9. Inscribed circle omitted. 19
1972
-
[2018]
Honors Thesis at College of William and Mary
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.