On the condition number of the shifted real Ginibre ensemble

Giorgio Cipolloni, László Erdős, Dominik Schröder

Abstract

We derive an accurate lower tail estimate on the lowest singular value $\sigma_1(X-z)$ of a real Gaussian (Ginibre) random matrix $X$ shifted by a complex parameter $z$. Such shift effectively changes the upper tail behaviour of the condition number $\kappa(X-z)$ from the slower $\mathbf{P}(\kappa(X-z)\ge t)\lesssim 1/t$ decay typical for real Ginibre matrices to the faster $1/t^2$ decay seen for complex Ginibre matrices as long as $z$ is away from the real axis. This sharpens and resolves a recent conjecture in [arXiv:2005.08930] on the regularizing effect of the real Ginibre ensemble with a genuinely complex shift. As a consequence we obtain an improved upper bound on the eigenvalue condition numbers (known also as the eigenvector overlaps) for real Ginibre matrices. The main technical tool is a rigorous supersymmetric analysis from our earlier work [arXiv:1908.01653].

Introduction

In numerical linear algebra, the condition number $\kappa(X)$ is a vital metric that quantifies how much input errors, such as rounding errors, are amplified in the output. High condition numbers indicate "ill-conditioned" problems where results are inherently unreliable.

A well-known discrepancy exists in Random Matrix Theory (RMT): large matrices with independent real Gaussian entries (real Ginibre ensemble) are significantly more likely to be ill-conditioned than their complex counterparts. Specifically, the probability tail for real matrices decays as $1/t$, while for complex matrices, it decays much faster, as $1/t^2$. This paper investigates the shifted real Ginibre ensemble $(X - zI)$, demonstrating that shifting a real matrix by a complex number $z$ causes it to inherit the superior numerical stability of complex matrices.

Methods

The research employs a sophisticated blend of mathematical physics and probability theory:

  • Supersymmetric (SUSY) Analysis: Originating in theoretical physics, the SUSY method reduces high-dimensional integrals over $N \times N$ matrices into simpler 3-fold integrals, allowing for precise estimates of singular values.
  • Green Function Comparison (GFT): The authors use GFT to demonstrate that their bounds, while derived for Gaussian entries, hold more generally for matrices with other distributions (e.g., Bernoulli) that share the same first few moments.
  • Numerical Simulations: Theoretical proofs are validated via Monte Carlo simulations of 10,000 random matrices (size $100 \times 100$), plotting complementary cumulative distribution functions (CCDF) to visualize tail behavior.

Key Insights and Results

The $N^{-1/2}$ Threshold and Tail Transition

The study identifies a critical threshold: when the imaginary part of the shift $z$ is significantly larger than $N^{-1/2}$, the real matrix transitions from its native symmetry class to behave like a complex matrix. Theorem 2.1 provides a precise lower tail estimate for the smallest singular value $\sigma_1(X - z)$, including an exponential suppression factor $\exp(-\frac{1}{2}N\eta^2)$ (where $\eta = \Im z$) that captures this transition.

Figure 4: CCDF of the condition number showing the transition from $1/t$ decay (blue, slope $\approx -0.9$) to $1/t^2$ decay (red/orange, slope $\approx -1.8$) as the shift becomes complex.

As shown in the figure above, the probability $\mathbf{P}(\kappa(X - z) \ge t)$ transitions from the characteristic real Ginibre $\sim 1/t$ decay to the more desirable $\sim 1/t^2$ decay as the shift $z$ moves away from the real axis. This resolves a conjecture by Banks et al. (2020) by providing the sharpest possible bound and refining the necessary scaling.

Eigenvector Overlaps and Stability

The paper further links the matrix condition number to "eigenvector condition numbers" (overlaps). Complex shifts effectively prevent the "fat tails" of eigenvector instability that typically plague real matrices near the real axis. The authors derive an improved upper bound on eigenvalue condition numbers, showing they scale as $N^{3/2} \sqrt{\log N}$ in the worst case.

Figure 6: CCDF of eigenvector overlaps $O_{ii}/N$ demonstrating that complex shifts (blue/orange) lead to faster tail decay compared to real matrices near the real axis (green).

Conclusion and Future Work

This work confirms that a genuinely complex shift acts as a powerful regularizer for real Ginibre matrices. While the current results rely heavily on the Gaussian nature of entries for full SUSY precision, future work aims to extend these results to general distributions and close the gap between the theoretical $N^{3/2}$ bound and the empirically observed linear scaling of eigenvector condition numbers. Additionally, Conjecture 2.4 suggests this regularizing effect may hold for any deterministic matrix $A$ added to a real Ginibre matrix, provided $A$ is "sufficiently complex."

Summary updated

Abstract

We derive an accurate lower tail estimate on the lowest singular value $σ_1(X-z)$ of a real Gaussian (Ginibre) random matrix $X$ shifted by a complex parameter $z$. Such shift effectively changes the upper tail behaviour of the condition number $κ(X-z)$ from the slower $\mathbf{P}(κ(X-z)\ge t)\lesssim 1/t$ decay typical for real Ginibre matrices to the faster $1/t^2$ decay seen for complex Ginibre matrices as long as $z$ is away from the real axis. This sharpens and resolves a recent conjecture in [arXiv:2005.08930] on the regularizing effect of the real Ginibre ensemble with a genuinely complex shift. As a consequence we obtain an improved upper bound on the eigenvalue condition numbers (known also as the eigenvector overlaps) for real Ginibre matrices. The main technical tool is a rigorous supersymmetric analysis from our earlier work [arXiv:1908.01653].
BibTeX
@article{cipolloni2022condition,
  author = {Giorgio Cipolloni and László Erdős and Dominik Schröder},
  title = {{On the condition number of the shifted real Ginibre ensemble}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2022},
  doi = {10.1137/21m1424408},
}
Figure