7
$\begingroup$

What's the best way to invert a simple Toeplitz matrix of the following form?

$ A = \begin{bmatrix} 1 & a & 0 & \ldots & \ldots & 0 \\\ a & 1 & a & \ddots & & \vdots \\\ 0 & a & 1 & \ddots & \ddots& \vdots \\\ \vdots & \ddots & \ddots & \ddots & a & 0\\\ \vdots & & \ddots & a & 1 & a\\\ 0 & \ldots & \ldots & 0 & a & 1 \end{bmatrix} $

1 Answers 1

8

Usually, an eigendecomposition is the least efficient way to generate the inverse of a matrix, but in the case of the symmetric tridiagonal Toeplitz matrix, we have the nice eigendecomposition $\mathbf A=\mathbf V\mathbf D\mathbf V^\top$, where $\mathbf D=\mathrm{diag}\left(1+2a\cos\frac{\pi}{n+1},\dots,1+2a\cos\frac{k\pi}{n+1},\dots,1+2a\cos\frac{n\pi}{n+1}\right)$ and $\mathbf V$ is the symmetric and orthogonal matrix whose entries are $v_{j,k}=\sqrt{\frac2{n+1}}\sin\frac{\pi jk}{n+1}$ Thus, to generate the inverse, use $\mathbf A=\mathbf V\mathbf D^{-1}\mathbf V^\top$, and inverting a diagonal matrix is as easy as reciprocating the diagonal entries.