12
$\begingroup$

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.

Book link: http://newdoc.nccu.edu.tw/teasyllabus/111648701013/Numerical_Analysis.pdf

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.

$\endgroup$
  • 1
    $\begingroup$ Maybe Gershgorin might apply? $\endgroup$ – copper.hat May 6 at 23:32
  • $\begingroup$ @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 $\endgroup$ – user666729 May 6 at 23:51
  • $\begingroup$ Offhand, I can only get $(n-1)\epsilon$, but all eigenvalues lie in $\cup_k B(b_{jj}, (n-1)\epsilon)$. $\endgroup$ – copper.hat May 7 at 0:10
  • $\begingroup$ @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$. $\endgroup$ – PierreCarre May 7 at 10:03
  • $\begingroup$ @PierreCarre: Can you give one of the examples please? $\endgroup$ – copper.hat May 7 at 13:13
6
+150
$\begingroup$

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 \begin{equation} (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, \end{equation} 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 \begin{equation} \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. \end{equation}

$\endgroup$
  • $\begingroup$ Thanks. What is the meaning of each $E^{(j)}$? Is it arbitrary? $\endgroup$ – user666729 May 9 at 11:33
  • $\begingroup$ 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? $\endgroup$ – user666729 May 9 at 11:58
  • $\begingroup$ $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. $\endgroup$ – Geethu Joseph May 9 at 12:23
  • $\begingroup$ How can I see that they have the same eigenvalue? $\endgroup$ – user666729 May 9 at 12:25
  • $\begingroup$ $(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$. $\endgroup$ – Geethu Joseph May 9 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy