The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach

Amit Harlev, Charles R. Johnson, Derek LimExp. Math 2022 · OpenReview

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 commonly associated with this set. This paper uses a group-theoretic computational approach to explore the "doubly stochastic single eigenvalue problem." The authors provide strong evidence for a "Boundary Conjecture," suggesting that the edges of this eigenvalue region are defined by simple combinations of just two permutation matrices, and they identify a unique anomaly in the $n=5$ case.

Introduction

A matrix is defined as "doubly stochastic" if its entries are non-negative and every row and column sums to 1. These matrices are foundational in probability, combinatorics, and computer science, particularly in the study of Markov chains. Despite their importance, the set $DS_n$ of all possible complex eigenvalues for an $n \times n$ doubly stochastic matrix remains partially understood.

For $n \leq 4$, the region $DS_n$ matches the Perfect-Mirsky region ($PM_n$), which is the convex hull of roots of unity. However, for $n=5$, $DS_5$ is known to be larger than $PM_5$. This research investigates whether this "leakage" persists for larger $n$ and tests the Boundary Conjecture, which posits that the boundary of $DS_n$ is generated by convex combinations of at most two permutation matrices.

Methodology

The authors utilize Birkhoff’s Theorem, which states that any doubly stochastic matrix is a convex combination of permutation matrices. To find the boundary of $DS_n$, the study focuses on convex combinations of pairs $(P, Q)$ of permutations.

Given the factorial growth of the symmetric group $S_n$, a naive search is computationally impossible for larger $n$. The authors employ computational group theory to make the problem tractable:

  1. Canonical Cycle Forms: The search is reduced to pairs where one matrix is in a standard cycle form.
  2. Inequivalent Pairs: An equivalence relation based on uniform permutation similarity is defined. By using centralizers and double cosets, the authors identify a minimal set of "inequivalent pairs" representing all possible eigenvalue paths.
  3. Algorithm 1: Implemented in the GAP algebra system, this routine efficiently enumerates representative pairs.
Algorithm 1: Computing inequivalent pairs of permutations.

Computational Results

The "data" for this study consists of eigenvalues from millions of matrices across dimensions $n=2$ to $n=13$. The group-theoretic reduction provided a massive decrease in complexity. For instance, at $n=10$, the naive approach would require checking over 152 million pairs; the authors' method reduced this to approximately 1.9 million.

Comparison of the number of inequivalent pairs versus the naive search space.

Key findings include:

  • The $n=5$ Anomaly: The "leakage" outside $PM_5$ is caused by exactly one inequivalent pair of permutations (up to similarity). This suggests the $n=5$ case is a specific mathematical coincidence.
  • Boundary Conjecture Validation: Testing convex combinations of triples and quadruples of permutations did not push the eigenvalue boundary further than pairs did, providing strong empirical support for the conjecture.
  • New Conjecture (7.1): The authors conjecture that $DS_n = PM_n$ for $n \in \{6, 7, 8, 9, 10, 11\}$, implying the $n=5$ anomaly does not immediately recur.

Discussion and Conclusion

This computational study provides overwhelming evidence for the Boundary Conjecture for $n \leq 11$. After over two years of CPU time, no counterexamples were found, even with fine sampling intervals.

The primary limitation remains that these results are empirical rather than a formal proof. It is theoretically possible that counterexamples exist for much larger $n$ or within intervals smaller than the sampling mesh. Future work will focus on developing a formal proof for the Boundary Conjecture and investigating the algebraic properties that make the $n=5$ case unique.

Summary updated

Abstract

The problem of determining DSn, 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, PMn, is c...
BibTeX
@inproceedings{harlev2022doubly,
  author = {Amit Harlev and Charles R. Johnson and Derek Lim},
  title = {{The Doubly Stochastic Single Eigenvalue Problem: A Computational Approach}},
  booktitle = {Exp. Math},
  year = {2022},
  url = {https://openreview.net/forum?id=_Opspkxls7Y},
}

Loading related content...

Figure