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, but they only differ by a rank 1 perturbation, and also enjoy some important algebraic properties. 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.

The inverse transform can be computed as follows. Firstly, direct computation shows

where , and is defined as

Hence the inverse of can be represented by its transpose:

therefore the inverse of can be computed as

As a result, we can also compute the inverse transform in time.