# 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.

-

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
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