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 ak,k+1ak+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+1ak+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 dimensionalvector 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, and let The sequence is called the continuant and satisfies the recurrence relation 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 is given by where the θi satisfy the recurrence relation with initial conditionsθ0 = 1, θ1 = a1 and the ϕi satisfy 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.
When a tridiagonal matrix is also Toeplitz, there is a simple closed-form solution for its eigenvalues, namely: A real symmetric tridiagonal matrix has real eigenvalues, and all the eigenvalues are distinct 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 operations for a matrix of size, although fast algorithms exist which require only. 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. For unsymmetric tridiagonal matrices one can compute the eigendecomposition using a similarity transformation.
Similarity to symmetric tridiagonal matrix
Given a real tridiagonal, nonsymmetic matrix where. Assume that each product of off-diagonal entries is strictly positive and define a transformation matrix by The similarity transformation yields a symmetric tridiagonal matrix by Note that and 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 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 LAPACKFortran 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.
