# 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.
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. 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.
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. Write f$_1$ = |a$_1$| = a$_1$ (i.e., f$_1$ is the determinant of the 1 by 1 matrix consisting only of a$_1$), 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$_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
    $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 θ$_0$ = 1, θ$_1$ = a$_1$ 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$.
Closed form solutions can be computed for special cases such as symmetric matrices with all diagonal and off-diagonal elements equal or Toeplitz matrices and for the general case as well.
In general, the inverse of a tridiagonal matrix is a semiseparable matrix and vice versa. 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
${\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.

### Eigenvalues

When a tridiagonal matrix is also Toeplitz, there is a simple closed-form solution for its eigenvalues, namely:
    $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. 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)$.
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.

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