Tridiagonal matrix

In linear algebra, a tridiagonal matrix is a matrix that has nonzero elements only on the main diagonal, the first diagonal below this, and 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

{{#invoke:main|main}} The determinant of a tridiagonal matrix A of order n can be computed from a three-term recurrence relation.^[4] Write f₁ = |a₁| = a₁ and

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

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\leq 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}\quad {\text{ for }}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}\quad {\text{ for }}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 off-diagonal elements equal^[7] or Toeplitz matrices^[8] and for the general case as well.^[9]^[10]

Solution of linear system

{{#invoke:main|main}} A system of equations A x = b for $\scriptstyle 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.^[11]

Eigenvalues

When a tridiagonal matrix is also Toeplitz, there is a simple closed-form solution for its eigenvalues, namely $a+2{\sqrt {bc}}\,\cos(k\pi /{(n+1)})$ , for $k=1,...,n.$ ^[12]^[13]

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 tridiagonal form as a first step.

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.

Notes

↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
↑ Horn & Johnson, page 174
↑ Template:Cite doi
↑ Template:Cite doi
↑ Template:Cite doi
↑ Template:Cite doi
↑ Template:Cite doi
↑ Template:Cite doi
↑ Template:Cite doi
↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
↑ Template:Cite doi
↑ 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: Template:Cite doi

External links

Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
Module for Tri-Diagonal Linear Systems
{{#invoke:Citation/CS1|citation

|CitationClass=journal }}

High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
Tridiagonal linear system solver in C++

[1] {{#invoke:citation/CS1|citation |CitationClass=book }}

[2] {{#invoke:citation/CS1|citation |CitationClass=book }}

[3] Horn & Johnson, page 174

[4] Template:Cite doi

[5] Template:Cite doi

[6] Template:Cite doi

[7] Template:Cite doi

[8] Template:Cite doi

[9] Template:Cite doi

[10] Template:Cite doi

[11] {{#invoke:citation/CS1|citation |CitationClass=book }}

[12] Template:Cite doi

[13] 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: Template:Cite doi

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Tridiagonal matrix

Contents