Abrazolica

This post will show how to invert a tridiagonal matrix in spectral decomposition form. This is a convenient form if you're only interested in one particular element of the inverse and want it as a sum of terms involving the eigenvalues of the matrix.

For any matrix \(\mathbf{A}\) with eigenvalues \(x_k\) and eigenvectors \(\lvert v_k \rangle\) such that:

\[\mathbf{A}\lvert v_k \rangle=x_k\lvert v_k \rangle\]

We can write \(\mathbf{A}\) in spectral decomposition form as:

\[\mathbf{A}=\sum_k x_k \lvert v_k \rangle \langle v_k \rvert\]

Since the inverse of \(\mathbf{A}\) has the same eigenvectors but reciprocal eigenvalues we can likewise write the inverse as:

\[\mathbf{A^{-1}}=\sum_k \frac{\lvert v_k \rangle \langle v_k \rvert}{x_k}\]

Expressing the inverse in this form is often quite useful especially when the eigenvalues and vectors of \(\mathbf{A}\) are known or can easily be calculated. One type of matrix where the eigenvalues and vectors are easily calculated is a Tridiagonal matrix with constant diagonals. A general matrix of this type is \(\mathbf{A}=\mathbf{tridiag}(c,a,b)\) which in the \(n=4\) dimensional case would look like:

\[\begin{pmatrix}a & b & 0 & 0\\c & a & b & 0\\0 & c & a & b\\0 & 0 & c & a\end{pmatrix}\]

The matrix can be made symmetric with a similarity transform

\[\mathbf{B} = \mathbf{S}^{-1}\mathbf{A}\mathbf{S} = \begin{pmatrix}a & \sqrt{bc} & 0 & 0\\\sqrt{bc} & a &\sqrt{bc} & 0\\0 & \sqrt{bc} & a & \sqrt{bc}\\0 & 0 & \sqrt{bc} & a\end{pmatrix}\]

where \(\mathbf{S}\) is the diagonal matrix

\[\mathbf{S} = \begin{pmatrix}1 & 0 & 0 & 0\\0 & (c/b)^{1/2} & 0 & 0\\0 & 0 & c/b & 0\\0 & 0 & 0 & (c/b)^{3/2}\end{pmatrix}\]

How does this affect the eigenvalues? We can write the eigenvalue equation as \(\mathbf{S}^{-1}\mathbf{A}\mathbf{S}\mathbf{S}^{-1}\lvert v_k \rangle=x_k\mathbf{S}^{-1}\lvert v_k \rangle\) or \(\mathbf{B}\mathbf{S}^{-1}\lvert v_k \rangle=x_k\mathbf{S}^{-1}\lvert v_k \rangle\). Therefor \(\mathbf{B}\) has the same eigenvalues as \(\mathbf{A}\) but the eigenvectors become \(\mathbf{S}^{-1}\lvert v_k \rangle\). Let \(\lvert u_k \rangle=\mathbf{S}^{-1}\lvert v_k \rangle\) then the eigenvalue equation for \(\mathbf{B}\) is \(\mathbf{B}\lvert u_k \rangle=x_k\lvert u_k \rangle\). By dividing this equation by \(\sqrt{bc}\) we can simplify the matrix to

\[\mathbf{C} = \mathbf{B}/\sqrt{bc} = \begin{pmatrix}\alpha & 1 & 0 & 0\\1 & \alpha & 1 & 0\\0 & 1 & \alpha & 1\\0 & 0 & 1 & \alpha\end{pmatrix}\]

where \(\alpha=a/\sqrt{bc}\). The eigenvalues similarly become \(y_k=x_k/\sqrt{bc}\) and now we have the eigenvalue equation \(\mathbf{C}\lvert u_k \rangle=y_k\lvert u_k \rangle\). The eigenvalues \(y_k\) are roots of the determinant \(p(y)=\mathrm{det}(y\mathbf{I}-\mathbf{C})\). Let \(p_n(y)\) be this determinant when \(\mathbf{C}\) has dimension \(n\) then the determinant can be calculated recursively using the equation

\[p_n(y)=(y-\alpha)p_{n-1}(y)-p_{n-2}(y)\]

with initial values \(p_0(y)=1\), \(p_1(y)=y-\alpha\). This equation can easily be found using the expansion theorem for determinants.

With the change in variables \(2z=y-\alpha\) the equation becomes the recurrence for the Type II Chebyshev polynomials:

\[U_n(z)=2zU_{n-1}(z)-U_{n-2}(z)\]

whose roots can easily be found. Letting \(z=\cos{\theta}\) we have

\[U_n(\theta)=\frac{\sin{(n+1)\theta}}{\sin{\theta}}\]

The roots of \(U_n(\theta)\) occur at \(\theta_k=k\pi/(n+1)\) therefor the corresponding roots for \(p_n(y)\) are at:

\[y_k=\alpha+2z_k=\alpha+2\cos{\theta_k}\]

These are the eigenvalues for the matrix \(\mathbf{C}\). The eigenvalues for the matrices \(\mathbf{A}\) and \(\mathbf{B}\) are

\[x_k=\sqrt{bc}y_k=a+2\sqrt{bc}\cos{\theta_k}\]

The only thing still needed to construct the inverse is the eigenvectors. The nice thing about symmetric tridiagonal matrices is that they all have the same eigenvectors. The \(i^{\mathrm{th}}\) component of the \(k^{\mathrm{th}}\) eigenvector is given by:

\[\lvert u_k \rangle_i=u_{i,k}=\sqrt{\frac{2}{n+1}}\sin{\frac{ik\pi}{n+1}}\]

We will not derive this result because it is quite easy to verify given the formula for the eigenvalues we derived above. The eigenvectors for the nonsymmetric matrix \(\mathbf{A}\) are then equal to \(\lvert v_k \rangle=\mathbf{S}\lvert u_k \rangle\) where \(\mathbf{S}\) is the diagonal matrix defined above.

In the next post I will show an interesting application of this.