Tridiagonal matrix

In linear algebra, a tridiagonal matrix is a matrix that has nonzero elements only in the main diagonal, the first diagonal below this, and 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 a continuant of its elements.

Determining an orthogonal transformation to tridiagonal form can be done with the Lanczos algorithm.

Properties

A tridiagonal matrix is of Hessenberg type; 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, so that the signs of its entries are symmetric, then it is similar to a Hermitian matrix, and hence, its eigenvalues are real. The latter conclusion continues to hold if we replace the condition a_k,k+1 a_k+1,k > 0 by a_k,k+1 a_k+1,k ≥ 0.

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. For instance, the determinant of a tridiagonal matrix A of order n can be computed by the recursive formula for a continuant

$\det [A]_{\{1,\ldots,n\}} = a_{n,n} \det \, [A]_{\{1,\ldots,n-1\}} - a_{n,n-1} a_{n-1,n} \det \, [A]_{\{1,\ldots,n-2\}} \, ,\,$

where det $[A]_{\{1,\ldots,k\}}$ denotes the kth principal minor, that is, $[A]_{\{1,\ldots,k\}}$ is the submatrix formed by the first k rows and columns of A. 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.

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.

A system of tridiagonal matrix Ax = b, for $b\in \reals^n$ can be solved by a specific algorithm called Tridiagonal matrix algorithm, requiring O(n) operations (Golub and Van Loan).

References

• Roger A. Horn and Charles R. Johnson, Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2.
• Gene H. Golub and Charles F. Van Loan, Matrix Computations, 3rd ed., The Johns Hopkins University Press, 1996. ISBN 0-8018-5414-8.

External links

• Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
• Module for Tri-Diagonal Linear Systems
• Moawwad El-Mikkawy, Abdelrahman Karawia (2006). "Inversion of general tridiagonal matrices". Applied Mathematics Letters 19 (8): 712–720. doi:10.1016/j.aml.2005.11.012. http://app2.mans.edu.eg/eulc/Libraries/itemsAttach/IssueArticle/1037592/papermik.pdf. 
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form