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:

{\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 a_k,k+1 a_k+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 a_k,k+1 a_k+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 f₁ = |a₁| = a₁ (i.e., f₁ is the determinant of the 1 by 1 matrix consisting only of a₁), and let

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 (f_i) is called the continuant and satisfies the recurrence relation

f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}

with initial values f₀ = 1 and f₋₁ = 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

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

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

where the θ_i satisfy the recurrence relation

\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 θ₀ = 1, θ₁ = a₁ and the ϕ_i satisfy

\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 = a_n.^[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] The inverse of a symmetric tridiagonal matrix can be written as a single-pair matrix (a.k.a. generator-representable semiseparable matrix) of the form^[12]^[13]

${\begin{pmatrix}\alpha _{1}&-\beta _{1}\\-\beta _{1}&\alpha _{2}&-\beta _{2}\\&\ddots &\ddots &\ddots &\\&&\ddots &\ddots &-\beta _{n-1}\\&&&-\beta _{n-1}&\alpha _{n}\end{pmatrix}}^{-1}={\begin{pmatrix}a_{1}b_{1}&a_{1}b_{2}&\cdots &a_{1}b_{n}\\a_{1}b_{2}&a_{2}b_{2}&\cdots &a_{2}b_{n}\\\vdots &\vdots &\ddots &\vdots \\a_{1}b_{n}&a_{2}b_{n}&\cdots &a_{n}b_{n}\end{pmatrix}}=\left(a_{\min(i,j)}b_{\max(i,j)}\right)$

where ${\begin{cases}\displaystyle a_{i}={\frac {\beta _{i}\cdots \beta _{n-1}}{\delta _{i}\cdots \delta _{n}\,b_{n}}}\\\displaystyle b_{i}={\frac {\beta _{1}\cdots \beta _{i-1}}{d_{1}\cdots d_{i}}}\end{cases}}$ with ${\begin{cases}d_{n}=\alpha _{n},\quad d_{i-1}=\alpha _{i-1}-{\frac {\beta _{i-1}^{2}}{d_{i}}},&i=n,n-1,\cdots ,2,\\\delta _{1}=\alpha _{1},\quad \delta _{i+1}=\alpha _{i+1}-{\frac {\beta _{i}^{2}}{\delta _{i}}},&i=1,2,\cdots ,n-1.\end{cases}}$

Solution of linear system

A system of equations Ax = b for $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.^[14]

Eigenvalues

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

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.^[17] Numerous methods exist for the numerical computation of the eigenvalues of a real symmetric tridiagonal matrix to arbitrary finite precision, typically requiring $O(n^{2})$ operations for a matrix of size $n\times n$ , although fast algorithms exist which (without parallel computation) require only $O(n\log n)$ .^[18]

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.^[19]

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

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 $b_{i}\neq c_{i}$ . Assume that each product of off-diagonal entries is strictly positive $b_{i}c_{i}>0$ and define a transformation matrix $D$ by^[20]

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 $D^{-1}TD$ yields a symmetric tridiagonal matrix $J$ by:^[21]^[20]

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 $T$ and $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.^[22]

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

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

{\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 $\Delta x$ . The matrix is tridiagonal with $a_{i}=-2$ and $b_{i}=c_{i}=1$ . Note: no boundary conditions are used here.

Notes

^ Thomas Muir (1960). A treatise on the theory of determinants. Dover Publications. pp. 516–525.
^ Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. p. 28. ISBN 0521386322.
^ Horn & Johnson, page 174
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ Meurant, Gerard (1992). "A review on the inverse of symmetric tridiagonal and block tridiagonal matrices". SIAM Journal on Matrix Analysis and Applications. 13 (3): 707–728. doi:10.1137/0613045.
^ Bossu, Sebastien (2024). "Tridiagonal and single-pair matrices and the inverse sum of two single-pair matrices". Linear Algebra and its Applications. 699: 129–158. arXiv:2304.06100. doi:10.1016/j.laa.2024.06.018.
^ Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). The Johns Hopkins University Press. ISBN 0-8018-5414-8.
^ 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.
^ This can also be written as $a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})$ because $\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.
^ Parlett, B.N. (1997) [1980]. The Symmetric Eigenvalue Problem. Classics in applied mathematics. Vol. 20. SIAM. ISBN 0-89871-402-8. OCLC 228147822.
^ 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.
^ Dhillon, Inderjit Singh (1997). A New O(n²) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem (PDF) (PhD). University of California, Berkeley. p. 8. CSD-97-971, ADA637073.
^ ^a ^b Kreer, M. (1994). "Analytic birth-death processes: a Hilbert space approach". Stochastic Processes and their Applications. 49 (1): 65–74. doi:10.1016/0304-4149(94)90112-0.
^ Meurant, Gérard (October 2008). "Tridiagonal matrices" (PDF) – via Institute for Computational Mathematics, Hong Kong Baptist University.
^ 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.

External links

Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
Moawwad El-Mikkawy, Abdelrahman Karawia (2006). "Inversion of general tridiagonal matrices" (PDF). Applied Mathematics Letters. 19 (8): 712–720. doi:10.1016/j.aml.2005.11.012. Archived from the original (PDF) on 2011-07-20.
High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
Tridiagonal linear system solver in C++

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

[VandebrilBarel2008-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.

[Meurant1992-12] Meurant, Gerard (1992). "A review on the inverse of symmetric tridiagonal and block tridiagonal matrices". SIAM Journal on Matrix Analysis and Applications. 13 (3): 707–728. doi:10.1137/0613045.

[13] Bossu, Sebastien (2024). "Tridiagonal and single-pair matrices and the inverse sum of two single-pair matrices". Linear Algebra and its Applications. 699: 129–158. arXiv:2304.06100. doi:10.1016/j.laa.2024.06.018.

[14] Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). The Johns Hopkins University Press. ISBN 0-8018-5414-8.

[15] 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.

[16] This can also be written as $a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})$ because $\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.

[17] Parlett, B.N. (1997) [1980]. The Symmetric Eigenvalue Problem. Classics in applied mathematics. Vol. 20. SIAM. ISBN 0-89871-402-8. OCLC 228147822.

[18] 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.

[19] Dhillon, Inderjit Singh (1997). A New O(n²) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem (PDF) (PhD). University of California, Berkeley. p. 8. CSD-97-971, ADA637073.

[kreer_operator-20] Kreer, M. (1994). "Analytic birth-death processes: a Hilbert space approach". Stochastic Processes and their Applications. 49 (1): 65–74. doi:10.1016/0304-4149(94)90112-0.

[21] Meurant, Gérard (October 2008). "Tridiagonal matrices" (PDF) – via Institute for Computational Mathematics, Hong Kong Baptist University.

[22] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

v t e Matrix classes
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz-stable Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Routh-Hurwitz Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematics portal List of matrices Category:Matrices