What's the best way to invert a simple symmetric tridiagonal 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}
$$
Best Answer
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.