# 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

• Looks like some computations with the adjusted matrix would probably work. Jan 28, 2014 at 22:36
• Adjusted matrix? I'm not sure I know of anything by that name. Could you perhaps elaborate? Jan 28, 2014 at 23:45
• If the diagonals are constant, you can easily calculate analytically the eigenvalues and the eigenvectors of $A$. Given the eigendecomposition, the inversion is then easy. Jan 30, 2014 at 1:43
• Sorry. I meant adjugate matrix. Jan 30, 2014 at 7:19

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, with the $$(i,j)$$-cofactor defined as: $${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 on linear algebra.

To get started, let's take $$b_N=a_{N-1}$$, which allows us to write the 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].$$ Therefore, we have $$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, arrive at 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.$$

• I feel like I just went on an entire journey. Impressive proof. Jan 2 at 7:33