Inverse of a symmetric tridiagonal matrix.

Hello, everyone!
I am trying to find the inverse of an $N\times N$ matrix with ones on the diagonal and $-\frac{1}{2}$ in all entries of the subdiagonal and superdiagonal. For example, with $N=3$, $$A = \left(\begin{array}{ccc}1 & -1/2 & 0 \\ -1/2 & 1 & -1/2 \\ 0 & -1/2 & 1 \end{array}\right);\,\,A^{-1} = \left(\begin{array}{ccc}3/2 & 1 & 1/2 \\ 1 & 2 & 1 \\ 1/2 & 1 & 3/2 \end{array}\right).$$ In fact, I really only need to determine the value of the first entry. I believe that it should be $\frac{2N}{N+1}$, but that is only by a heuristic method, when I'm really hoping for a proof by induction.

Thanks in advance for any assistance.

-Jason

We know that if a matrix $A \in \mathbb{M}_N(\mathbb{R})$ is invertible its inverse can be written as

$${A^{ - 1}} = \frac{1}{{\det \left( A \right)}}{C^T}$$

where $$C = \left[ {\begin{array}{*{20}{c}}{{C_{11}}}&{{C_{12}}}& \cdots &{{C_{1N}}}\\{{C_{21}}}&{{C_{22}}}& \cdots &{{C_{2N}}}\\ \vdots & \vdots & \ddots & \vdots \\{{C_{N1}}}&{{C_{N2}}}& \cdots &{{C_{NN}}}\end{array}} \right]$$

is the cofactor matrix. In case you don't remember/know, the $(i,j)$-cofactor is defined by $${C_{ij}} = {\left( { - 1} \right)^{i + j}}{M_{i,j}}$$ being $M_{i,j}$ the $(i,j)$-minor, which is by definition the determinant of the submatrix formed by deleting the i-th row and j-th column of $A$.

Now, let's consider $${A_N} = {\left[ {\begin{array}{*{20}{c}}1&{ - 1/2}&0& \cdots &0&0\\{ - 1/2}&1&{ - 1/2}& \cdots &0&0\\0&{ - 1/2}&1& \ddots &0&0\\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\0&0&0& \cdots &1&{ - 1/2}\\0&0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{N \times N}}$$ As you are only interested in the first entry of $A^{-1}_{N}$, we are done if we can find $C_{11}$ and $\det \left( A_{N} \right)$, as $${\left( {A_N^{ - 1}} \right)_{1,1}} = \frac{{{C_{11}}}}{{\det \left( {{A_N}} \right)}}.$$

Taking $a_{N}=\det \left( {{A_N}} \right)$ and applying Laplace's expansion along the first row we get $$\begin{array}{c}{a_N} = \det {\left[ {\begin{array}{*{20}{c}}1&{ - 1/2}&0&0& \cdots &0&0\\{ - 1/2}&1&{ - 1/2}&0& \cdots &0&0\\0&{ - 1/2}&1&{ - 1/2}& \cdots &0&0\\ \vdots & \vdots & \vdots & \vdots & \cdots & \vdots & \vdots \\0&0&0&0& \cdots &1&{ - 1/2}\\0&0&0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{\left( {N - 1} \right) \times \left( {N - 1} \right)}}\\ + \frac{1}{2}\det {\left[ {\begin{array}{*{20}{c}}{ - 1/2}&{ - 1/2}&0& \cdots &0&0\\0&1&{ - 1/2}& \cdots &0&0\\ \vdots & \vdots & \vdots & \cdots & \vdots & \vdots \\0&0&0& \cdots &1&{ - 1/2}\\0&0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{\left( {N - 1} \right) \times \left( {N - 1} \right)}}\end{array}$$ But $$\det {\left[ {\begin{array}{*{20}{c}}1&{ - 1/2}&0&0& \cdots &0&0\\{ - 1/2}&1&{ - 1/2}&0& \cdots &0&0\\0&{ - 1/2}&1&{ - 1/2}& \cdots &0&0\\ \vdots & \vdots & \vdots & \vdots & \cdots & \vdots & \vdots \\0&0&0&0& \cdots &1&{ - 1/2}\\0&0&0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{\left( {N - 1} \right) \times \left( {N - 1} \right)}}=a_{N-1}$$ and, again taking Laplace's expansion along the first row $$\begin{array}{l}\det {\left[ {\begin{array}{*{20}{c}}{ - 1/2}&{ - 1/2}&0& \cdots &0&0\\0&1&{ - 1/2}& \cdots &0&0\\ \vdots & \vdots & \vdots & \cdots & \vdots & \vdots \\0&0&0& \cdots &1&{ - 1/2}\\0&0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{\left( {N - 1} \right) \times \left( {N - 1} \right)}} = \\ = - \frac{1}{2}\det {\left[ {\begin{array}{*{20}{c}}1&{ - 1/2}& \cdots &0&0\\ \vdots & \vdots & \cdots & \vdots & \vdots \\0&0& \cdots &1&{ - 1/2}\\0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{\left( {N - 2} \right) \times \left( {N - 2} \right)}}\\{\rm{ }} + \frac{1}{2}\det {\left[ {\begin{array}{*{20}{c}}0&{ - 1/2}& \cdots &0&0\\ \vdots & \vdots & \cdots & \vdots & \vdots \\0&0& \cdots &1&{ - 1/2}\\0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{\left( {n - 2} \right) \times \left( {N - 2} \right)}}\\ = - \frac{1}{2}{a_{N - 2}} + \frac{1}{2} \times 0\end{array}$$ Hence, we get the following linear difference equation for $a_{N}=\det \left( {{A_N}} \right)$: $${a_N} = {a_{N - 1}} - \frac{1}{4}{a_{N - 2}}$$ There are many different techniques to solve linear difference equations, but I'm going to use my favorite, which is based uniquely in linear algebra.

To get started, let's take $b_N=a_{N-1}$, which allows us to write our second order linear difference equation as a system of two first order linear equations: $$\left\{ \begin{array}{l}{a_N} = {a_{N - 1}} - \frac{1}{4}{b_{N - 1}}\\{b_N} = {a_{N - 1}}\end{array} \right. \Leftrightarrow \underbrace {\left[ {\begin{array}{*{20}{c}}{{a_N}}\\{{b_N}}\end{array}} \right]}_{{X_N}} = \underbrace {\left[ {\begin{array}{*{20}{c}}1&{ - 1/4}\\1&0\end{array}} \right]}_M\underbrace {\left[ {\begin{array}{*{20}{c}}{{a_{N - 1}}}\\{{b_{N - 1}}}\end{array}} \right]}_{{X_{N - 1}}}$$

At this point, let's breathe and think what we can get from the last expression. We actually know $X_2$: $${X_2} = \left[ {\begin{array}{*{20}{c}}{{a_2}}\\{{b_2}}\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}{{a_2}}\\{{a_1}}\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}{\det \left( {{A_2}} \right)}\\{\det \left( {{A_1}} \right)}\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}{\left| {\begin{array}{*{20}{c}}1&{ - 1/2}\\{ - 1/2}&1\end{array}} \right|}\\{\left| 1 \right|}\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}{3/4}\\1\end{array}} \right]$$ so we can get $X_3=M X_2$, $X_4=M X_3=M^2 X_2$, ... and this inductively leads us to the following expression $${X_N} = {M^{N - 2}}{X_2}$$ If we are able to find $M^{N-2}$, then we can find the general expression for $X_N$ and thus get the solution, $a_N$, to our original second order linear difference equation.

Let's take the Jordan decomposition of $M$, $M=S J S^{-1}$. Then $${M^{N - 2}} = \underbrace {SJ{S^{ - 1}}SJ{S^{ - 1}} \ldots SJ{S^{ - 1}}}_{(N-2){\rm{ times}}} = SJ\left( {{S^{ - 1}}S} \right)J\left( {{S^{ - 1}}S} \right) \ldots \left( {{S^{ - 1}}S} \right)J{S^{ - 1}} = S{J^{N - 2}}S$$

To find, $S$ and $J$ we need to find the eigenvalues and eigenvectors of $M$. If $M$ is diagonalizable then $J$ will be a diagonal matrix whose entries are the eigenvalues of $M$ and $S$ will have the corresponding eigenvectors as columns. Otherwise, if $M$ has only one eigenvalue, say $\lambda$, of algebraic multiplicity 2 and its eigenspace is of dimension 1 (that is, we can only "extract" one eigenvector associated to $\lambda$) then, as the matrix $M$ is of order 2, we know that $J$ will have the form

$$J = \left[ {\begin{array}{*{20}{c}}\lambda &1\\0&\lambda \end{array}} \right]$$

and $S$ will have the only eigenvector we could find as its first column and a generalized eigenvector as its second column.

The characteristic polynomial associated to $M$ is $$p\left( \lambda \right) = {\left( {\lambda - \frac{1}{2}} \right)^2}$$

so $M$ has only one eigenvalue of algebraic multiplicity 2: $\lambda = 1/2$. After a few calculations we find that the eigenspace associated to $\lambda = \frac{1}{2}$ is $${E_\lambda } = N\left( {M - \frac{1}{2}I} \right) = \left\{ {\alpha \in \mathbb{R}:\alpha \left[ {\begin{array}{*{20}{c}}1\\2\end{array}} \right],} \right\}$$ so $\dim \left( {{E_\lambda }} \right) = 1$ and we only get one eigenvector; let's take $${v_\lambda } = {\left[ {\begin{array}{*{20}{c}}1&2\end{array}} \right]^T}.$$ We now need to find a generalized eigenvector and that we can do by solving the following linear system $$\left( {M - \frac{1}{2}I} \right)x = {v_\lambda }.$$ The solution for this system is $$x = {\left[ {\begin{array}{*{20}{c}}3&2\end{array}} \right]^T}$$ and so we get $$S = \left[ {\begin{array}{*{20}{c}}1&3\\2&2\end{array}} \right]; J = \left[ {\begin{array}{*{20}{c}}{\frac{1}{2}}&1\\0&{\frac{1}{2}}\end{array}} \right].$$ Doing some more calculation we can easily find $${S^{ - 1}} = \left[ {\begin{array}{*{20}{r}}{ - \frac{1}{2}}&{\frac{3}{4}}\\{\frac{1}{2}}&{ - \frac{1}{4}}\end{array}} \right].$$ Now, we only need to compute $J^{N-2}$. Fortunately for us it is a well known fact (you can prove it by induction) that $${\left[ {\begin{array}{*{20}{r}}\lambda &1\\0&\lambda \end{array}} \right]^N} = \left[ {\begin{array}{*{20}{c}}{{\lambda ^N}}&{N{\lambda ^{N - 1}}}\\0&{{\lambda ^N}}\end{array}} \right]$$ so we get $${J^{N - 2}} = \left[ {\begin{array}{*{20}{c}}{\frac{1}{{{2^{N - 2}}}}}&{\left( {N - 2} \right)\frac{1}{{{2^{N - 3}}}}}\\0&{\frac{1}{{{2^{N - 2}}}}}\end{array}} \right].$$ After some really messy calculations we arrive at $${X_N} = \left[ {\begin{array}{*{20}{c}}{{a_N}}\\{{b_N}}\end{array}} \right] = {M^{N - 2}}{X_2} = S{J^{N - 2}}{S^{ - 1}}{X_2} = \left[ {\begin{array}{*{20}{c}}{\frac{{N + 1}}{{{2^N}}}}\\{\frac{N}{{{2^{N - 1}}}}}\end{array}} \right]$$ and we can conclude that $${a_N} = \det \left( {{A_N}} \right) = \frac{{N + 1}}{{{2^N}}}.$$

Let's return to our initial problem of finding ${\left( {A_N^{ - 1}} \right)_{1,1}}$. We are now only missing $C_{11}$.

$${M_{1,1}} = \det {\left[ {\begin{array}{*{20}{c}}1&{ - 1/2}&0&0& \cdots &0&0\\{ - 1/2}&1&{ - 1/2}&0& \cdots &0&0\\0&{ - 1/2}&1&{ - 1/2}& \cdots &0&0\\ \vdots & \vdots & \vdots & \vdots & \cdots & \vdots & \vdots \\0&0&0&0& \cdots &1&{ - 1/2}\\0&0&0&0& \cdots &{ - 1/2}&1\end{array}} \right]_{\left( {N - 1} \right) \times \left( {N - 1} \right)}} = {a_{N - 1}} = \frac{{N}}{{{2^{N-1}}}}.$$ Hence $${C_{11}} = {\left( { - 1} \right)^{1 + 1}}{M_{1,1}} = \frac{N}{{{2^{N - 1}}}}$$ and we can finally conclude that $${\left( {A_N^{ - 1}} \right)_{1,1}} = \frac{{{C_{11}}}}{{\det \left( {{A_N}} \right)}} = \frac{N}{{{2^{N - 1}}}}\frac{{{2^N}}}{{N + 1}} = \frac{{2N}}{{N + 1}}, Q.E.D.$$