Tridiagonal matrix

From Free net encyclopedia

In linear algebra, a tridiagonal matrix is one that is "almost" diagonal. To be exact, a tridiagonal matrix has nonzero elements only in the main diagonal, the first diagonal below this, and the first diagonal above the main diagonal.

For example:

<math>\begin{pmatrix}

1 & 4 & 0 & 0 \\ 3 & 4 & 1 & 0 \\ 0 & 2 & 3 & 4 \\ 0 & 0 & 1 & 3 \\ \end{pmatrix}</math> is tridiagonal.

A tridiagonal matrix is Hessenberg. 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.

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

<math> \det A = a_{n,n} \det \, [A]_{\{1,\ldots,n-1\}} - a_{n,n-1} a_{n-1,n} \det \, [A]_{\{1,\ldots,n-2\}} \, ,\, </math>

where det <math>[A]_{\{1,\ldots,k\}}</math> denotes the kth principal minor, that is, <math>[A]_{\{1,\ldots,k\}}</math> 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.

A transformation that reduces a general matrix to Hessenberg form will reduce a Hermitian matrix to tridiagonal form. Thus, many eigenvalue algorithms, when applied to a Hermitian matrix, involve reduction 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.

[edit]