On the real Davies' conjecture (Q2072087)

The analytic function \(f(A)\) of a complex diagonalizable matrix \(A=WDW^{-1}\) (\(D\) is diagonal and \(W\) is invertible) may be written as \(f(A)=Wf(D)W^{-1}\), where \(f(D)\) is the diagonal matrix with entries given by \(f(D)_{ii}=f(D_{ii})\). The columns of \(W\) are eigenvectors of \(A\). So, from the computational viewpoint, when the eigenvector condition number \[\kappa_V (A):= \inf_{W: A=WDW^{-1}} \|W\| \|W^{-1}\|\] is large, to compute \(f(A)\) is not straightforward. \textit{E. B. Davies} [SIAM J. Matrix Anal. Appl. 29, No. 4, 1051--1064 (2008; Zbl 1157.65024)] suggested a way to overcome this difficulty by finding a small perturbation \(A+E\) of \(A\) such that \(\kappa_V (A+E)\) is small and then computing \(f(A+E)\) instead of \(f(A)\). He conjectured that, for every positive integer \(n\), there exists \(c_n\) such that, for all \(A\in \mathbb{C}^{n\times n}\) with \(\|A\|\leq 1\) and \(\varepsilon>0\), \[ \inf_{E\in \mathbb{C}^{n\times n}} (\kappa_V (A+E)\varepsilon+\|E\|)\leq c_n\sqrt{\varepsilon}. \] Davies' conjecture [loc. cit.] was recently solved in a stronger form in [\textit{J. Banks} et al., Commun. Pure Appl. Math. 74, No. 10, 2114--2131 (2021; Zbl 1480.15014)]. In this paper, the authors study the original Davies' conjecture by means of a probabilistic approach, and show that real perturbations suffice to regularize the eigenvector condition number at least when \(A\) is real. A random variable \(X\) is said to be sub-Gaussian if there exist constants \(c\), \(C>0\) such that \(\mathbb{P}[|X|>t]\leq Ce^{-ct^2}\) for all \(t\geq 0\). Assume that \(\xi\) is a real sub-Gaussian random variable with density bounded by \(K\) and let \(G_n:=G_n(\xi)\), where \(G_n(\xi)\) is the random matrix such that \(n^{1/2}G_n(\xi)\) is distributed as an \(n\times n\) matrix, each of whose entries is an independent copy of \(\xi\). Given an \(n\times n\) matrix \(M\), denote the minimum eigenvalue gap of \(M\) by \(\eta(M)\) and the smallest singular value of \(M\) by \(\sigma_n(M)\). To prove Davies' conjecture the authors first present the following three key estimates. Estimate 1: For any \(A\in \mathbb{C}^{n\times n}\) and \(\varepsilon \geq 0\), we have \[\mathbb{P}[\sigma_n(A+\delta G_n)\leq \varepsilon]\leq 2\sqrt{2e}Kn^2\frac{\varepsilon}{\delta}.\] Estimate 2: Let \(A\in \mathbb{R}^{n\times n}\) with \(\|A\|\leq 1\) and \(\delta \in (0,1)\). Let \(\mathcal{E}_{K'}\) denote the event that \(\|G_n\|\leq K'\), and let \(z\in \mathbb{C}\) such that \(|z|\leq 3\delta K'+3\). Finally, let \(M=A+\delta G_n-zI\) and \(\varepsilon \geq 0\). Then \[\mathbb{P}[\mathcal{E}_{K'}\cap \sigma_n(M)\leq \varepsilon]\leq c_{4.2}(1+\delta K')\frac{\max(K,K^2)n^3\varepsilon^2}{\delta^2 | \operatorname{Im} z |}, \] where \(c_{4.2}>0\) is an absolute constant. Estimate 3: Let \(A\in \mathbb{R}^{n\times n}\) with \(\|A\|\leq 1\), let \(\delta\in (0,1)\) and let \(M=A+\delta G_n.\) Let \(\mathcal{E}_{K'}\) denote the event that \(\|G_n\|\leq K'\). Then, for \(s\leq 1,\) \[\mathbb{P}[\mathcal{E}_K'\cap \eta(M)\leq s]\leq c_{4.3} \log_2(2(1+\delta K')/s)\cdot (1+\delta K')^2 \max(K^2,K^3)n^5\frac{s}{\delta^3},\] where \(c_{4.3}>0\) is an absolute constant. Then they show that for \(A\in \mathbb{R}^{n\times n}\) with \(\|A\|\leq 1\) and \(\delta \in (0,1)\), there are \(C_1, C_2\), depending only on \(\xi\), such that \[\mathbb{P}[\{\kappa_V(A+\delta G_n(\xi))\leq C_1n^2 \delta^{-1}\sqrt{\log(n\delta^{-1})}\}\cap\{\|\delta G_n\|\leq C_2\delta \}]\geq 1/2.\] At last, the authors apply the above results to show that, for \(\delta \in (0, 1/2)\) and \(A\in \mathbb{R}^{n\times n}\), there is a matrix \(E\in \mathbb{R}^{n\times n}\) with \(\|E\|\leq \delta\|A\|\) such that \[ \kappa_V(A+E)\leq C n^2\delta ^{-1}\sqrt{\log(n\delta^{-1})},\] where \(C>0\) is an absolute constant. This implies Davies' conjecture up to an overall factor of \(\log ((1/\varepsilon))^{1/4}\).