# Numerical Calculation of Eigenvalues of a large real Symmetric tridiagonal matrix

If I have an $N \times N$ matrix where every entry is zero except for along the super-diagonal and sub-diagonal, where the each entry is the conjugate of the last, like the following $5 \times 5$ matrix

$$\begin{bmatrix}0 & (1-t) & 0 & 0 & 0 \\(1-t) & 0 & (1+t) & 0 & 0 \\0 & (1+t) & 0 & (1-t) & 0 \\0 & 0 & (1-t) & 0 & (1+t)\\0 & 0 & 0 & (1+t) & 0 \end{bmatrix}$$

where $t$ is some parameter. Imagine a much larger matrix following the same pattern.

Is there any way, numerical or otherwise to find the eigenvalues?

• If $N$ is odd, the problem can be solved explicitly; if it's even, one has to rely instead on approximations. Unfortunately, my references offhand for this are from the physics literature and so are not necessarily transparent. (I had to do a lot of analytic calculations/approximations in the case of $N$ even, so I have some familiarity.) May 29, 2016 at 0:06
• Is $|t| \ll 1$? Can the matrix be thought of as a perturbation of a tridiagonal Toeplitz matrix? May 29, 2016 at 4:23
• I fixed a typo in my answer. The cost of the QR algorithm is $O(n)$ pr. iteration. Typically one needs $2-3$ iterations pr. eigenvalue. So if you want them all, then the cost is $O(n^2)$. May 29, 2016 at 17:52
• @Semiclassical can you point me to anywhere I can find more information on what you said in your answer? May 30, 2016 at 16:56

This is not a full solution, but may give you some clues:

The trace of this matrix is zero, so the sum of eigenvalues should be zero. In fact for every odd power of the matrix the trace is zero. If you multiply the matrix by itself the trace of new matrix is no longer zero, so the sum of eigenvalues of the squared matrix is not zero. In fact, again, every even power has non-zero trace, which leads me to believe that the eigenvalues will consist of non-zero pairs $\lambda, -\lambda$ and $0$ (maybe repeated values of $0$ for even order matrix, not sure).

So indeed, for the $5 \times 5$ matrix you have there, if I just use Mathematica to get the eigenvalues: $\left\{0,-\sqrt{t^2+3},\sqrt{t^2+3},-\sqrt{3 t^2+1},\sqrt{3 t^2+1}\right\}$. Maybe if you try with different orders of matrices you will be able to develop some formula in terms of $n$, where $n$ is the order of the matrix.

• Hey Christiaan, I'm wondering if I can borrow your expertise; maybe you can see something I'm not. So for the matrix, here are some facts I now know: if N is even you will have Symmetric eigenvalues ie: if λ is an eigenvalue, so is -λ, and λ will never be 0. For odd N, There will always be one 0 eigen value, and then symmetric eigenvalues again. As well if you fill the matrix with 1+t or 1-t, you get the same values If N is odd. However if N is even, flipping the fill order will produce very different values. Is there any relation between the eigen values in the even case? Thanks! Jun 9, 2016 at 17:19
• Well my next step would be to look at how the characteristic polynomial develops as $n$ increases. Again, just a quick look using Mathematica, for $n=4$ using the same order you have in the question: $z^4+((2-3 t) t-3) z^2+(t-1)^4$, then for $n=6$: $z^6+((2-5 t) t-5) z^4+2 (t (t (t (3 t-4)+10)-4)+3) z^2-(t-1)^6$. Now maybe numerically you can exploit some properties of the parameter $t$, i.e. if it is smaller than 1 then the constant term approaches zero as $n$ increases...this is in the current order. If you flip the order the constant term is a power of $(1+t)$, so the term won't vanish. Jun 10, 2016 at 8:31

In general, the symmetric eigenvalue problem is solved by reducing the matrix to tridiagonal form and then applying the QR algorithm with implicit shifts.

Only the last stage is relevant here and the run time is $O(n^2)$ as you only want the eigenvalues. I recommend starting with the routines implemented in LAPACK. A short list of relevant routines is given here

http://www.netlib.org/lapack/lug/node48.html

I see no way to exploit the very special substructure of your tridiagonal matrix in numerical computations.

• What is the run time for finding eigenvectors as well? Jun 16, 2016 at 3:10
• @Craig: First you find the eigenvectors for the tridiagonal matrix. You need to solve $n$ triangular linear systems to do that. This costs $O(n^2)$ operations. Then you to back-transform these eigenvectors to get the eigenvectors for the original matrix. That costs $O(n^3)$ operations. Jun 21, 2016 at 9:54
• What original matrix? The only matrix I'm working with is tridiagonal Jun 21, 2016 at 14:06