A Note on Eigenvalues of Perturbed Hermitian Matrices This paper originally published in Linear Algebra and its Applications , 395 (2005), 183–190. The main results are well received since. Unfortunately, the published version contains quite a number of typos. This arXiv version serves two purposes:
Chi-Kwong Li, Ren-Cang Li · 2025
Read A Note on Eigenvalues of Perturbed Hermitian Matrices This paper originally published in Linear Algebra and its Applications , 395 (2005), 183–190. The main results are well received since. Unfortunately, the published version contains quite a number of typos. This arXiv version serves two purposes: by Chi-Kwong Li, Ren-Cang Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08203.txt.
Introduction
Chi-Kwong Li and Ren-Cang Li revisit a result on how eigenvalues shift when a matrix is perturbed, in a note first published in a linear algebra journal in 2005. Posted in corrected form in 2025. The authors say the original printed version held many typos. Their setting splits a Hermitian matrix into two diagonal blocks plus an off-diagonal disturbance.
Older bounds either ignore the gap between the two blocks or blow up when that gap is tiny. Their bound uses both the size of the disturbance and the gap, improving on earlier estimates. Matrix eigenvalues underpin stability work across physics and engineering, so a sharper bound has wide use.
Catalog record
| CREATOR | Chi-Kwong Li, Ren-Cang Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-08203
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Note on Eigenvalues of Perturbed Hermitian Matrices This paper originally published in Linear Algebra and its Applications , 395 (2005), 183–190. The main results are well received since. Unfortunately, the published version contains quite a number of typos. This arXiv version serves two purposes: 1) fix typos, and 2) add an appendix on how to best use the main results for sharper error bounds than straightforward applications in certain situations, e.g., approximations from Krylov subspaces. Chi-Kwong Li, Ren-Cang Li Abstract Let A = ( H 1 E ∗ E H 2 ) and A ~ = ( H 1 O O H 2 ) A=\left(\begin{array}[]{cc}H_{1}&E^{*}\\ E&H_{2}\end{array}\right)\quad\hbox{ and }\quad\widetilde{A}=\left(\begin{array}[]{cc}H_{1}&O\\ O&H_{2}\end{array}\right) be two N N -by- N N Hermitian matrices with eigenvalues λ 1 ≥ ⋯ ≥ λ N \lambda_{1}\geq\cdots\geq\lambda_{N} and λ ~ 1 ≥ ⋯ ≥ λ ~ N \widetilde{\lambda}_{1}\geq\cdots\geq\widetilde{\lambda}_{N} , respectively. Denote by ‖ E ‖ \|E\| the spectral norm of the matrix E E , and η \eta the spectral gap between the spectra of H 1 H_{1} and H 2 H_{2} . It is shown that | λ i − λ ~ i | ≤ 2 ‖ E ‖ 2 η + η 2 + 4 ‖ E ‖ 2 , |\lambda_{i}-\widetilde{\lambda}_{i}|\leq{2\|E\|^{2}\over\eta+\sqrt{\eta^{2}+4\|E\|^{2}}}\,, which improves all the existing results. Similar bounds are obtained for singular values of matrices under block perturbations. AMS Classifications: 15A42, 15A18, 65F15. Keywords: Hermitian matrix, eigenvalue, singular value. 1 Introduction Consider a partitioned Hermitian matrix A=\bordermatrix{&\scriptstyle m&\scriptstyle n\cr\scriptstyle m&H_{1}&E^{*}\cr\scriptstyle n&E&H_{2}\cr}, (1.1) where E^{*} is E ’s complex conjugate transpose. At various situations (typically when E is small ), one is interested in knowing the impact of removing E and E^{*} on the eigenvalues of A . More specifically, one would like to obtain bounds for the differences between that eigenvalues of A and those of its perturbed matrix \widetilde{A}=\bordermatrix{&\scriptstyle m&\scriptstyle n\cr\scriptstyle m&H_{1}&O\cr\scriptstyle n&O&H_{2}\cr}. (1.2) Let \lambda(X) be the spectrum of the square matrix X , and let \|Y\| be the spectral norm of a matrix Y , i.e., the largest singular value of Y . There are two kinds of bounds for the eigenvalues \lambda_{1}\geq\cdots\geq\lambda_{m+n} and \widetilde{\lambda}_{1}\geq\cdots\geq\widetilde{\lambda}_{m+n} of A and \widetilde{A} , respectively: 1. [ 1 , 7 , 8 ] |\lambda_{i}-\widetilde{\lambda}_{i}|\leq\|E\|. (1.3) 2. [ 1 , 2 , 3 , 5 , 7 , 8 ] If the spectra of H_{1} and H_{2} are disjoint, then |\lambda_{i}-\widetilde{\lambda}_{i}|\leq\|E\|^{2}/\eta, (1.4) where \eta\stackrel{{\scriptstyle{\mbox{\scriptsize\rm{def}}}}}{{=}}\min_{\mu_{1}\in\lambda(H_{1}),\,\mu_{2}\in\lambda(H_{2})}|\mu_{1}-\mu_{2}|. The bound of the first kind does not use information of the spectral distributions of the H_{1} and H_{2} , which will give (much) weaker bounds when \eta is not so small; while the bound of the second kind may blow up whenever H_{1} and H_{2} have a common eigenvalue. Thus both kinds have their own drawbacks, and it would be advantageous to have bounds that are always no bigger than \|E\| , of {\cal O}(\|E\|) as \eta\to 0 , and at the same time behave like {\cal O}(\|E\|^{2}/\eta) for not so small \eta . To further motivate our study, let us look at the following 2\times 2 example. Example 1 Consider the 2\times 2 Hermitian matrix A=\left(\begin{array}[]{cc}\alpha&\epsilon\\ \epsilon&\beta\end{array}\right). (1.5) Interesting cases are when \epsilon is small , and thus \alpha and \beta are approximate eigenvalues of A . We shall analyze by how much the eigenvalues of A differ from \alpha and \beta . Without loss of generality, assume \alpha>\beta,\quad\mbox{and $\epsilon$ is real}. The eigenvalues of A , denoted by \lambda_{\pm} , satisfy \lambda^{2}-(\alpha+\beta)\lambda+\alpha\beta-\epsilon^{2}=0 ; and thus \lambda_{\pm}=\frac{\alpha+\beta\pm\sqrt{(\alpha+\beta)^{2}-4(\alpha\beta-\epsilon^{2})}}{2}=\frac{\alpha+\beta\pm\sqrt{(\alpha-\beta)^{2}+4\epsilon^{2}}}{2}. Now \displaystyle 0<\left\{\begin{array}[]{c}\lambda_{+}-\alpha\\ \beta-\lambda_{-}\end{array}\right\} \displaystyle= \displaystyle\frac{-(\alpha-\beta)+\sqrt{(\alpha-\beta)^{2}+4\epsilon^{2}}}{2} (1.9) \displaystyle= \displaystyle\frac{2\epsilon^{2}}{(\alpha-\beta)+\sqrt{(\alpha-\beta)^{2}+4\epsilon^{2}}} which provides a difference that enjoys the following properties: \frac{2\epsilon^{2}}{(\alpha-\beta)+\sqrt{(\alpha-\beta)^{2}+4\epsilon^{2}}}\left\{\begin{array}[]{l}\leq\epsilon\quad\mbox{always,}\\ \to\epsilon\quad\mbox{as $\alpha\to\beta^{+}$,}\\ \leq\epsilon^{2}/(\alpha-\beta).\end{array}\right. The purpose of this note is to extend this 2\times 2 example and obtain bounds which improve both ( 1.3 ) and ( 1.4 ). Such results are not only of theoretical interest but also important in the computations of eigenvalues of Hermitian matrices [ 4 , 6 , 9 ] . As an application, similar bounds are presented for the singular value problem. 2 Main Result Theorem 2 Let A=\bordermatrix{&\scriptstyle m&\scriptstyle n\cr\scriptstyle m&H_{1}&E^{*}\cr\scriptstyle n&E&H_{2}\cr}\quad\hbox{ and }\quad\widetilde{A}=\bordermatrix{&\scriptstyle m&\scriptstyle n\cr\scriptstyle m&H_{1}&O\cr\scriptstyle n&O&H_{2}\cr} be Hermitian matrices with eigenvalues \lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{m+n}\quad\mbox{and}\quad\widetilde{\lambda}_{1}\geq\widetilde{\lambda}_{2}\geq\cdots\geq\widetilde{\lambda}_{m+n}, (2.1) respectively. Define \displaystyle\eta_{i} \displaystyle\stackrel{{\scriptstyle{\mbox{\scriptsize\rm{def}}}}}{{=}} \displaystyle\left\{\begin{array}[]{ll}\min\limits_{\mu_{2}\in\lambda(H_{2})}|\widetilde{\lambda}_{i}-\mu_{2}|,&\mbox{if $\widetilde{\lambda}_{i}\in\lambda(H_{1})$},\\ \min\limits_{\mu_{1}\in\lambda(H_{1})}|\widetilde{\lambda}_{i}-\mu_{1}|,&\mbox{if $\widetilde{\lambda}_{i}\in\lambda(H_{2})$},\end{array}\right. \displaystyle\eta \displaystyle\stackrel{{\scriptstyle{\mbox{\scriptsize\rm{def}}}}}{{=}} \displaystyle\min_{1\leq i\leq m+n}\eta_{i}=\min_{\mu_{1}\in\lambda(H_{1}),\,\mu_{2}\in\lambda(H_{2})}|\mu_{1}-\mu_{2}|. (2.5) Then for i=1,2,\cdots,m+n , we have \displaystyle|\lambda_{i}-\widetilde{\lambda}_{i}| \displaystyle\leq \displaystyle\frac{2\|E\|^{2}}{\eta_{i}+\sqrt{\eta_{i}^{2}+4\|E\|^{2}}} (2.6) \displaystyle\leq \displaystyle\frac{2\|E\|^{2}}{\eta+\sqrt{\eta^{2}+4\|E\|^{2}}}. (2.7) Proof. Suppose U^{*}H_{1}U and V^{*}H_{2}V are in the diagonal form with their diagonal entries arranged in the descending order, respectively. We may assume that U=I_{m} and V=I_{n} . Otherwise, replace A by (U\oplus V)^{*}A(U\oplus V). We may perturb the diagonal of A so that all entries are distinct, and apply continuity argument for the general case. We prove the result by induction on m+n . If m+n=2 , the result is clear (from our Example). Assume that m+n>2 , and the result is true for Hermitian matrices of size m+n-1 . First, refining an argument of Mathias [ 5 ] , we show that ( 2.6 ) holds for i=1 . Assume that the (1,1) st entry of H_{1} equals \widetilde{\lambda}_{1} . By the min-max principle [ 1 , 7 , 8 ] , we have \lambda_{1}\geq e_{1}^{*}Ae_{1}=\widetilde{\lambda}_{1}, where e_{1} is the first column of the identity matrix. No proof is necessary if \lambda_{1}=\widetilde{\lambda}_{1} . Assume \lambda_{1}>\widetilde{\lambda}_{1} and let X=\pmatrix{I_{m}&0\cr-(H_{2}-\lambda_{1}I_{n})^{-1}E&I_{n}}. Then X^{*}(A-\lambda_{1}I)X=\left(\begin{array}[]{cc}M(\lambda_{1})&0\\ 0&H_{2}-\lambda_{1}I_{n}\end{array}\right), where M(\lambda)=H_{1}-\lambda I_{m}-E^{*}(H_{2}-\lambda I_{n})^{-1}E. Since A and X^{*}AX have the same inertia, we see that M(\lambda_{1}) has zero as the largest eigenvalue. Notice that the largest eigenvalue of H_{1}-\lambda_{1}I is \widetilde{\lambda}_{1}-\lambda_{1}\leq 0 . Thus, for \delta_{1}=|\lambda_{1}-\widetilde{\lambda}_{1}|=\lambda_{1}-\widetilde{\lambda}_{1} , we have (see [ 7 , (10.9)] ) \lambda_{1}\leq\widetilde{\lambda}_{1}+\|E\|^{2}_{2}/(\delta_{1}+\eta_{1}), and hence \delta_{1}\leq\|E\|^{2}/(\delta_{1}+\eta_{1}). Consequently, \delta_{1}\leq{2\|E\|^{2}\over\eta_{1}+\sqrt{\eta_{1}^{2}+4\|E\|^{2}}} as asserted. Similarly, we can prove the result if the (1,1) th entry of H_{2} equals \widetilde{\lambda}_{1} . In this case, we will apply the inertia arguments to A and YAY^{*} with Y=\pmatrix{I_{m}&0\cr-E(H_{1}-\lambda_{1}I_{m})^{-1}&I_{n}}. Applying the result of the last paragraph to -A , we see that ( 2.6 ) holds for i=m+n . Now, suppose 1<i<m+n . The result trivially holds if \lambda_{i}=\widetilde{\lambda}_{i} . Suppose \lambda_{i}\neq\widetilde{\lambda}_{i} . We may assume that \widetilde{\lambda}_{i}>\lambda_{i} . Otherwise, replace (A,\widetilde{A},i) by (-A,-\widetilde{A},m+n-i+1) . Delete the row and column of A that contain the diagonal entry \widetilde{\lambda}_{m+n} . Suppose the resulted matrix \widehat{A} has eigenvalues \nu_{1}\geq\cdots\geq\nu_{m+n-1} . By the interlacing inequalities [ 7 , Section 10.1] , we have \lambda_{i}\geq\nu_{i}\qquad\hbox{ and hence }\qquad\widetilde{\lambda}_{i}-\lambda_{i}\leq\widetilde{\lambda}_{i}-\nu_{i}. (2.8) Note that \widetilde{\lambda}_{i} is the i th largest diagonal entries in \widehat{A} . Let \widehat{\eta}_{i} be the minimum distance between \widetilde{\lambda}_{i} and the diagonal entries in the diagonal block \widehat{H}_{j} in \widehat{A} not containing \widetilde{\lambda}_{i} , where j\in\{1,2\} . Then {\widehat{\eta}}_{i}\geq\eta_{i} because \widehat{H}_{j} may have one fewer diagonal entries than H_{j} . Let \widehat{E} be the off-diagonal block of \widehat{A} . Then \|\widehat{E}\|\leq\|E\| . Thus, \displaystyle|\lambda_{i}-\widetilde{\lambda}_{i}| \displaystyle= \displaystyle\widetilde{\lambda}_{i}-\lambda_{i}\hskip 72.1972pt\hbox{ because }\widetilde{\lambda}_{i}>\lambda_{i} \displaystyle\leq \displaystyle\widetilde{\lambda}_{i}-\nu_{i}\hskip 73.354pt\hbox{ by }(\ref{eq:2}) \displaystyle\leq \displaystyle{2\|\widehat{E}\|^{2}\over\widehat{\eta}_{i}+\sqrt{\widehat{\eta}_{i}^{2}+4\|\widehat{E}\|^{2}}}\hskip 15.17719pt\hbox{ by induction assumption } \displaystyle\leq \displaystyle{2\|\widehat{E}\|^{2}\over\eta_{i}+\sqrt{\eta_{i}^{2}+4\|\widehat{E}\|^{2}}}\hskip 15.17719pt\hbox{ because }\widehat{\eta}_{i}\geq\eta_{i} \displaystyle= \displaystyle{1\over 2}\sqrt{\eta_{i}^{2}+4\|\widehat{E}\|^{2}}-\eta_{i} \displaystyle\leq \displaystyle{1\over 2}\sqrt{\eta_{i}^{2}+4\|E\|^{2}}-\eta_{i}\quad\hbox{ because }\|\widehat{E}\|\leq\|E\| \displaystyle= \displaystyle{2\|E\|^{2}\over\eta_{i}+\sqrt{\eta_{i}^{2}+4\|E\|^{2}}} as asserted. 3 Application to Singular Value Problem In this section, we apply the result in Section 2 to study singular values of matrices. For notational convenience in connection to our discussion, we define the sequence of singular values of a complex p\times q matrix X by \sigma(X)=(\sigma_{1}(X),\dots,\sigma_{k}(X)), where k=\max\{p,q\} and \sigma_{1}(X)\geq\cdots\geq\sigma_{k}(X) are the