What Is a Tridiagonal Matrix?

A tridiagonal matrix is a square matrix whose elements are zero away from the main diagonal, the subdiagonal, and the superdiagonal. In other words, it is a banded matrix with upper and lower bandwidths both equal to $1$ . It has the form

$\notag A = \begin{bmatrix} d_1 & e_1 & & &\\ c_2 & d_2 & e_2 & &\\ & c_3 & \ddots & \ddots &\\ & & \ddots & \ddots & e_{n-1}\\ & & & c_n & d_n \end{bmatrix} \in\mathbb{C}^{n\times n}.$

An important example is the matrix $T_n$ that arises in discretizating the Poisson partial differential equation by a standard five-point operator, illustrated for $n = 5$ by

$\notag T_5 = \left[ \begin{array}{@{}*{4}{r@{\mskip10mu}}r} 4 & -1 & & & \\ -1 & 4 & -1 & & \\ & -1 & 4 & -1 & \\ & & -1 & 4 & -1 \\ & & & -1 & 4 \end{array}\right].$

It is symmetric positive definite, diagonally dominant, a Toeplitz matrix, and an $M$ -matrix.

Tridiagonal matrices have many special properties and various algorithms exist that exploit their structure.

Symmetrization

It can be useful to symmetrize a matrix by transforming it with a diagonal matrix. The next result shows when symmetrization is possible by similarity.

Theorem 1. If $A\in\mathbb{R}^{n\times n}$ is tridiagonal and $c_i e_{i-1} > 0$ for all $i$ then there exists a diagonal $D\in\mathbb{R}^{n\times n}$ with positive diagonal elements such that $D^{-1}AD$ is symmetric, with $(i-1,i)$ element $(c_ie_{i-1})^{1/2}$ .

Proof. Let $D = \mathrm{diag}(\omega_i)$ . Equating $(i,i-1)$ and $(i-1,i)$ elements in the matrix $D^{-1}AD$ gives

$\notag c_i \displaystyle\frac{\omega_{i-1}}{\omega_i} = e_{i-1} \displaystyle\frac{\omega_i}{\omega_{i-1}}, \quad i = 2:n, \qquad(1)$

or

$\notag \biggl(\displaystyle\frac{\omega_{i-1}}{\omega_i}\biggr)^2 = \frac{e_{i-1} }{c_i}, \quad i = 2:n. \qquad (2)$

As long as $c_i e_{i-1} > 0$ for all $i$ we can set $\omega_1 = 1$ and solve (2) to obtain real, positive $\omega_i$ , $i = 2:n$ . The formula for the off-diagonal elements of the symmetrized matrix follows from (1) and (2).

LU Factorization

The LU factors of a tridiagonal matrix are bidiagonal:

$\notag L = \begin{bmatrix} 1 & & & & \\ \ell_2 & 1 & & & \\ & \ell_3 & 1 & & \\ & & \ddots & \ddots & \\ & & & \ell_n & 1 \end{bmatrix}, \quad U = \begin{bmatrix} u_1 & e_1 & & & \\ & u_2 & e_2 & & \\ & & \ddots & \ddots & \\ & & & \ddots & e_{n-1}\\ & & & & u_n \end{bmatrix}. \qquad (3)$

The equation $A = LU$ gives the recurrence

$\notag u_1 = d_1, \qquad \ell_i = c_i/u_{i-1}, \quad u_i = d_i - \ell_i e_{i-1}, \quad i=2\colon n. \qquad (4)$

The recurrence breaks down with division by zero if one of the leading principal submatrices $A(1:k,1:k)$ , $k = 1:n-1$ , is singular. In general, partial pivoting must be used to ensure existence and numerical stability, giving a factorization $PA = LU$ where $L$ has at most two nonzeros per column and $U$ has an extra superdiagonal. The growth factor $\rho_n$ is easily seen to be bounded by $2$ .

For a tridiagonal Toeplitz matrix

$\notag T_n(c,d,e) = \begin{bmatrix} d & e & & \\ c & d & \ddots & \\ & \ddots & \ddots & e \\ & & c & d \end{bmatrix} \in\mathbb{C}^{n\times n} \qquad (5)$

the elements of the LU factors converge as $n\to\infty$ if $A$ is diagonally dominant.

Theorem 2. Suppose that $T_n(c,d,e)$ has an LU factorization with LU factors (3) and that $ce > 0$ and $|d| \ge 2\sqrt{ce}$ . Then $|u_j|$ decreases monotonically and

$\notag \lim_{n\to \infty}u_n = \frac{1}{2} \Bigl(d + \mathrm{sign}(d) \sqrt{ d^2 - 4ce } \Bigr).$

From (4), it follows that under the conditions of Theorem 2, $|\ell_i|$ increases monotonically and $\lim_{n\to\infty}\ell_n = e/\lim_{n\to\infty}u_n$ . Note that the conditions of Theorem 2 are satisfied if $A$ is diagonally dominant by rows, since $ce> 0$ implies $d \ge c + e \ge 2\sqrt{ce}$ . Note also that if we symmetrize $A$ using Theorem 1 then we obtain the matrix $T_n(\sqrt{ce},d, \sqrt{ce})$ , which is irreducibly diagonally dominant and hence positive definite if $d > 0$ .

Inverse

The inverse of a tridiagonal matrix is full, in general. For example,

$\notag T_5(-1,3,-1)^{-1} = \left[\begin{array}{rrrrr} 3 & -1 & 0 & 0 & 0\\ -1 & 3 & -1 & 0 & 0\\ 0 & -1 & 3 & -1 & 0\\ 0 & 0 & -1 & 3 & -1\\ 0 & 0 & 0 & -1 & 3 \end{array}\right]^{-1} = \frac{1}{144} \left[\begin{array}{ccccc} 55 & 21 & 8 & 3 & 1 \\ 21 & 63 & 24 & 9 & 3 \\ 8 & 24 & 64 & 24 & 8 \\ 3 & 9 & 24 & 63 & 21\\ 1 & 3 & 8 & 21 & 55 \end{array}\right].$

Since an $n\times n$ tridiagonal matrix depends on only $3n-2$ parameters, the same must be true of its inverse, meaning that there must be relations between the elements of the inverse. Indeed, in $T_5(-1,3,-1)^{-1}$ any $2\times 2$ submatrix whose elements lie in the upper triangle is singular, and the $(1:3,3:5)$ submatrix is also singular. The next result explains this special structure. We note that a tridiagonal matrix is irreducible if $a_{i+1,i}$ and $a_{i,i+1}$ are nonzero for all $i$ .

Theorem 3. If $A\in\mathbb{C}^{n\times n}$ is tridiagonal, nonsingular, and irreducible then there are vectors $u$ , $v$ , $x$ , and $y$ , all of whose elements are nonzero, such that

$\notag (A^{-1})_{ij} = \begin{cases} u_iv_j, & i\le j,\\ x_iy_j, & i\ge j.\\[4pt] \end{cases}$

The theorem says that the upper triangle of the inverse agrees with the upper triangle of a rank- $1$ matrix ( $uv^T$ ) and the lower triangle of the inverse agrees with the lower triangle of another rank- $1$ matrix ( $xy^T$ ). This explains the singular submatrices that we see in the example above.

If a tridiagonal matrix $A$ is reducible with $a_{k,k+1} = 0$ then it has the block form

$\notag \begin{bmatrix} A_{11} & 0 \\ A_{21} & A_{22} \end{bmatrix},$

where $A_{21} = a_{k+1,k}e_1e_k^T$ , and so

$\notag \begin{bmatrix} A_{11}^{-1} & 0 \\ - A_{22}^{-1} A_{21} A_{11}^{-1} & A_{22}^{-1} \end{bmatrix},$

in which the $(2,1)$ block is rank $1$ if $a_{k+1,k}\ne 0$ . This blocking can be applied recursively until Theorem 1 can be applied to all the diagonal blocks.

The inverse of the Toeplitz tridiagonal matrix $T_n(a,b,c)$ is known explicitly; see Dow (2003, Sec. 3.1).

Eigenvalues

The most widely used methods for finding eigenvalues and eigenvectors of Hermitian matrices reduce the matrix to tridiagonal form by a finite sequence of unitary similarity transformations and then solve the tridiagonal eigenvalue problem. Tridiagonal eigenvalue problems also arise directly, for example in connection with orthogonal polynomials and special functions.

The eigenvalues of the Toeplitz tridiagonal matrix $T_n(c,d,e)$ in (5) are given by

$\notag d + 2 (ce)^{1/2} \cos\biggl( \displaystyle\frac{k \pi}{n+1} \biggr), \quad k = 1:n. \qquad (6)$

The eigenvalues are also known for certain variations of the symmetric matrix $T_n(c,d,c)$ in which the $(1,1)$ and $(n,n)$ elements are modified (Gregory and Karney, 1969).

Some special results hold for the eigenvalues of general tridiagonal matrices. A matrix is derogatory if an eigenvalue appears in more than one Jordan block in the Jordan canonical form, and nonderogatory otherwise.

Theorem 4. If $A\in\mathbb{C}^{n\times n}$ is an irreducible tridiagonal matrix then it is nonderogatory.

Proof. Let $G = A - \lambda I$ , for any $\lambda$ . The matrix $G(1:n-1,2:n)$ is lower triangular with nonzero diagonal elements $e_1, \dots, e_{n-1}$ and hence it is nonsingular. Therefore $G$ has rank at least $n-1$ for all $\lambda$ . If $A$ were derogatory then the rank of $G$ would be at most $n-2$ when $\lambda$ is an eigenvalue, so $A$ must be nonderogatory.

Corollary 5. If $A\in\mathbb{R}^{n\times n}$ is tridiagonal with $c_i e_{i-1} > 0$ for all $i$ then the eigenvalues of $A$ are real and simple.

Proof. By Theorem 1 the eigenvalues of $A$ are those of the symmetric matrix $S = D^{-1}AD$ and so are real. The matrix $S$ is tridiagonal and irreducible so it is nonderogatory by Theorem 4, which means that its eigenvalues are simple because it is symmetric.

The formula (6) confirms the conclusion of Corollary 5 for tridiagonal Toeplitz matrices.

Corollary 5 guarantees that the eigenvalues are distinct but not that they are well separated. The spacing of the eigenvalues in (6) clearly reduces as $n$ increases. Wilkinson constructed a symmetric tridiagonal matrix called $W_n^+$ , defined by

$\notag \begin{aligned} d_i &= \frac{n+1}{2} - i = d_{n-i+1}, \quad i = 1:n/2, \qquad d_{(n+1)/2} = 0 \quad \mathrm{if}~n~\mathrm{is~odd}, \\ c_i &= e_{i-1} = 1. \end{aligned}$

For example,

$\notag W_5^+ = \left[\begin{array}{ccccc} 2 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 2 \end{array}\right].$

Here are the two largest eigenvalues of $W_{21}^+$ , as computed by MATLAB.

>> A = anymatrix('matlab/wilkinson',21); 
>> e = eig(A); e([20 21])
ans =
  10.746194182903322
  10.746194182903393

These eigenvalues (which are correct to the digits shown) agree almost to the machine precision.

Notes

Theorem 2 is obtained for symmetric matrices by Malcolm and Palmer (1974), who suggest saving work in computing the LU factorization by setting $u_j = u_k$ for $j > k$ once $u_k$ is close enough to the limit.

A sample reference for Theorem 3 is Ikebe (1979), which is one of many papers on inverses of banded matrices.

The eigenvectors of a symmetric tridiagonal matrix satisfy some intricate relations; see Parlett (1998, sec. 7.9).

References

This is a minimal set of references, which contain further useful references within.

Murray Dow, Explicit Inverses of Toeplitz and Associated Matrices, ANZIAM J. 44, E185–E215, 2003.
Robert Gregory and David Karney, A Collection of Matrices for Testing Computational Algorithms, Wiley, 1969.
Yasuhiko Ikebe, On inverses of Hessenberg matrices. Linear Algebra Appl., 24:93–97, 1979.
Michael A. Malcolm and John Palmer, A Fast Method for Solving a Class of Tridiagonal Linear Systems, Comm. ACM 17, 14–17, 1974.
Beresford Parlett, The Symmetric Eigenvalue Problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1998.
J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, 1965, Section 5.45.

What Is a Tridiagonal Matrix?

Symmetrization

LU Factorization

Inverse

Eigenvalues

Notes

References

Related Blog Posts

Leave a Reply Cancel reply

Symmetrization

LU Factorization

Inverse

Eigenvalues

Notes

References

Related Blog Posts

Share this:

Related

Leave a Reply Cancel reply