# Tridiagonal matrix

In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal below this), and the supradiagonal/upper diagonal (the first diagonal above the main diagonal). For example, the following matrix is tridiagonal:

${\displaystyle {\begin{pmatrix}1&4&0&0\\3&4&1&0\\0&2&3&4\\0&0&1&3\\\end{pmatrix}}.}$

The determinant of a tridiagonal matrix is given by the continuant of its elements.[1]

An orthogonal transformation of a symmetric (or Hermitian) matrix to tridiagonal form can be done with the Lanczos algorithm.

## Properties

A tridiagonal matrix is a matrix that is both upper and lower Hessenberg matrix.[2] In particular, a tridiagonal matrix is a direct sum of p 1-by-1 and q 2-by-2 matrices such that p + q/2 = n — the dimension of the tridiagonal. Although a general tridiagonal matrix is not necessarily symmetric or Hermitian, many of those that arise when solving linear algebra problems have one of these properties. Furthermore, if a real tridiagonal matrix A satisfies ak,k+1 ak+1,k > 0 for all k, so that the signs of its entries are symmetric, then it is similar to a Hermitian matrix, by a diagonal change of basis matrix. Hence, its eigenvalues are real. If we replace the strict inequality by ak,k+1 ak+1,k ≥ 0, then by continuity, the eigenvalues are still guaranteed to be real, but the matrix need no longer be similar to a Hermitian matrix.[3]

The set of all n × n tridiagonal matrices forms a 3n-2 dimensional vector space.

Many linear algebra algorithms require significantly less computational effort when applied to diagonal matrices, and this improvement often carries over to tridiagonal matrices as well.

### Determinant

The determinant of a tridiagonal matrix A of order n can be computed from a three-term recurrence relation.[4] Write f1 = |a1| = a1 (i.e., f1 is the determinant of the 1 by 1 matrix consisting only of a1), and let

${\displaystyle f_{n}={\begin{vmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{vmatrix}}.}$

The sequence (fi) is called the continuant and satisfies the recurrence relation

${\displaystyle f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}}$

with initial values f0 = 1 and f−1 = 0. The cost of computing the determinant of a tridiagonal matrix using this formula is linear in n, while the cost is cubic for a general matrix.

### Inversion

The inverse of a non-singular tridiagonal matrix T

${\displaystyle T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}}$

is given by

${\displaystyle (T^{-1})_{ij}={\begin{cases}(-1)^{i+j}b_{i}\cdots b_{j-1}\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}ij\\\end{cases}}}$

where the θi satisfy the recurrence relation

${\displaystyle \theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\qquad i=2,3,\ldots ,n}$

with initial conditions θ0 = 1, θ1 = a1 and the ϕi satisfy

${\displaystyle \phi _{i}=a_{i}\phi _{i+1}-b_{i}c_{i}\phi _{i+2}\qquad i=n-1,\ldots ,1}$

with initial conditions ϕn+1 = 1 and ϕn = an.[5][6]

Closed form solutions can be computed for special cases such as symmetric matrices with all diagonal and off-diagonal elements equal[7] or Toeplitz matrices[8] and for the general case as well.[9][10]

In general, the inverse of a tridiagonal matrix is a semiseparable matrix and vice versa.[11]

### Solution of linear system

A system of equations Ax = b for ${\displaystyle b\in \mathbb {R} ^{n}}$ can be solved by an efficient form of Gaussian elimination when A is tridiagonal called tridiagonal matrix algorithm, requiring O(n) operations.[12]

### Eigenvalues

When a tridiagonal matrix is also Toeplitz, there is a simple closed-form solution for its eigenvalues, namely:[13][14]

${\displaystyle a-2{\sqrt {bc}}\cos \left({\frac {k\pi }{n+1}}\right),\qquad k=1,\ldots ,n.}$

A real symmetric tridiagonal matrix has real eigenvalues, and all the eigenvalues are distinct (simple) if all off-diagonal elements are nonzero.[15] Numerous methods exist for the numerical computation of the eigenvalues of a real symmetric tridiagonal matrix to arbitrary finite precision, typically requiring ${\displaystyle O(n^{2})}$ operations for a matrix of size ${\displaystyle n\times n}$, although fast algorithms exist which (without parallel computation) require only ${\displaystyle O(n\log n)}$.[16]

As a side note, an unreduced symmetric tridiagonal matrix is a matrix containing non-zero off-diagonal elements of the tridiagonal, where the eigenvalues are distinct while the eigenvectors are unique up to a scale factor and are mutually orthogonal.[17]

### Similarity to symmetric tridiagonal matrix

For unsymmetric or nonsymmetric tridiagonal matrices one can compute the eigendecomposition using a similarity transformation. Given a real tridiagonal, nonsymmetric matrix

${\displaystyle T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}}$

where ${\displaystyle b_{i}\neq c_{i}}$. Assume that each product of off-diagonal entries is strictly positive ${\displaystyle b_{i}c_{i}>0}$ and define a transformation matrix ${\displaystyle D}$ by

${\displaystyle D:=\operatorname {diag} (\delta _{1},\dots ,\delta _{n})\quad {\text{for}}\quad \delta _{i}:={\begin{cases}1&,\,i=1\\{\sqrt {\frac {c_{i-1}\dots c_{1}}{b_{i-1}\dots b_{1}}}}&,\,i=2,\dots ,n\,.\end{cases}}}$

The similarity transformation ${\displaystyle D^{-1}TD}$ yields a symmetric tridiagonal matrix ${\displaystyle J}$ by:[18]

${\displaystyle J:=D^{-1}TD={\begin{pmatrix}a_{1}&\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}\\\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}&a_{2}&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}\\&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}&\ddots &\ddots \\&&\ddots &\ddots &\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}\\&&&\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}&a_{n}\end{pmatrix}}\,.}$

Note that ${\displaystyle T}$ and ${\displaystyle J}$ have the same eigenvalues.

## Computer programming

A transformation that reduces a general matrix to Hessenberg form will reduce a Hermitian matrix to tridiagonal form. So, many eigenvalue algorithms, when applied to a Hermitian matrix, reduce the input Hermitian matrix to (symmetric real) tridiagonal form as a first step.[19]

A tridiagonal matrix can also be stored more efficiently than a general matrix by using a special storage scheme. For instance, the LAPACK Fortran package stores an unsymmetric tridiagonal matrix of order n in three one-dimensional arrays, one of length n containing the diagonal elements, and two of length n − 1 containing the subdiagonal and superdiagonal elements.

## Applications

The discretization in space of the one-dimensional diffusion or heat equation

${\displaystyle {\frac {\partial u(t,x)}{\partial t}}=\alpha {\frac {\partial ^{2}u(t,x)}{\partial x^{2}}}}$

using second order central finite differences results in

${\displaystyle {\begin{pmatrix}{\frac {\partial u_{1}(t)}{\partial t}}\\{\frac {\partial u_{2}(t)}{\partial t}}\\\vdots \\{\frac {\partial u_{N}(t)}{\partial t}}\end{pmatrix}}={\frac {\alpha }{\Delta x^{2}}}{\begin{pmatrix}-2&1&0&\ldots &0\\1&-2&1&\ddots &\vdots \\0&\ddots &\ddots &\ddots &0\\\vdots &&1&-2&1\\0&\ldots &0&1&-2\end{pmatrix}}{\begin{pmatrix}u_{1}(t)\\u_{2}(t)\\\vdots \\u_{N}(t)\\\end{pmatrix}}}$

with discretization constant ${\displaystyle \Delta x}$. The matrix is tridiagonal with ${\displaystyle a_{i}=-2}$ and ${\displaystyle b_{i}=c_{i}=1}$. Note: no boundary conditions are used here.

## Notes

1. ^ Thomas Muir (1960). A treatise on the theory of determinants. Dover Publications. pp. 516–525.
2. ^ Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. p. 28. ISBN 0521386322.
3. ^ Horn & Johnson, page 174
4. ^ El-Mikkawy, M. E. A. (2004). "On the inverse of a general tridiagonal matrix". Applied Mathematics and Computation. 150 (3): 669–679. doi:10.1016/S0096-3003(03)00298-4.
5. ^ Da Fonseca, C. M. (2007). "On the eigenvalues of some tridiagonal matrices". Journal of Computational and Applied Mathematics. 200: 283–286. doi:10.1016/j.cam.2005.08.047.
6. ^ Usmani, R. A. (1994). "Inversion of a tridiagonal jacobi matrix". Linear Algebra and its Applications. 212–213: 413–414. doi:10.1016/0024-3795(94)90414-6.
7. ^ Hu, G. Y.; O'Connell, R. F. (1996). "Analytical inversion of symmetric tridiagonal matrices". Journal of Physics A: Mathematical and General. 29 (7): 1511. doi:10.1088/0305-4470/29/7/020.
8. ^ Huang, Y.; McColl, W. F. (1997). "Analytical inversion of general tridiagonal matrices". Journal of Physics A: Mathematical and General. 30 (22): 7919. doi:10.1088/0305-4470/30/22/026.
9. ^ Mallik, R. K. (2001). "The inverse of a tridiagonal matrix". Linear Algebra and its Applications. 325: 109–139. doi:10.1016/S0024-3795(00)00262-7.
10. ^ Kılıç, E. (2008). "Explicit formula for the inverse of a tridiagonal matrix by backward continued fractions". Applied Mathematics and Computation. 197: 345–357. doi:10.1016/j.amc.2007.07.046.
11. ^ Raf Vandebril; Marc Van Barel; Nicola Mastronardi (2008). Matrix Computations and Semiseparable Matrices. Volume I: Linear Systems. JHU Press. Theorem 1.38, p. 41. ISBN 978-0-8018-8714-7.
12. ^ Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). The Johns Hopkins University Press. ISBN 0-8018-5414-8.
13. ^ Noschese, S.; Pasquini, L.; Reichel, L. (2013). "Tridiagonal Toeplitz matrices: Properties and novel applications". Numerical Linear Algebra with Applications. 20 (2): 302. doi:10.1002/nla.1811.
14. ^ This can also be written as ${\displaystyle a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})}$ because ${\displaystyle \cos(x)=-\cos(\pi -x)}$, as is done in: Kulkarni, D.; Schmidt, D.; Tsui, S. K. (1999). "Eigenvalues of tridiagonal pseudo-Toeplitz matrices" (PDF). Linear Algebra and its Applications. 297: 63. doi:10.1016/S0024-3795(99)00114-7.
15. ^ Parlett, B.N. (1980). The Symmetric Eigenvalue Problem. Prentice Hall, Inc.
16. ^ Coakley, E.S.; Rokhlin, V. (2012). "A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices". Applied and Computational Harmonic Analysis. 34 (3): 379–414. doi:10.1016/j.acha.2012.06.003.
17. ^ Dhillon, Inderjit Singh. A New O(n 2 ) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem (PDF). p. 8.
18. ^
19. ^ Eidelman, Yuli; Gohberg, Israel; Gemignani, Luca (2007-01-01). "On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms". Linear Algebra and its Applications. 420 (1): 86–101. doi:10.1016/j.laa.2006.06.028. ISSN 0024-3795.