Jacobi Matrices

A Jacobi matrix is a symmetric tridiagonal matrix with the following form:

More generally, a Jacobi operator is a symmetric linear operator acting on sequences which is given by an infinite tridiagonal matrix. It is commonly used to specify systems of orthonormal polynomials over a finite, positive Borel measure. The name derives from a theorem from Jacobi, dating to 1848, stating that every symmetric matrix over a principal ideal domain is congruent to a tridiagonal matrix.

Algebraic Properties

Given a series of orthonormal polynomials with respect to the following three-term recurrence relation:

then the corresponding Jacobi matrix is defined in .

A simple calculation shows that the determinant of the Jacobi matrix satisfies the following recurrence relation:

Let , then the above equation can be rewritten as

and this is the three-term recurrence relation gives another traditional matrix

In fact, we can show that

and is the monic version of . As a result, the eigenvalues of are the roots of , as well as the roots of .

Lanczos Alogorithm

Multiplication Matrix

The multiplication matrix of Chebyshev polynomials is defined as

which is NOT a Jacobi matrix since it’s not symmetric. However, and the Jacobi matrix are closely related. In fact, we can show that the eigenvalues of are the roots of the Chebyshev polynomial , that is, the first kind of Chebyshev points, and the eigenvectors of are scaled values of the Chebyshev polynomials at the first kind of Chebyshev points:

where

and

To see this, we suppose , then gives

Assume , then we have

hence above recurrence relation gives

Furthermore, note that

therefore we can express the product as

Recall the DCT-II (Discrete Cosine Transform of type II)

can be computed in time, we can compute the product in time.