# Tridiagonal Toeplitz matrix complex eigenvalues instead of real
**URL:** https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892
**Category:** Numerics
**Tags:** linearalgebra
**Created:** [November 3, 2021, 5:12pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892 "2021-11-03T17:12:44Z")
**Posts on this page:** 8
**Page:** 1
### Author:  [@jamblejoe](https://discourse.julialang.org/u/jamblejoe)
#### Post date: [November 3, 2021, 5:12pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/1 "2021-11-03T17:12:44Z")
The spectrum of tridiagonal Toeplitz matrices is known analytically ([Tridiagonal-Toeplitz-Matrix – Wikipedia](https://de.wikipedia.org/wiki/Tridiagonal-Toeplitz-Matrix)) and is (for non-zero off-diagonals) simple and real. Julia’s eigen function returns for small non-symmetric Toeplitz matrices the correct real spectrum, but for larger sizes fails to do so. E.g.
```julia
n = 200
p = 0.7
q = 0.4
A = Tridiagonal([q for _ in 1:(n-1)], zeros(n), [p for _ in 1:(n-1)])
A = Array(A)
maximum(imag.(eigvals(A)))
```
Shows non-zero imaginary parts significantly larger than machine precision. The same happens in numpy. Changing to BigFloat helped for sizes of n around 200. I did not test for larger n, but would guess that at sufficiently large n it will fail as well.
Is there a way to detect the failure of `eigen`?
EDIT: In python an example was given here: [python - How to get real eigenvalues and eigenvectors for a tridiagonal Toeplitz matrix? - Stack Overflow](https://stackoverflow.com/questions/48999970/how-to-get-real-eigenvalues-and-eigenvectors-for-a-tridiagonal-toeplitz-matrix)
and here
[python - Eigenvectors are complex but only for large matrices - Stack Overflow](https://stackoverflow.com/questions/61878026/eigenvectors-are-complex-but-only-for-large-matrices?rq=1)
---
### Author:  [@andreasnoack](https://discourse.julialang.org/u/andreasnoack)
#### Post date: [November 3, 2021, 7:01pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/2 "2021-11-03T19:01:22Z")
The eigenvalues of these matrices are super ill conditioned. I spent some time on these matrices with @sverek a while ago. Sven-Erik knows a lot more about these than I do.
The condition number of the eigenvalue is roughly reciprocal of the inner product between the right and the left (normalized) eigenvectors for that value. (I think I have the condition number from Nick HIgham’s book). So you have
```julia
julia> n = 20;
julia> A = Tridiagonal([q for _ in 1:(n-1)], zeros(n), [p for _ in 1:(n-1)]);
julia> F = eigen(Array(A));
julia> vr = (A - F.values[end]*I)\randn(n) |> t -> t/norm(t);
julia> vl = (A' - F.values[end]*I)\randn(n) |> t -> t/norm(t);
julia> abs(inv(vl'vr))
6.737730466564851
julia> n = 200;
julia> A = Tridiagonal([q for _ in 1:(n-1)], zeros(n), [p for _ in 1:(n-1)]);
julia> F = eigen(Array(A));
julia> vr = (A - F.values[end]*I)\randn(n) |> t -> t/norm(t);
julia> vl = (A' - F.values[end]*I)\randn(n) |> t -> t/norm(t);
julia> abs(inv(vl'vr))
7.360334831197046e19
```
so `n` doen’t have to get large before small perturbations will be heavily amplified in the eigenvalues.
---
### Author:  [@sverek](https://discourse.julialang.org/u/sverek)
#### Post date: [November 3, 2021, 8:01pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/3 "2021-11-03T20:01:47Z")
I can send you some current references regarding this (and some ways how to deal with it). By the way, the spectrum does not have to be real (e.g., just set q=-0.4).
---
### Author:  [@zdenek\_hurak](https://discourse.julialang.org/u/zdenek_hurak)
#### Post date: [November 3, 2021, 8:11pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/4 "2021-11-03T20:11:22Z")
By the way, when I run your code
```julia
using LinearAlgebra
n = 200
p = 0.7
q = 0.4
A = Tridiagonal([q for _ in 1:(n-1)], zeros(n), [p for _ in 1:(n-1)])
A = Array(A)
```
to build the matrix `A` of the size 200×200 in Julia 1.6.3 and then I compute the eigenvalues, I get just real eigenvalues for this size
```julia
julia> λ = eigvals(A)
200-element Vector{Float64}:
-1.058223000149799
-1.0576000083075798
-1.0572843720725433
-1.056332059729569
-1.0544327076739584
-1.0543669353419873
-1.0515818708879903
-1.0503080759555965
-1.0477502207464444
-1.045428090444631
⋮
1.0477851444774355
1.050211862207378
1.051655860894167
1.0543900728172997
1.0543919786468086
1.0563388912151381
1.0572818987403343
1.0576011289599778
1.058222590801755
```
I only get complex eigvenvalues for `n=207` (and larger).
---
### Author:  [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)
#### Post date: [November 3, 2021, 8:20pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/5 "2021-11-03T20:20:59Z")
> [@zdenek\_hurak](#):
>
> matrix `A` of the size 200×200 in Julia 1.6.3 and then I compute the eigenvalues, I get just real eigenvalues for this size
Fyi, that is not the case here on Win10 for Julia 1.6.3 or v"1.7.0-rc1" …
_ **NB:**
the maximum imaginary part is ~ 0.05% of the corresponding real part_
---
### Author:  [@zdenek\_hurak](https://discourse.julialang.org/u/zdenek_hurak)
#### Post date: [November 3, 2021, 8:24pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/6 "2021-11-03T20:24:08Z")
How come? Julia is the same, the rules for floating point arithmetics are the same. Is it that it is linked to different BLAS or LAPACK or what?
---
### Author:  [@zdenek\_hurak](https://discourse.julialang.org/u/zdenek_hurak)
#### Post date: [November 3, 2021, 8:37pm UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/7 "2021-11-03T20:37:18Z")
As @andreasnoack mentions, the matrix is ill-conditioned. For such matrices, computing [pseudospectrum](https://www.cs.ox.ac.uk/pseudospectra/) instead of spectrum (eigenvalues) gives some/more insight. Julia has a [package for computing Pseudospectra](https://ralphas.github.io/Pseudospectra.jl) too.
For your matrix with `n=1000` it looks like this
The code to produce it this:
```julia
using LinearAlgebra
using Plots
using Pseudospectra
n = 1000
p = 0.7
q = 0.4
A = Tridiagonal([q for _ in 1:(n-1)], zeros(n), [p for _ in 1:(n-1)])
A = Array(A)
λ = eigvals(A)
spectralportrait(A)
```
For `n=200`, the pseudospectrum is this
---
### Author:  [@jamblejoe](https://discourse.julialang.org/u/jamblejoe)
#### Post date: [November 4, 2021, 10:08am UTC](https://discourse.julialang.org/t/tridiagonal-toeplitz-matrix-complex-eigenvalues-instead-of-real/70892/8 "2021-11-04T10:08:17Z")
Thank you for all your great answers. I was not aware that finding the eigenvalues of tridiagonal Toeplitz matrices is such an ill-conditioned problem. I will mark @andreasnoack post as answer, but I am very grateful for all your comments, especially @zdenek_hurak pointing to the pseudo spectrum.
@zdenek_hurak @rafael.guerra I did my tests in Windows 10. On WSL 2, Ubuntu 20.04 I get non-zero imaginary parts for `n=200` as well. My specs are for
Windows
```julia
Julia Version 1.6.2
Commit 1b93d53fc4 (2021-07-14 15:36 UTC)
Platform Info:
OS: Windows (x86_64-w64-mingw32)
CPU: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
Environment:
JULIA_NUM_THREADS = 4
```
and WSL 2 Ubuntu:
```julia
julia> versioninfo()
Julia Version 1.6.3
Commit ae8452a9e0 (2021-09-23 17:34 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
```
Could it be something processor specific?