# Eigenvalues of a sum of a non-negative symmetric Toeplitz and a non-negative diagonal matrix

I have an $n\times n$ Toeplitz matrix $\mathbf{A}$ that is non-negative and symmetric (that is, $A_{i,j}=A_{j,i}=a_i\geq 0$) and a diagonal matrix $\mathbf{B}=\operatorname{diag}(b_1,b_2,\ldots,b_n)$ where $b_i\geq 0$.

Are there are any theorems/lemmas on the eigenvalues of the sum $\mathbf{A}+\mathbf{B}$? Specifically, I am looking for the upper and lower bounds (or exact results if they exist) on the maximum and minimum eigenvalues, respectively.

## 1 Answer

You might try to look up the Courant-Fischer (sometimes called Courant Mini-max) Theorem. It does a decent job in certain contexts of estimating maximum eigenvalues.

• Since $\mathbf{A}+\mathbf{B}$ is symmetric, by a version of Courant-Fischer in Lemma 2.1 here, its max. eigenvalue $\eta_M(\mathbf{A}+\mathbf{B})=\max_{z:z^Tz=1}z^T(\mathbf{A}+\mathbf{B})z$. Then $\eta_M(\mathbf{A}+\mathbf{B})=\max_{z:z^Tz=1}z^T\mathbf{A}z+z^T\mathbf{B}z$, and $\eta_M(\mathbf{A}+\mathbf{B})\leq\max_{z_1:z_1^Tz_1=1}z_1^T\mathbf{A}z_1+\max_{z_2:z_2^Tz_2=1}z_2^T \mathbf{B}z_2=\eta_M(\mathbf{A})+\eta(\mathbf{B})$. Min. is similar. Am I right? – M.B.M. Apr 4 '12 at 3:52
• Yes your estimates appear to be correct. Notice that this immediately gives you something that may be useful because you can directly calculate the eigenvalues of $B$, namely they are just the diagonal elements $b_1,b_2,\dots,b_n$. One other property is that $A+B$ is again a Toeplitz matrix (I didn't know what this was at first when I answered the question). So this may give you an extra property that I am unaware of, though from my quick search it doesn't seem that Toeplitz matrices lend themselves to easier eigenvalue computation in general. – Keaton Apr 4 '12 at 4:36
• What you have gotten from this is a corollary that often comes from the Courant-Fischer theorem and that is if you have any real symmetric matrix, and you add positive elements to its diagonal, then you only increase (more accurately you don't decrease) the eigenvalues. In your case, you get an upper estimate of how the eigenvalues could have changed. – Keaton Apr 4 '12 at 4:39
• Yeah, this is interesting. Thanks for the reminder about the Courant-Fischer. Btw, $\mathbf{A}+\mathbf{B}$ is not Toeplitz, as the diagonal entries aren't the same, however, it is still symmetric. Toeplitz matrices actually do have nice eigenvalue behavior in the limit, since, as their size increases, they get closer to circulant matrices, whose eigenvalues are just the DFT of the top row. The reference I cited in my earlier comment covers that. – M.B.M. Apr 4 '12 at 5:36