Eigenvalue degeneracy in sparse random matrices

This paper demonstrates that sparse random matrices with discontinuous entries exhibit a positive probability of eigenvalue degeneracy due to the accumulation of eigenvalues at the origin, a phenomenon evaluated using Erdős-Rényi matching probability theory for random bipartite graphs.

The Gist

Imagine you have a giant, complex machine made of thousands of tiny gears. In the world of mathematics, this machine is a matrix (a grid of numbers), and the "gears" are its eigenvalues. These eigenvalues tell us how the machine vibrates, spins, or behaves.

Usually, mathematicians assume that in a random machine, every single gear is unique. No two gears are exactly the same size. This is the "common sense" of the field: if you build a machine with random parts, the odds of two parts being exactly identical are zero. It's like throwing a handful of sand into the air and expecting two grains to land in the exact same spot at the exact same time.

But what happens if the machine is "sparse"?

This paper by Masanari Shimura asks a fascinating question: What if our machine is mostly empty? Imagine a grid where most of the spots are empty (zero), and only a few spots have actual numbers. This is a sparse random matrix.

The author discovers that in these "sparse" machines, the old rules break. Instead of every gear being unique, there is a real, positive chance that two gears will be exactly the same size. In fact, they often get stuck at the very center of the machine (the number zero).

Here is the breakdown of the paper's journey, using some creative analogies:

1. The "Smooth" World vs. The "Broken" World

In the "smooth" world (where every number in the matrix is a continuous random variable, like picking a number from a smooth line), the chance of a "degeneracy" (two eigenvalues being identical) is zero. It's like trying to guess the exact second a specific raindrop hits the ground; the odds are infinitesimally small.

However, the paper looks at a "broken" or "discontinuous" world. Here, the matrix is built like a switchboard.

• The Switch: Imagine a light switch that is either ON (1) or OFF (0).
• The Bulb: If the switch is ON, a light bulb (a random number) turns on. If it's OFF, the bulb is dark (zero).

The paper studies what happens when we have a huge grid of these switches, but most of them are OFF. The matrix is "sparse" because it's mostly darkness.

2. The Perfect Match Game (The Graph Theory Analogy)

To solve this, the author uses a concept from graph theory called a Perfect Matching.

Imagine you have a dance hall with $N$ men on one side and $N$ women on the other.

• The Edges: A "connection" exists between a man and a woman if they know each other (or if the switch in our matrix is ON).
• The Goal: Can everyone find a unique partner so that no one is left standing alone? This is a "Perfect Matching."

The paper proves a brilliant link: The eigenvalues of the matrix will be unique (no degeneracy) if and only if the dance hall allows for a Perfect Matching.

If the dance hall is too empty (too many switches are OFF), people get left alone. In math terms, this "left alone" state corresponds to the eigenvalues crashing into zero and becoming identical.

3. The "Isolated Person" Problem

The key to the discovery is the isolated point.
In our dance hall analogy, an "isolated point" is a person who knows no one. They have no connections.

The author calculates the probability of these isolated people appearing in a sparse network.

• If the network is very dense (everyone knows everyone), no one is isolated, and the eigenvalues are unique.
• If the network is sparse (people barely know each other), isolated people start to appear.

The paper finds a specific "tipping point" (a mathematical threshold involving the number of people $N$ and the probability of connection $p$). Just above this tipping point, the number of isolated people follows a specific pattern (a Poisson distribution).

4. The Big Discovery: The "Zero" Crash

The most surprising result is that degeneracy happens because the eigenvalues pile up at zero.

Think of the eigenvalues as cars on a highway.

• In a normal, dense matrix, the cars are spread out evenly.
• In this sparse matrix, the "traffic jam" happens at the exit ramp (Zero).

Because the matrix is so full of zeros (the switches are mostly off), the "cars" (eigenvalues) get stuck at the exit. When two or more cars get stuck at the exact same spot, we have degeneracy.

The paper calculates exactly how likely this traffic jam is. It turns out that even as the matrix gets infinitely large, there is a positive, non-zero chance that the eigenvalues will degenerate. It's not a rare accident; it's a feature of the sparse system.

The Formula for the "Traffic Jam"

The paper gives a specific formula for the probability of this happening:
$$\text{Probability} = 1 - e^{-\lambda} - \lambda e^{-\lambda}$$
(Where $\lambda$ depends on how sparse the matrix is).

In plain English: This formula tells us the odds that the "dance hall" has enough isolated people to cause a crash in the machine's gears.

Summary

• Old Belief: Random matrices never have identical eigenvalues.
• New Discovery: If the matrix is sparse (mostly zeros) and the zeros are "hard" (discontinuous), identical eigenvalues do happen.
• Why? The zeros cause the eigenvalues to collapse into the center (zero), creating a pile-up.
• How? The author used the math of "perfect dance matches" to prove that if the network is too empty, the machine's gears will lock up.

This paper is like finding out that while a crowded party usually has everyone talking to someone different, a very quiet, sparse party often leaves people standing alone in the corner, and that "standing alone" changes the entire vibe of the room.

Technical Summary

1. Problem Statement

In classical random matrix theory (RMT), it is a standard assumption that eigenvalue degeneracy (multiple eigenvalues having the same value) occurs with probability zero. This assumption holds when matrix entries are drawn from independent, continuous probability distributions (e.g., Gaussian), as the set of matrices with degenerate eigenvalues has a lower dimension (codimension) than the space of all matrices.

However, this paper addresses a gap in the literature regarding sparse random matrices where the probability measure of the entries is discontinuous. Specifically, the paper investigates matrices where entries are zero with high probability (sparsity) and non-zero with a continuous distribution. The central question is: Does eigenvalue degeneracy occur with a non-zero probability in the limit of large matrix dimensions ($N \to \infty$) for such sparse models, and if so, what is the asymptotic probability?

2. Methodology

The author employs a multi-faceted approach combining linear algebra, graph theory, and asymptotic probability:

• Discriminant Analysis: The paper utilizes the discriminant of the characteristic polynomial. A matrix has degenerate eigenvalues if and only if its discriminant is zero. The author proves that for matrices depending analytically on continuous random variables, the probability of degeneracy is either 0 or 1, depending on whether any configuration of parameters yields distinct eigenvalues.
• Graph Theory Mapping: The core innovation is mapping the eigenvalue degeneracy problem to the perfect matching problem in bipartite graphs.
  • For an $N \times N$ matrix $A$ with non-zero entries only at positions defined by a set $\Lambda$, the existence of distinct eigenvalues is linked to the existence of a perfect matching in a corresponding bipartite graph $G=(V_R, V_C, E)$, where edges exist if $A_{j\ell} \neq 0$.
  • The paper establishes that if the bipartite graph has a perfect matching (or a perfect matching in a subgraph formed by removing one vertex), there exists a choice of non-zero values for the entries such that all eigenvalues are distinct.
• Erdős-Rényi Random Graph Theory: To evaluate the probability of these graph structures in the sparse limit, the paper relies on the asymptotic theory of random bipartite graphs developed by Erdős and Rényi. The sparsity is modeled by a Bernoulli variable $Y_{j\ell}$ with parameter $p(N)$, where $p(N) \approx \frac{\log N + c}{N}$.
• Asymptotic Evaluation: The author calculates the probability of the graph not having a perfect matching. It is shown that in the critical sparse regime, the primary obstruction to a perfect matching is the presence of isolated vertices (vertices with degree zero).

3. Key Contributions and Results

A. General Sparse Random Matrices (Asymmetric)

The paper analyzes $N \times N$ matrices $M = (Y_{j\ell}Z_{j\ell})$, where $Y_{j\ell} \sim \text{Bernoulli}(p)$ and $Z_{j\ell}$ are continuous random variables.

• Condition for Non-Degeneracy: The matrix has $N$ distinct eigenvalues with probability 1 (conditional on the sparsity pattern) if and only if the associated random bipartite graph satisfies Condition 4.1:
  1. The graph has a perfect matching, OR
  2. There exists a vertex $j$ such that the subgraph $G[N \setminus \{j\}]$ has a perfect matching.
• Asymptotic Probability: Using the Erdős-Rényi threshold for perfect matchings, the paper derives the asymptotic probability of degeneracy.
  • Let $p(N) = \frac{\log N + c}{N} + o(1/N)$.
  • Define $\lambda = 2e^{-c}$.
  • The probability that the matrix has distinct eigenvalues converges to:
    $$P(\text{distinct}) \to e^{-\lambda} + \lambda e^{-\lambda}$$
  • Consequently, the degeneracy probability is:
    $$P(\text{degenerate}) \to 1 - e^{-\lambda} - \lambda e^{-\lambda}$$
• Mechanism: The degeneracy arises because the sparsity causes eigenvalues to accumulate at the origin. If the graph has two or more isolated vertices, the matrix has at least two zero eigenvalues, leading to degeneracy.

B. Symmetric Sparse Random Matrices

The analysis is extended to symmetric matrices ($M_{j\ell} = M_{\ell j}$).

• Modified Graph Structure: The symmetry constraint implies that if $v_j^R$ is isolated, $v_j^C$ is also isolated. The problem reduces to counting isolated vertices in the underlying undirected graph structure.
• Asymptotic Probability:
  • Let $p(N) = \frac{\log N + c}{N}$ for off-diagonal entries and $q(N) \to q_\infty$ for diagonal entries.
  • Define $\mu = (1 - q_\infty)e^{-c}$.
  • The probability of having distinct eigenvalues converges to:
    $$P(\text{distinct}) \to e^{-\mu} + \mu e^{-\mu}$$
  • The degeneracy probability is $1 - e^{-\mu} - \mu e^{-\mu}$.

4. Significance and Implications

1. Positive Degeneracy Probability: The most significant finding is that unlike continuous random matrices (where degeneracy probability is 0), sparse random matrices with discontinuous entries exhibit a strictly positive probability of eigenvalue degeneracy in the thermodynamic limit.
2. Role of Sparsity: The paper demonstrates that sparsity is not just a structural feature but a fundamental driver of spectral degeneracy. The "accumulation of eigenvalues to the origin" is a direct consequence of the matrix entries being zero with high probability.
3. Graph-Theoretic Connection: The work provides a rigorous bridge between the spectral properties of random matrices and the combinatorial properties of random graphs (specifically perfect matchings and isolated vertices). It validates that the spectral behavior of sparse matrices is dominated by the "zero-structure" of the matrix.
4. Generalization: The results generalize previous work by Tao, Vu, and Luh, which focused on conditions where degeneracy probability vanishes. This paper identifies the specific regime (sparse, discontinuous) where degeneracy becomes a dominant feature.

Conclusion

Masanari Shimura's paper resolves the question of eigenvalue degeneracy in sparse random matrices by proving that discontinuity in the entry distribution (specifically the high probability of zero entries) leads to a non-zero asymptotic probability of degeneracy. The probability is explicitly calculated using the theory of random bipartite graphs, showing that degeneracy is primarily caused by the existence of multiple isolated vertices in the underlying graph, which forces multiple zero eigenvalues. This finding challenges the standard assumption of non-degeneracy in RMT when applied to sparse systems.