Tridiagonal matrix

Template:Short description 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:

$\left(\begin{array}{cccc}1& 4& 0& 0\\ 3& 4& 1& 0\\ 0& 2& 3& 4\\ 0& 0& 1& 3\end{array}\right).$

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 Template:Nowrap — 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

Template:Main The determinant of a tridiagonal matrix A of order n can be computed from a three-term recurrence relation. Write f₁ = |a₁| = a₁ (i.e., f₁ is the determinant of the 1 by 1 matrix consisting only of a₁), and let

$f_n=\left|\begin{array}{cc}{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{array}\right|.$

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=\left(\begin{array}{cc}{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{array}\right)$

is given by

$(T^{-1}{)}_{ij}=\{\begin{array}{cc}(-1{)}^{i+j}{b}_i\cdots b_{j-1}{\theta }_{i-1}{\varphi }_{j+1}/{\theta }_n& \text{ if }i<j\\ {\theta }_{i-1}{\varphi }_{j+1}/{\theta }_n& \text{ if }i=j\\ (-1{)}^{i+j}{c}_j\cdots c_{i-1}{\theta }_{j-1}{\varphi }_{i+1}/{\theta }_n& \text{ if }i>j\end{array}$

where the θ_i satisfy the recurrence relation

${\theta }_i=a_i{\theta }_{i-1}-b_{i-1}{c}_{i-1}{\theta }_{i-2}i=2,3,\dots ,n$

with initial conditions θ₀ = 1, θ₁ = a₁ and the ϕ_i satisfy

${\varphi }_i=a_i{\varphi }_{i+1}-b_i{c}_i{\varphi }_{i+2}i=n-1,\dots ,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

${\left(\begin{array}{cc}{\alpha }_1& -{\beta }_1\\ -{\beta }_1& {\alpha }_2& -{\beta }_2\\ & \ddots & \ddots & \ddots & \\ & & \ddots & \ddots & -{\beta }_{n-1}\\ & & & -{\beta }_{n-1}& {\alpha }_n\end{array}\right)}^{-1}=\left(\begin{array}{cccc}{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\\ ⋮& ⋮& \ddots & ⋮\\ a_1{b}_n& a_2{b}_n& \cdots & a_n{b}_n\end{array}\right)=\left(a_{min(i,j)}{b}_{max(i,j)}\right)$

where $\{\begin{array}{c}{a}_i=\frac{{\beta }_i\cdots {\beta }_{n-1}}{{\delta }_i\cdots {\delta }_n{b}_n}\\ b_i=\frac{{\beta }_1\cdots {\beta }_{i-1}}{d_1\cdots d_i}\end{array}$ with $\{\begin{array}{cc}{d}_n={\alpha }_n,d_{i-1}={\alpha }_{i-1}-\frac{{\beta }_{i-1}^2}{d_i},& i=n,n-1,\cdots ,2,\\ {\delta }_1={\alpha }_1,{\delta }_{i+1}={\alpha }_{i+1}-\frac{{\beta }_i^2}{{\delta }_i},& i=1,2,\cdots ,n-1.\end{array}$

Solution of linear system

Template:Main A system of equations Ax = b for $b\in {ℝ}^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),k=1,\dots ,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=\left(\begin{array}{cc}{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{array}\right)$

where $b_i\ne c_i$. Assume that each product of off-diagonal entries is Template:Em positive $b_i{c}_i>0$ and define a transformation matrix $D$ by

$D:=\mathrm{diag}({\delta }_1,\dots ,{\delta }_n)\text{for}{\delta }_i:=\{\begin{array}{cc}1& ,i=1\\ \sqrt{\frac{c_{i-1}\dots c_1}{b_{i-1}\dots b_1}}& ,i=2,\dots ,n.\end{array}$

The similarity transformation $D^{-1}TD$ yields a symmetric tridiagonal matrix $J$ by:

$J:=D^{-1}TD=\left(\begin{array}{cc}{a}_1& \mathrm{sgn}{b}_1\sqrt{b_1{c}_1}\\ \mathrm{sgn}{b}_1\sqrt{b_1{c}_1}& a_2& \mathrm{sgn}{b}_2\sqrt{b_2{c}_2}\\ & \mathrm{sgn}{b}_2\sqrt{b_2{c}_2}& \ddots & \ddots \\ & & \ddots & \ddots & \mathrm{sgn}{b}_{n-1}\sqrt{b_{n-1}{c}_{n-1}}\\ & & & \mathrm{sgn}{b}_{n-1}\sqrt{b_{n-1}{c}_{n-1}}& a_n\end{array}\right).$

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

$\left(\begin{array}{c}\frac{\partial u_1(t)}{\partial t}\\ \frac{\partial u_2(t)}{\partial t}\\ ⋮\\ \frac{\partial u_N(t)}{\partial t}\end{array}\right)=\frac{\alpha }{\mathrm{\Delta }{x}^2}\left(\begin{array}{ccccc}-2& 1& 0& \dots & 0\\ 1& -2& 1& \ddots & ⋮\\ 0& \ddots & \ddots & \ddots & 0\\ ⋮& & 1& -2& 1\\ 0& \dots & 0& 1& -2\end{array}\right)\left(\begin{array}{c}{u}_1(t)\\ u_2(t)\\ ⋮\\ u_N(t)\end{array}\right)$

with discretization constant $\mathrm{\Delta }x$. The matrix is tridiagonal with $a_i=-2$ and $b_i=c_i=1$. Note: no boundary conditions were explicitly assigned, but this matrix happens to correspond to Neumann boundary conditions (zero gradient).

See also

• Pentadiagonal matrix
• Jacobi matrix (operator)

External links

• Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
• Template:Cite journal
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
• Tridiagonal linear system solver in C++