Pith. sign in

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 →

arxiv 1908.03647 v2 pith:DSHA7VOA submitted 2019-08-09 math.SP

classification math.SP MSC 15-0415A1815A2915B51
keywords doublystochasticmatrixeigenvaluepermutationgrouprepresentationsingleproblemPerfect-MirskyregionBoundaryConjectureconvexcombination
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish the Boundary Conjecture: every complex number on the boundary of DS_n, the set of eigenvalues of n-by-n doubly stochastic matrices, is already an eigenvalue of a convex combination of at most two permutation matrices. If true, the hard task of characterizing all doubly stochastic eigenvalues reduces to studying line segments between pairs of permutation matrices. The authors support this conjecture with a computational method that cuts the number of permutation pairs to a tractable set and with searches for n up to 11. They further conjecture that DS_n equals the Perfect-Mirsky region PM_n for n = 6 through 11, and that the known n = 5 exception comes from a single inequivalent pair of permutations.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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)
  1. [§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.
  2. [§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)
  1. [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).
  2. [§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.
  3. [§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.
  4. [§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

1 steps flagged · score 2.0 of 10

Minor self-citation in the supporting evidence; the central computational derivation is self-contained and not circular.

  1. 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 1 free parameters · 5 assumptions · 0 invented entities

The paper's mathematical core rests on standard theorems (Birkhoff, Mackey, representation theory) and on tooling assumptions (GAP). The evidential claims additionally assume the Boundary Conjecture when pair-only searches are used to infer DS_n=PM_n, and assume that the chosen finite meshes are fine enough to detect all boundary excursions. There are no fitted constants or invented entities.

free parameters (1)
  • mesh_size_m_for_pairs = m=10000 for n=6-9; m=1000 for n=10; m=200 for n=11
    Chosen discretization of the convex coefficient t in [0,1]. The no-counterexample claims and all plots depend on these values, and no error bound is given.
assumptions (5)
  • standard math Birkhoff's theorem: every doubly stochastic matrix is a convex combination of permutation matrices.
    Invoked in Section 2 as Theorem 2.1 and used throughout to justify studying permutations rather than general doubly stochastic matrices.
  • standard math Mackey's formula for G-sets and orbit-stabilizer structure.
    Used in Section 3 to reduce pairs of permutations to inequivalent pairs via double cosets.
  • domain assumption Correctness of GAP double-coset enumeration and centralizer routines.
    Algorithm 1 relies on these routines; the paper cites GAP 4.10.2 but does not prove the enumeration.
  • ad hoc to paper Boundary Conjecture, Conjecture 2.7.
    Used to justify restricting high-n searches to pairs, and to give weight to Conjecture 7.1; it is the claim under test, not an established theorem.
  • ad hoc to paper Sufficient mesh resolution.
    Assumed in Section 5; the authors note finer meshes may be needed for larger n, so absence of counterexamples is evidence, not a proof.

how reviews work

0 comments
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 reproduced from arXiv: 1908.03647 by the authors.

Figure 1
Figure 1. Inequivalent pairs for DS5. The boundaries of Πk for k ≤ 5 are outlined in black. Eigenvalues of inequivalent pairs are in red. Only the upper half plane is shown due to the symmetry of DSn across the real line. pair class of the original counterexample gives an eigenpath that leaves PM5; in fact, all of the eigenpaths from other inequivalent pair classes stay well inside PM5. Lastly, since the exceptional curve goe… view at source ↗
Figure 2
Figure 2. Close-up of exceptional curve in DS5, along with other pair (1234) that comes close to leaving PM5, both in red. PM5 is in black as per usual. The exceptional curve leaves PM5 above the intersection of Π3 and Π5 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Eigenvalues of triples of permutations for [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Close-up of subset of DS5 generated by triples. Eigenvalues of triples are in blue while the exceptional curve is in red. Only those points outside of PM5 are plotted. No eigenvalues of triples extend beyond the exceptional curve that is generated by pairs. pair. As sh…
Figure 5
Figure 5. Figure 5: Inequivalent pairs for DS6. Πk for k ≤ 6 outlined in black [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Inequivalent pairs for DS7. Πk for k ≤ 7 outlined in black. 12 [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: Eigenvalues of convex combinations of pairs and triples of 4-by-4 even permu [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: Eigenvalues of convex combinations of pairs and triples of 5-by-5 even permu [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]
Figure 9
Figure 9. Figure 9: Zoomed in version of Figure 8 [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]
Figure 10
Figure 10. Figure 10: PM5 in outlined in black and K4 filled in blue. Only the subset of K4 that is outside of PM5 is displayed. See [17] for equations determining Kn for small n [PITH_FULL_IMAGE:figures/full_fig_p016_10.png]
Figure 11
Figure 11. Figure 11: PM6 in black and K5 in blue. Again, only the subset of K5 outside of PM6 is displayed. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 12
Figure 12. Figure 12: Inequivalent pairs for DS8. Inscribed circle omitted. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_12.png]
Figure 13
Figure 13. Figure 13: Inequivalent pairs for DS9. Inscribed circle omitted. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_13.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [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

  2. [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

  3. [3]

    N. A. Dmitriev and E. Dynkin , On characteristic roots of stochastic matrices , Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 10 (1946), pp. 167– 184

  4. [4]

    The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.10.2 , 2019

  5. [5]

    R. A. Horn and C. R. Johnson , Matrix Analysis, Cambridge University Press, New York, NY, second ed., 2013

  6. [6]

    Ito, A new statement about the theorem determining the region of eigenvalues of stochastic matrices, Linear Algebra and its Applications, 267 (1997), pp

    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

  7. [7]

    Jankowski, C

    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

  8. [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

Show all 18 references
  1. [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

  2. [10]

    C. R. Johnson and J. Wilkes, The Doubly Stochastic Single Eigenvalue Problem: An Empirical Approach . https://scholarworks.wm.edu/honorstheses/1258/,

  3. [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

  4. [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

  5. [13]

    Marcus and R

    M. Marcus and R. Ree , Diagonals of doubly stochastic matrices , The Quarterly Journal of Mathematics, 10 (1959), pp. 296–302

  6. [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

  7. [15]

    https://oeis.org/ A110143, 2019

    OEIS, The On-Line Encyclopedia of Integer Sequences . https://oeis.org/ A110143, 2019. [Online; accessed 8-August-2019]

  8. [16]

    Perfect and L

    H. Perfect and L. Mirsky , Spectral properties of doubly-stochastic matrices , Monatshefte f¨ ur Mathematik, 69 (1965), pp. 35–57

  9. [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

  10. [2018]

    Honors Thesis at College of William and Mary

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.