Gaussian Regularization of the Pseudospectrum and Davies' Conjecture
Jess Banks Archit Kulkarni Satyaki Mukherjee Nikhil Srivastava

Modeling dark sector in Horndeski gravity at first-order formalism
    F. F. Santos ^1, R.M.P. Neves^1 and F. A. Brito^1,2
    December 30, 2023
==================================================================

 
	A matrix A∈^n× n is diagonalizable if it has a basis of linearly independent eigenvectors. 
	Since the set of nondiagonalizable matrices has measure zero, every A∈^n× n is the limit of diagonalizable matrices. 
	We prove a quantitative version of this fact conjectured by E.B. Davies: for each δ∈ (0,1), every matrix A∈^n× n is at least δA-close to one whose eigenvectors have condition number at worst c_n/δ, for some c_n depending only on n. We further show that the dependence on δ cannot
	be improved to 1/δ^p for any constant p<1. 
	
	Our proof uses tools from random matrix theory to show that the pseudospectrum of A can be regularized with the addition of a complex Gaussian perturbation.  Along the way, we explain how a variant of a theorem of Śniady implies a conjecture of Sankar, Spielman and Teng on the optimal constant for smoothed analysis of condition numbers.
	
	Keywords: Numerical Analysis,  Non-Hermitian Random Matrix Theory, Ginibre Ensemble, Smoothed Analysis, Matrix Analysis.
 




§ INTRODUCTION

A matrix A∈^n× n is diagonalizable if it can be written as
A = VDV^-1,
where D is diagonal and V is a matrix  consisting of linearly independent eigenvectors of A. 
Further, A is normal if and only if V^-1=V^*, or in other words if the eigenvectors can be chosen to be orthogonal.
A fundamental quantity capturing the nonnormality of a matrix is the eigenvector condition number

    κ_V(A) ≜inf_V:A=VDV^-1VV^-1,

which ranges between 1 and ∞ when A is normal and nondiagonalizable respectively, where ·  denotes the operator norm. 
Matrices with small κ_V enjoy many
of the desirable properties of normal matrices, such as stability of the spectrum under small perturbations (this is the content of the Bauer-Fike theorem <cit.>).
In this paper we study the following question posed by E. B. Davies in <cit.>:


	How well can an arbitrary matrix be approximated by one with a small eigenvector condition number?


Our main theorem is as follows.

 
	Suppose A∈^n× n and δ∈ (0,1). Then there is a matrix E∈^n× n such that E≤δA and
	
    κ_V(A+E)≤ 4n^3/2(1+1/δ).



In other words, every matrix is at most inverse polynomially close to a matrix whose eigenvectors have condition number at most polynomial in the dimension. The previously best known general bound in such a result was <cit.>:

    κ_V(A+E)≤(n/δ)^(n-1)/2,

so our theorem constitutes an exponential improvement in the dependence on both δ and n. We show in Proposition <ref> that the
1/δ-dependence in Theorem
<ref> cannot be improved beyond 1/δ^1-1/n, so our bound is essentially optimal in δ for large n.



 §.§ Davies' Conjecture

Theorem <ref> implies a positive resolution to a conjecture of Davies <cit.>.
  For every positive integer n there is a constant c_n such that for every A∈^n× n with A≤ 1 and ϵ∈ (0, 1):

    inf_E∈^n× n(κ_V(A+E)ϵ + E) ≤ c_n√(ϵ).

	 Given ϵ>0,
	set δ = d_n √() for some d_n > 0 and apply Theorem <ref>.  This yields c_n = 4n^3/2 + 4n^3/2/d_n + d_n.  This is minimized at d_n = 2n^3/4, which yields c_n = 4n^3/2 + 4n^3/4≤ 8n^3/2.
	

The phrasing of Conjecture <ref> is motivated by a particular application in numerical analysis. 
Suppose one wants to evaluate analytic functions f(A) of a given matrix A, which may be nonnormal. 
If A is diagonalizable, one can use the formula f(A)=Vf(D)V^-1, where f(D) means the function is applied to the scalar diagonal entries of D. 
However, this may be numerically infeasible if κ_V(A) is very large: if all computations are carried to precision ϵ, the result may be off by an error of κ_V(A)ϵ.
Davies' idea was to replace A by a perturbation A+E with a much smaller κ_V(A+E), and compute f(A+E) instead. In <cit.>, he showed that the net error incurred by this scheme for a given ϵ>0 and sufficiently regular f is controlled by:

    κ_V(A+E)ϵ + E,

which is the quantity appearing in (<ref>). The key desirable feature of (<ref>) is the dimension-independent fractional power of ϵ on the right-hand side, which shows that the total error scales slowly. 

Davies proved his conjecture in the special case of upper triangular Toeplitz matrices, in dimension n= 3 with the constant c_n = 2, as well as in the general case with the weaker dimension-dependent and nonconstructive bound (n+1)ϵ^2/(n+1). This last result corresponds to (<ref>) above.  
He also speculated that a random
regularizing perturbation E suffices to prove Conjecture <ref>,
and presented empirical evidence to that effect.  Our proof of Theorem
<ref> below indeed follows this strategy.



 §.§ Gaussian Regularization

Theorem <ref> follows from a probabilistic result concerning complex Gaussian perturbations of a given matrix A.
To state our result, we recall two standard notions.

 
	A complex Ginibre matrix is an n× n random matrix G_n=(g_ij) with i.i.d complex Gaussian entries g_ij∼ N(0,1_/n), by which we mean g_ij=0 and |g_ij|^2=1/n. Equivalently the real and imaginary parts of each g_ij are independent N(0,1/2n) random variables. 


 
	Let M∈^n× n have distinct eigenvalues λ_1,…,λ_n, and spectral expansion
	
    M = ∑_i=1^n λ_i v_i w_i^∗ = VDV^-1,

	where the right and left eigenvectors v_i and w_i^∗ are the columns and rows of V and V^-1, respectively, normalized so that w_i^*v_i=1. 
	The eigenvalue condition number of λ_i is defined as:
	
    κ(λ_i) ≜v_i w_i^∗ =v_iw_i.


The κ(λ_i)'s are called condition numbers because they determine the sensitivity of the λ_i to perturbations of the matrix.
We show that adding a small Ginibre perturbation regularizes the eigenvalue condition numbers of any matrix in the following averaged sense.
  
	Suppose A∈^n× n with A≤ 1 and δ∈ (0,1). Let G_n be a complex Ginibre matrix, and let λ_1,…,λ_n∈ be the (random) eigenvalues of A+δ G_n. Then for every measurable open set B⊂,
	
    ∑_λ_i ∈ Bκ(λ_i)^2 ≤n^2/πδ^2(B).


Note that the κ(λ_i) appearing above are well-defined because A+δ G_n has distinct eigenvalues with probability one. 



 §.§ Related Work
 
Random Matrix Theory. There have been numerous studies of the eigenvalue condition numbers κ(λ_i)^2, sometimes called eigenvector overlaps in the random matrix theory and mathematical physics literature, for non-Hermitian random matrix models of type A+δ G_n.
In the centered case A=0 and δ=1 of a standard complex Ginibre matrix, 
the seminal work of Chalker and Mehlig <cit.> calculated the large-n limit of
the conditional expectations 
    [κ(λ)^2|
    λ=z]n→∞∼ n(1-|z|^2),
 whenever |z|<1.
Recent works by Bourgade and Dubach <cit.> and Fyodorov <cit.>
improved on this substantially by giving exact nonasymptotic formulas for the distribution of κ(λ)^2 conditional on the location of the eigenvalue λ, as well as
concise descriptions of the scaling limits for these formulas.



The paper <cit.> proved (in the more general setup of invariant ensembles) that the angles between the right
eigenvectors (v_i^*v_j)/v_iv_j have subgaussian tails, which has some bearing on κ_V (for instance, a small angle between unit eigenvectors causes ‖ V^-1‖ and therefore κ_V to blow up.)

In the non-centered case, Davies and Hager <cit.>
showed that if A is a Jordan block and δ=n^-α for some
appropriate α, then almost all of the eigenvalues of A+δ G_n lie
near a circle of radius δ^1/n with probability 1-o_n(1).  Basak,
Paquette, and Zeitouni <cit.> showed
that for a sequence of banded Toeplitz matrices A_n with a finite symbol, the
spectral measures of A_n+n^-αG_n converge weakly in probability, as n→∞, to a
predictable density determined by the symbol. Both of the above results were
recently and substantially improved by Sjöstrand and Vogel
<cit.> who proved that for any
Toeplitz A, almost all of the eigenvalues of A+n^-αG_n are close to the
symbol curve of A with exponentially good probability in n. Note that none of the results
mentioned in this paragraph explicitly discuss the κ(λ_i); however, they do deal qualitatively
with related phenomena surrounding spectral instability of non-Hermitian matrices.

The idea of managing spectral instability by adding a random perturbation can
be traced back to the influential papers of Haagerup and Larsen
<cit.> and Śniady <cit.> (see also
<cit.>), who used it to study
convergence of the eigenvalues of certain non-Hermitian random matrices to a limiting Brown
measure, in the context of free probability theory.

There are three notable differences between Theorem <ref> and the results mentioned above:

	
  * Our result is much coarser, and only guarantees an upper bound on the κ(λ_i)^2, 
		rather than a precise description of any distribution, limiting or not.
	
  * It applies to any A∈^n× n and δ∈ (0,1).
	
  * It is completely nonasymptotic and does not require n→∞ or even sufficiently large n.


Numerical Analysis. In the numerical linear algebra literature, several works have analyzed the condition numbers of Gaussian matrices (notably the seminal results of Demmel <cit.> and Edelman <cit.>) as well as perturbations of arbitrary matrices by Gaussian matrices (beginning with <cit.>) in the nonasymptotic regime. In contrast, this paper studies the condition numbers of the eigenvectors of such matrices, rather than of the matrices themselves.

The idea of approximating matrix functions by adding a regularizing perturbation was introduced in <cit.> and has since appeared in several works regarding numerical computation of the matrix logarithm, sine, cosine, and related functions <cit.>.



 §.§ Techniques and Organization

The proofs of Theorems <ref> and <ref> are quite simple and rely on an interplay between various notions of spectral stability.  In addition to κ_V and the κ(λ_i), we
will heavily use the notion of the ϵ-pseudospectrum of a matrix M, defined for ϵ>0 as:

    Λ_ϵ(M) 
    	   ≜{z ∈ℂ : z ∈Λ(M + E)  for some E < ϵ}
       = {z ∈ℂ : (zI - M)^-1 > 1/ϵ}
       = {z ∈ℂ :  σ_n(zI-M)< ϵ},

where Λ(M) denotes the spectrum M.
For a proof of the equivalence of these three sets and a comprehensive treatment of pseudospectra, see the beautiful book
by Trefethen and Embree <cit.>.
Note that for a normal matrix, we have 

    Λ_ϵ(M) = Λ(M)+ ⋃_iD(λ_i, ϵ),


whereas for a nonnormal matrix such as a Jordan block, Λ_ϵ can be much larger.  Figure 1 illustrates the regularizing effect of a small complex Gaussian perturbation on the pseudospectrum of a nondiagonalizable matrix, which is the key phenomenon underlying our results. 




















 To analyze this phenomenon, we first collect some tools from random matrix theory in Section <ref>, along the way proving a conjecture of Sankar, Spielman, and Teng <cit.> regarding the optimal constant in their smoothed analysis of condition numbers of matrices under real Gaussian perturbations in Section <ref>. Section <ref> contains the proofs of our main results, Theorems <ref> and <ref>.
In Section <ref>, we prove optimality of the 1/δ-dependence in Theorem
<ref> as discussed above, and show that Theorem <ref> is sharp up to a small constant factor. We conclude with a discussion of some open problems in Section <ref>.



  §.§.§ Notation
 We denote the singular values of an n× n
matrix by σ_1(M)≥…≥σ_n(M), its operator and Frobenius
(Hilbert-Schmidt) norms by M and M_F, and its condition number by
κ(M)≜σ_1(M)/σ_n(M). Open disks in the complex plane will be written as D(z_0,r)≜{z∈: |z-z_0|<r}.
We will often write G for a standard complex Gaussian matrix with N(0,1_) entries, and G_n = n^-1/2G for a (normalized) Ginibre matrix.





§ TOOLS FROM RANDOM MATRIX THEORY




 §.§ Nonasymptotic Extreme Singular Value Estimates


Let us record some standard non-asymptotic estimates for the extreme singular values of complex Ginibre matrices. The lower tail behavior of the smallest singular value of a Ginibre matrix was worked out by Edelman in the unnormalized scaling of i.i.d. N(0,1_) entries <cit.>, and in our setting it translates to:

  
	 For a complex Ginibre matrix G_n, 
	
    [σ_n(G_n) < ϵ] = 1 - e^-ϵ^2n^2≤ϵ^2 n^2.

    

We will also require a cruder tail estimate on the largest singular value. We believe the lemma holds with a constant 2 instead of 2√(2), but did not find a reference to a nonasymptotic result to this effect; since the difference is not very consequential in this context, we reduce to the real case.
  For a complex Ginibre matrix G_n,
	
    [σ_1(G_n)> 2√(2)+t]≤ 2exp(-nt^2).



	We can write G_n = 1/√(2)(X+iY) where X and Y are independent with i.i.d. real N(0,1/n) entries.
	It is well-known (e.g. <cit.>) that:
	
    σ_1(G_n) ≤2/√(2)X≤ 2√(2).

	Lipschitz concentration of functions of real Gaussian random variables yields the result.




 §.§ Śniady's Comparison Theorem

To bound the least singular value of noncentered Gaussian matrices, we will lean on a remarkable theorem of Śniady <cit.>.
  
	Let A_1 and A_2 be n × n complex matrices such that σ_i(A_1) ≤σ_i(A_2) for all 1 ≤ i ≤ n.  Assume further that σ_i(A_1) σ_j(A_1) and σ_i(A_2) σ_j(A_2) for all i  j.  Then for every t ≥ 0, there exists a joint distribution on pairs of n × n complex matrices (G_1, G_2) such that 
	
    	
  * the marginals G_1 and G_2 are distributed as (normalized) complex Ginibre matrices G_n, and
    	
  * almost surely σ_i(A_1 + √(t) G_1) ≤σ_i(A_2 + √(t) G_2) for every i.
 	 

We will briefly sketch the proof of this theorem for the reader's benefit, since it is quite beautiful and we will need to perform a slight modification to prove the conjecture of Sankar-Spielman-Teng in the next subsection.

	The key insight of the proof is that it is possible to couple the distributions of G_1 and G_2 through their singular values. To do so, one first derives a stochastic differential equation satisfied by the singular values s_1,...,s_n of a matrix Brownian motion (i.e., a matrix whose entries are independent complex Brownian motions):
	
    ds_i = 1/√(2n)dB_i + dt/2s_i(1 - 1/2n + ∑_j  is_i^2 + s_j^2/n(s_i^2 - s_j^2)),

	where the B_i are independent standard real Brownian motions.
	Next, one uses a single n-tuple of real Brownian motions B_1,...,B_n to drive two processes (s_1^(1), …, s_n^(1)) and (s_1^(2), …, s_n^(2)) according to (<ref>), with initial conditions s_i^(1)(0) = σ_i(A_1) and s_i^(2)(0) = σ_i(A_2) for all i. (To do this rigorously, one needs existence and uniqueness of strong solutions to the above SDE; this is shown in <cit.> under the hypothesis s_i(0)  s_j(0) for all i  j.)

	Things have been arranged so that the joint distribution of (s_1^(j), …, s_n^(j)) at time t matches the joint distribution of the singular values of A_j + √(t) G_j for each j = 1,2. One can then sample unitaries U_j and V_j from the distribution arising from the singular value decomposition A_j+√(t)G_j = U_jD_jV_j^*, conditioned on D_j = diag(s_1^(j), …, s_n^(j)). Thus each G_j is separately Ginibre-distributed. However, A_1 + √(t)G_1 and A_2 + √(t)G_2 are coupled through the shared randomness driving the evolution of their singular values. In particular, since the same B_i were used for both processes, from (<ref>) one can verify that the n differences s_i^(2) - s_i^(1) are C^1 in t.  By taking derivatives, one can then show the desired monotonicity property: if s_i^(2) - s_i^(1)≥ 0 holds for all i at t=0, it must hold for all t ≥ 0.




 §.§ Sankar-Spielman-Teng Conjecture

The proof technique of Śniady can be adapted to prove a counterpart of Theorem <ref> for real Ginibre perturbations (by this we mean matrices with i.i.d. real N(0,1/n) entries).  Because a rigorous proof requires some stochastic analysis, we defer the proof and discussion of the following theorem to the appendix.

	Let A_1 and A_2 be n × n real matrices such that σ_i(A_1) ≤σ_i(A_2) for all 1 ≤ i ≤ n.  Assume further that σ_i(A_1) σ_j(A_1) and σ_i(A_2) σ_j(A_2) for all i  j.  Then for every t ≥ 0, there exists a joint distribution on pairs of real  n × n matrices (G_1, G_2) such that 
	
    	
  * the marginals G_1 and G_2 are distributed as real Ginibre matrices (with i.i.d. N(0,1/n) entries), and
    	
  * almost surely σ_i(A_1 + √(t) G_1) ≤σ_i(A_2 + √(t) G_2) for every i.
 	 


This resolves Conjecture 1 in <cit.>, which we restate below as a proposition:
 
	Let G be an n × n matrix with i.i.d. real N(0,1) entries, and A be any n × n matrix with real entries. Then 
	
    [σ_n(A + G) < ] ≤√(n).



The case A=0 is a result of Edelman <cit.>.  The proposition for general A would then follow from Theorem <ref> with A_1 = 0 and A_2 = A if not for the hypothesis σ_i(A_1) σ_j(A_1) and σ_i(A_2) σ_j(A_2) for all i  j.  So we approach 0 and A by matrices satisfying this hypothesis, apply Theorem <ref>, and take limits, using the continuous mapping theorem and continuity of σ_n(·).





§ PROOF OF THEOREMS <REF> AND <REF>

We begin with a lemma relating the eigenvector and eigenvalue condition numbers. For related results, including an extension of this lemma to the more general context of block diagonalization, see the thesis of Demmel <cit.>.
 
Let M be an n × n matrix with distinct eigenvalues, and let V be the matrix whose columns are the eigenvectors of M normalized to have unit norm.  Then

    κ(V)≤√(n ∑_i=1^n κ(λ_i)^2).
 


Note that the left eigenvectors w_i are the rows of V^-1.  Then ‖ V ‖_F^2 = n and ‖ V^-1‖_F^2 = ∑_i=1^n ‖ w_i‖^2 = ∑_i=1^n κ(λ_i)^2, so 

    κ(V)= ‖ V ‖‖ V^-1‖≤‖ V ‖_F ‖ V^-1‖_F =√(n ∑_i=1^n κ(λ_i)^2).



We can now prove the main theorem.
 
Let λ_1,…,λ_n be the eigenvalues of the random matrix A+δ G_n, and t > 2 √(2) and  s > 1 be parameters to be optimized later.  Davies' original bound (<ref>) implies our bound for n ≤ 3, so assume n ≥ 4.
 Then Lemma <ref> tells us that 
	
    [‖δ G_n ‖≥ tδ] ≤ 2 e^-4 (t - 2 √(2))^2.

Letting B=D(0,A+tδ), we have
	
    [∑_λ_i∈ Bκ(λ_i)^2 ≠∑_i≤ nκ(λ_i)^2] ≤[δ G_n≥ tδ]≤ 2 e^-4 (t - 2 √(2))^2

	since max_i≤ n |λ_i|≤A+δ G_n.
	On the other hand, by Theorem <ref> applied to B and Markov's inequality:
	
    [∑_λ_i∈ Bκ(λ_i)^2 ≥ s n^2(B)/δ^2π]≤1/s.

By the union bound, if we choose s and t such that

    2 e^-4 (t - 2 √(2))^2 + 1/s < 1
 then there exists a choice of G_n such that neither of the events (<ref>), (<ref>) occurs.
	Letting E=δ G_n for this choice, we have
	
    ∑_i=1^n κ(λ_i)^2 = ∑_i∈ Bκ(λ_i)^2 ≤ sn^2(B)/πδ^2.

	Taking a square root and applying Lemma <ref>, we have
	
    κ_V(A+E) ≤√(s)n^3/2/δ(A+tδ) ≤√(s)n^3/2A/δ + t √(s)n^3/2.

	Because E≤ tδ and not δ, replacing δ by δ/t yields the bound
	
    κ_V(A+E)≤t √(s) n^3/2A/δ+t √(s) n^3/2.

	
	To get the best bound, we must minimize t √(s) subject to the constraints (<ref>), t > 2 √(2) and s > 1.  Solving for s this becomes a univariate optimization problem, and one can check numerically that the optimum is achieved at t ≈ 3.7487 and t√(s)≈ 3.8822 < 4, as advertised.
 

We begin the proof of Theorem <ref> by relating the eigenvalue condition numbers of a matrix to the rate at which its pseudospectrum Λ_ϵ shrinks as a function of the
parameter ϵ>0.  The following proposition is not new; the proof
essentially appears for example in Section 3.6 of
<cit.>, but we include it for completeness since it is
critical to our argument.
 
    Let M be an n × n matrix with n distinct eigenvalues λ_1, …, λ_n and let B⊂ be a measurable open set.  Then
    
    lim_→ 0(Λ_(M)∩ B)/^2 = π∑_λ_i∈ B^n κ(λ_i)^2.
 
 


	Write the spectral decomposition 
	
    (zI-M)^-1 = ∑_i=1^n v_i w_i^*/z - λ_i,

	where the v_i and w_i^∗ are right and left eigenvectors of M,
	respectively. Since the λ_i are distinct, we may choose 
	ϵ_0 > 0 sufficiently small to guarantee that there exists a constant C>0 satisfying (1) the disks D(λ_i,ϵ_0) are disjoint; (2) for every λ_i∈ B the disk D(λ_i,ϵ_0) is contained in B; and (3) whenever z∈ D(λ_i,ϵ_0) for some i,
	
    ‖ (zI-M)^-1‖≥‖ v_i w_i^* ‖/|z-λ_i| - C  = κ(λ_i)/|z - λ_i| - C.

	Using the definition of the -pseudospectrum in (<ref>),



	we rearrange (<ref>) to obtain
	
    Λ_(M)∩ B⊃{ z : |z - λ_i| ≤min{ϵ_0, κ(λ_i) /1 +  C}, for some λ_i∈ B}.

	Thus, taking  small enough, we have
	
    lim inf_→ 0(Λ_(M)∩ B)/^2≥π∑_i=1^nκ(λ_i)^2.
 

    For the opposite inequality, Theorem 52.1 of <cit.> states that the -pseudospectrum is contained in disks around the eigenvalues λ_i of radii κ(λ_i) + O(^2). Choosing ϵ small enough so that for λ_i∈ B these disks are entirely contained in B:
    
    (Λ_∩ B)    ≤∑_λ_i∈ Bπ (κ(λ_i) + O(^2))^2 
    
    	    ⇒lim sup_→ 0(Λ_∩ B)/^2≤∑_λ_i∈ Bπκ(λ_i)^2.



Next, we show that for fixed ϵ>0, any particular point z∈ is
unlikely to be in Λ_ϵ(A+δ G_n). This is based on the
following singular value estimate, which generalizes Theorem <ref>.

    Let M be an n× n matrix with complex entries, and G be drawn from the Ginibre ensemble. Then for all δ>0 and ϵ>0
    
    [σ_n(M + δ G_n) < ϵ] ≤ n^2 ϵ^2/δ^2.



	Repeat the proof of Proposition <ref> using instead Theorems <ref> and <ref>. 









  
	If one is willing to lose a small constant factor in the bound, Lemma <ref> has an elementary geometric proof (which avoids stochastic calculus), essentially identical to the proof of Sankar-Spielman-Teng <cit.> in the case of real Ginibre perturbations. Note however that it is crucial to use a complex Gaussian for our purposes. A real Gaussian would yield a small ball estimate of order ϵ (see Proposition <ref>) rather than ϵ^2, which is not good enough to take the limit below.


	For every z∈ we have the upper bound
	
    [z ∈Λ_ϵ(A + δ G_n)] =  [σ_n(zI-(A+δ G_n))<ϵ]  ≤ n^2 ^2/δ^2,

		by applying Lemma <ref> to M=zI-A and noting that G and -G have the same distribution.

	Fix a measurable open set B⊂. Then
	
    (Λ_ϵ(A + δ G_n)∩ B)    = ∫_B 1_{z ∈Λ_ϵ(A + δ G_n)}  dz 
       = ∫_B {z ∈Λ_ϵ(A + δ G_n)} dz       by Fubini
       ≤∫_B n^2^2/δ^2 dz       by (<ref>)
       = n^2^2/δ^2(B)

	where the integrals are with respect to Lebesgue measure on . 
		



	Finally, taking a limit as ϵ→ 0 yields the desired bound:
	
    ∑_λ_i∈ Bκ(λ_i^2) 
    		   = lim inf_ϵ→ 0(Λ_ϵ(A + δ G_n)∩ B)/πϵ^2      by Lemma <ref>
    
    		   ≤lim inf_ϵ→ 0(Λ_ϵ(A + δ G_n)∩ B)/πϵ^2      by Fatou's Lemma
       ≤n^2(B)/πδ^2      by (<ref>).







§ OPTIMALITY OF THE BOUNDS

We first show that Theorem <ref> has essentially the optimal dependence on δ for n large.  The  example  which  requires  this dependence is simply a Jordan block J, for which Davies <cit.> established the upper bound κ_V(J+δ E) ≤ 2/δ^1-1/n, for some E with ||E|| < 1.




 
	Fix n > 0 and let J ∈ℂ^n × n be the upper triangular Jordan block with ones on the superdiagonal and zeros everywhere else. Then there exist c_n > 0 and δ_n>0 such that for all E ∈ℂ^n × n with ‖ E ‖≤ 1 and all δ < δ_n, we have 
    κ_V(J + δ E) ≥c_n/δ^1 - 1/n.












	As a warm-up, we'll need the following bound on the pseudospectrum of J. Let λ be an eigenvalue of J + δ E, with v its associated right eigenvector; then (J + δ E)^nv = λ^n v and, accordingly, |λ|^n ≤(J + δ E)^n. Expanding, using nilpotence of J, J = 1, and submultiplicativity of the operator norm, we get
	
    |λ|^n ≤(J + δ E)^n≤ (1 + δ)^n - 1 = O(δ)

	where the big-O refers to the limit δ→ 0 (recall n is fixed).

	Writing J + δ E = V^-1DV, we want to lower bound the condition number of V. As above, let λ be an eigenvalue of J + δ E, now writing w^∗ and v for its left and right eigenvectors. We'll use the lower bound
	
    κ(V) = V^-1V≥w^∗v/|w^∗ v|=κ(λ).

	Since the formula above is agnostic to the scaling of the left and right eigenvectors, we'll assume that both have unit length and show that |w^∗ v| is small.

	Let 0 ≤ k ≤ n. Then ‖ (J + δ E)^k v ‖ = |λ|^k, and analogously to (<ref>), 
	
    (J + δ E)^k - J^k≤ (1 + δ)^k - 1 = O(δ).

	Since J acts on the left as a left shift,
	
    ( ∑_i=k+1^n |v_i|^2 )^1/2   = ‖ J^k v ‖
       ≤‖ (J+δ E)^k v‖  + ‖ (J^k - (J+δ E)^k)v‖
       ≤ |λ|^k + O(δ) 
       = O(δ^k/n),

	where the final line follows from (<ref>). Similarly,
	
    (∑_i=1^n-k |w_i|^2 )^1/2 = ‖ w^∗ J^k ‖ = O(δ^k/n).

	Finally, we have κ(V)^-1 = |w^* v| ≤∑_j=1^n |w_j| |v_j|, which in turn is at most
	
    ∑_j=1^n ( ∑_i=1^j |w_i|^2 )^1/2( ∑_i=j^n |v_i|^2 )^1/2 = O( δ^(n-j)/nδ^(j-1)/n) = O(δ^1 - 1/n).





We end by showing that the dependence on n in Theorem <ref> cannot be improved. 

There exists c > 0 such that for all n, 

    ∑_i∈[n]κ^2(λ_i(G_n)) ≥ cn^2.




Bourgade and Dubach <cit.> show that eigenvalue condition numbers in the bulk of the spectrum of complex Ginibre matrices are of order √(n).  Precisely,
	
    lim_n →∞ [ κ(λ_i)^2 | λ_i = z ] /n = 1 - |z|^2

	uniformly for (say) z ∈ D(0,r) for any r< 1.  The classical circular law for the limiting spectral distribution of Ginibre matrices ensures that 
	
    lim_n →∞ | Λ(G_n) ∩ D(0,r)|/n = vol(D(0, r))/vol(D(0, 1)) = r^2 .
  Thus,
	
    lim inf_n →∞∑_i∈[n]κ(λ_i(G_n))^2/n^2≥ r^2 (1 - r^2) > 0.
























































§ CONCLUSION AND DISCUSSION

A key theme in our work is the interplay between the related notions of eigenvector condition number κ_V, eigenvalue condition number κ(λ_i) and pseudospectrum Λ_. Equally important is the fact that global objects such as κ_V and Λ_ can be controlled by local quantities, specifically the least singular values of shifts σ_n(zI - M) for each z ∈ℂ. The proof also heavily exploits the left and right unitary invariance of the Ginibre ensemble (via Theorem <ref>, due to Śniady) as well as anticoncentration of the complex Gaussian.

One natural question is whether similar results hold if one replaces Gaussian perturbations with a different class of random perturbations G'.  To apply the approach in this paper, the key difficulty would be obtaining suitable bounds for the least singular value of z - A - δ G'. Davies <cit.> presents experimental evidence that Theorem <ref> holds for random real rank-one perturbations and random real Gaussian perturbations, but a proof (or disproof) remains to be found.  See Remark <ref> for a discussion of why our proof does not extend to the case of real Gaussian perturbations.

One may also ask if Theorem <ref> can be derandomized; that is, if the regularizing perturbation E can be chosen by a deterministic algorithm given A as input. One natural choice would be to perturb in the direction of the nearest normal matrix in either operator or Frobenius norm, the latter of which can be written as a certain optimization problem over unitary matrices <cit.>.

Proposition <ref> shows that the upper bound in Theorem
<ref> is tight in the perturbation size δ.  Now, let c_n be the
smallest constant such that Theorem <ref> holds with an upper bound of
c_n/δ.  Theorem <ref> implies that c_n ≤ 8 n^3/2, and since
κ_V  = ‖ V ‖‖ V^-1‖≥ 1 for any matrix, we have
c_n ≥ 1.  It would be interesting to determine the correct asymptotic
behavior of c_n. Davidson, Herrero, and Salinas asked in 1989 <cit.> whether the statement of
Theorem <ref> is possible with κ_V(A+E) depending only on δ and not on n.
In the present context, we can ask the more refined question: does Theorem
<ref> hold with bounded c_n, or must c_n go to infinity with n?






§ ACKNOWLEDGEMENTS

J.B. is supported by the NSF Graduate Research Fellowship Program under Grant DGE-1752814. A.K., S.M., and N.S. are supported by NSF Grant CCF-1553751. This work was done at the Simons Institute at UC Berkeley as part of the Spring 2019 program "Geometry of Polynomials." We thank Jorge Garza Vargas for helpful conversations and for pointing out errors in an earlier version of this paper.  We thank Stanisław Szarek for pointing out the reference <cit.> to us. We thank Amol Aggarwal, Milind Hegde, Tyler Maltba, and Jim Pitman for helpful conversations regarding stochastic differential equations. Finally, we thank the anonymous referee for thoughtful comments on an earlier version of this paper.

alpha






§ PROOF OF THEOREM <REF>

The goal of this appendix is to adapt Śniady's  <cit.> proof of Theorem <ref>, as outlined below the statement of Theorem <ref>,  to the case of real matrices with real Ginibre perturbations.

The stochastic differential equation satisfied by the squared singular values of a real matrix Brownian motion was derived by Bru in her work on Wishart processes <cit.> and independently by Le in her work on shape theory <cit.>.  The equation reads as follows:


    dλ_i = 2√(λ_i)/n dB_i + ( 1+∑_j  iλ_i + λ_j/λ_i - λ_j) dt,      1 ≤ i ≤ n.


The proof strategy of Śniady crucially relies on the existence and uniqueness of strong solutions to the singular value SDE. This is needed in order to obtain two solutions driven by the same Brownian motion, and to assert that the law of each solution indeed matches the law of the singular values of a noncentered Ginibre matrix. See <cit.> for a definition of strong solution and a rigorous proof of existence and uniqueness of strong solutions for Dyson Brownian motion, the Hermitian analogue of the Ginibre singular values process.

Fortunately, such results are known for the SDE (<ref>).  Let Λ denote the domain

    Λ∈ℝ^n := {λ : 0 ≤λ_n < … < λ_1}.

For any initial data λ(0) lying in the closure Λ, it is known that strong solutions to (<ref>) exist, are unique, and lie in Λ for all t > 0, almost surely <cit.>.  Combining this with <cit.>, we have that for initial data λ(0) lying in Λ, the law of the strong solutions to (<ref>) matches the law of the squared singular values process of A + M/√(n), where M is a matrix of i.i.d. standard real Brownian motions and A has squared singular values λ(0).  (It should be possible to extend this last statement for initial data in Λ, but the proof may be somewhat involved—cf. <cit.>, which contains a proof of the corresponding extension for Dyson Brownian motion.)  

Let a_i(λ) = 1 + ∑_j  iλ_i + λ_j/λ_i - λ_j denote the drift coefficient in (<ref>).  As in Śniady's proof for the complex Ginibre case (Theorem <ref>), the key property of a allowing for the comparison theorem is the so-called quasi-monotonicity (see <cit.>) or Kamke–Ważewski condition <cit.> from differential inequalities, which is simply that 

    for all i,  a_i(λ^(1)) ≤ a_i(λ^(2))   whenever λ^(1)_i = λ^(2)_i and λ^(1)_j ≤λ^(2)_j  for all  j  i.
  One easily checks that a satisfies this condition on the domain Λ.

The nonconstant (indeed, non-Lipschitz) diffusion coefficient 2√(λ_i)/n in (<ref>) is a technical obstacle which does not appear in the SDE (<ref>) for the complex case.  Consequently, the final step of Śniady's proof as sketched below Theorem <ref> cannot be repeated naively, because taking the difference of two solutions no longer cancels out the diffusion terms. Fortunately, theory has been developed to handle Hölder-1/2 diffusion coefficients; see <cit.> for exposition of the one-dimensional case and see <cit.> for a survey of comparison theorems for SDEs in general.

Quasi-monotonicity and the one-dimensional Hölder-1/2 comparison theory are combined in a rather general multidimensional comparison theorem of Geiß and Manthey <cit.>.  Applied to the SDE (<ref>), this theorem provides exactly the right conclusion to replace the final step of Śniady's proof.  We state the relevant special case of their theorem below:
 
Consider the SDE

    dX_i = σ_i(X) dB_i + a_i(X) dt,      1 ≤ i ≤ n,

where the B_i are independent standard real Brownian motions, and σ_i, a_i : ℝ^n →ℝ are continuous.  Suppose the following conditions are satisfied:

    
  * the drift coefficient a satisfies the quasi-monotonicity condition (<ref>)
    
  * there exists ρ : ℝ_+ →ℝ_+ increasing with ∫_0^ρ^-2(u) du = ∞ for some >0, such that |σ_i(x) - σ_i(y)| ≤ρ(|x_i - y_i|) for all i and all x, y ∈ℝ^n
    
  * strong solutions for the SDE exist for all time and are unique.
 Suppose initial conditions X^(1)(0) and X^(2)(0) satisfy the inequality X^(1)_i(0) ≤ X^(2)_i(0) for all i.  Then almost surely, X^(1)_i(t) ≤ X^(2)_i(t) for all i and for all t > 0.  


Setting ρ(u) := √(u), the SDE (<ref>) satisfies the conditions of the Geiß-Manthey theorem, except that our domain for both a_i and σ_i is Λ, not ℝ^n.  We address these two coefficients in turn.

First we deal with the drift coefficient a_i, using a standard localization argument already implicit in the proof of Geiß and Manthey.  They (implicitly) define the stopping time ϑ_N to be the first time ‖ X^(1)‖≥ N or ‖ X^(2)‖≥ N, and use the fact that a is Lipschitz on the restricted domain ‖ X ‖≤ N to show that

    ℙ[X^(1)_i(t) ≤ X^(2)_i(t)   for all  0 ≤ t ≤ϑ_N] = 1.
 
Since strong solutions exist for all time, we have ϑ_N →∞ as N →∞ almost surely, which proves the theorem.  We modify this strategy for our SDE (<ref>) in the standard way:  Define the stopping time τ_1/m to be the first time either λ^(1) or λ^(2) leaves the set 

    Λ_1/m := {λ∈Λ: |λ_i - λ_i+1| > 1/m  for all 1 ≤ i ≤ n-1.}.
  Since strong solutions starting in Λ stay in Λ for all t ≥ 0 and are continuous, we have τ_1/m→∞ as m →∞ almost surely.  Since our a is Lipschitz on Λ_1/m, the proof of Theorem <ref> shows that 
    ℙ[λ^(1)_i(t) ≤λ^(2)_i(t)   for all  0 ≤ t ≤τ_1/m] = 1
 for all m. Taking m →∞, the result follows.

Finally, we address the diffusion coefficient σ_i(λ) = 2√(λ_i)/n.  The standard fix is to first modify the SDE to have diffusion coefficients 2√(|λ_i|)/n for all i, so that the domain of σ_i is enlarged to ℝ^n and Theorem <ref> may be applied. For this modified SDE, note that the constant zero function λ^(1)(t) = 0 is a strong solution.  Now let λ^(2) be any solution with λ^(2)_i(0) ≥ 0 for all i.  Applying Theorem <ref> to λ^(1) and λ^(2), we conclude that in fact, λ^(2)(t) ≥ 0 for all t ≥ 0.  Thus, the absolute value bars in the modified SDE can be removed a posteriori.  This argument is used, for example, when setting up the SDE for the so-called Bessel process, which shares this square-root diffusion coefficient—see <cit.> for details.


