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 — 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
ak,
k+1
ak+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
ak,
k+1
ak+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
f1 = |
a1| =
a1 (i.e.,
f1 is the determinant of the 1 by 1 matrix consisting only of
a1), 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 (
fi) 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
f0 = 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 j\\ \end{cases} Correction!? --> :(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\\ \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 =
a1 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 =
an. 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 \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 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} T D yields a
symmetric tridiagonal matrix J by: : J:=D^{-1} T D = \begin{pmatrix} a_1 & \sgn b_1 \, \sqrt{b_1 c_1} \\ \sgn b_1 \, \sqrt{b_1 c_1} & a_2 & \sgn b_2 \, \sqrt{b_2 c_2} \\ & \sgn b_2 \, \sqrt{b_2 c_2} & \ddots & \ddots \\ & & \ddots & \ddots & \sgn b_{n-1} \, \sqrt{b_{n-1} c_{n-1}} \\ & & & \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==