# 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:

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*_{1} = |*a*_{1}| = *a*_{1} and

The sequence (*f*_{i}) is called the continuant and satisfies the recurrence relation

with initial values *f*_{0} = 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*

is given by

where the *θ*_{i} satisfy the recurrence relation

with initial conditions *θ*_{0} = 1, *θ*_{1} = *a*_{1} and the *ϕ*_{i} satisfy

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 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
,
for ^{[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.

## See also

## 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 because , 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++