# Proving there is an eigenvalue $\lambda$ for which $|\lambda - b_{jj}| < \epsilon \sqrt{n}$

Let $$A$$ be an $$n\times n$$ real symmetric matrix. By applying Jacobi's method, suppose we have generated an orthogonal matrix $$R$$ and a symmetric matrix $$B$$ such that the equality

$$B = R^{T}AR$$

holds. Moreover, suppose the inequality $$|b_{ij}| < \epsilon$$ holds for all $$i \neq j$$.

Show that for each $$j = 1, 2, \ldots, n$$, there is at least one eigenvalue $$\lambda$$ of $$A$$ such that $$|\lambda - b_{jj}| < \epsilon \sqrt{n}$$ holds.

This is an exercise that I am doing to study for my final exam. So, I've just recently learned Jacobi's method, and I know that the eigenvalues and eigenvectors are related to the matrices $$B$$ and $$R$$; however, I have no idea how to use those results to prove an inequality. I also have no idea how to get the $$\sqrt{n}$$ term in there. I would greatly appreciate any help in this exercise.

Thanks

UPDATE: These are some theorems in my book that might help.

Theorem (Gerschgorin’s Theorem): Let $$n \geq 2$$ and $$A \in \mathbb{C}^{n\times n}$$. All eigenvalues of $$A$$ lie in the region $$D = \bigcup_{i=1}^{n} D_{i}$$, where $$D_{i}$$ are the Gerschgorin discs of $$A$$.

Definition: (Gerschgorin Disc): Suppose $$n \geq 2$$ and $$A \in \mathbb{C}^{n\times n}$$. The Gerschgorin discs $$D_{i}$$ of the matrix $$A$$ are defined by the closed circular regions

$$D_{i} = \{z \in \mathbb{C} : |z - a_{ii}| \leq R_{i}\},$$

where $$R_{i} = \sum_{j = 1, \\ i \neq j}^{n} |a_{ij}|$$

is the radius of $$D_{i}$$.

Theorem (Bauer-Fike): Suppose $$A$$ and $$E$$ are real symmetric $$n\times n$$ matrices and $$B = A - E$$. Assume, further, that the eigenvalues of $$A$$ are denoted by $$\lambda_{j}, j = 1, 2, 3, \ldots, n$$ and $$\mu$$ is an eigenvalue of $$B$$. Then at least one eigenvalue of $$\lambda_{j}$$ of $$A$$ satisfies $$|\lambda_{j} - \mu| \leq ||E||_{2}$$, where $$|| \cdot ||_{2}$$ denotes the $$2$$-norm of a matrix.

The problem is from chapter 5. I would appreciate it if the answer does not use too many outside results from the book. I suppose a few are okay though, as long as they aren't really strong results that are hard to understand.

• Maybe Gershgorin might apply? – copper.hat May 6 at 23:32
• @copper.hat I have no idea how to proceed. Can you please help me? I will update my original post with my the statement of Gerschgorin's Theorem – user666729 May 6 at 23:51
• Offhand, I can only get $(n-1)\epsilon$, but all eigenvalues lie in $\cup_k B(b_{jj}, (n-1)\epsilon)$. – copper.hat May 7 at 0:10
• @gallileo The eigenvalues of $A$ and $B$ are the same. You can easily find matrices $B$ that do not satisfy the proposed condition. So, either the result is false or coming from Jacobi's method sets some restrictions on $B$. – PierreCarre May 7 at 10:03
• @PierreCarre: Can you give one of the examples please? – copper.hat May 7 at 13:13

## 1 Answer

The eigenvalues of a matrix and its similarity transform are the same, so the eigenvalues of $$A$$ and $$B$$ are the same.

Next, for every $$j=1,2,\ldots,n$$, define a symmetric matrix $$E^{(j)}=(B-b_{jj}I)e_je_j^T+e_je_j^T(B-b_{jj}I)$$, where $$e_j$$ is $$j^\text{th}$$ standard basis vector. We have $$$$(B-E^{(j)})e_j= Be_j - (B-b_{jj}I)e_j+e_je_j^T(B-b_{jj}I) e_j= b_{jj}e_j,$$$$ since $$e_je_j^TBe_j = e_j(e_j^TBe_j )= b_{jj}e_j.$$ Thus, $$b_{jj}$$ is an eigenvalue of $$B-E^{(j)}$$, and hence we invoke Bauer-Fike theorem to show that there exists an eigenvalue $$\lambda$$ of $$B$$ such that $$$$\vert b_{jj}-\lambda\vert\leq \Vert E^{(j)}\Vert = \Vert(B-b_{jj}I)e_j\Vert = \sqrt{\sum_{i=1,i\neq j}^nb_{ij}^2}\leq \sqrt{n-1}\epsilon<\sqrt{n}\epsilon.$$$$

• Thanks. What is the meaning of each $E^{(j)}$? Is it arbitrary? – user666729 May 9 at 11:33
• Does $(B - b_{jj}I)e_{j}e_{j}^{T}$ represent the diagonal elements of matrix $B$? And the second term in $E^{(j)}$ represents the off-diagonal elements of matrix $B$? Is that correct? – user666729 May 9 at 11:58
• $E^{(j)}$ is well defined perturbation for every $j$. It perturbs the original matrix so that the perturbed matrix has $b_{jj}$ as it's eigenvalue. – Geethu Joseph May 9 at 12:23
• How can I see that they have the same eigenvalue? – user666729 May 9 at 12:25
• $(B-b_{jj})e_j$ represents the $j^\text{the}$ column of $B$ with the $j$ entry replaced by 0. $E^{(j)}$ is zero everywhere except the $j^\text{the}$ row and column replaced with $(B-b_{jj})e_j$. Note that $E^{(j)}$ is different for each $j$. – Geethu Joseph May 9 at 12:28