7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Looks like some computations with the adjusted matrix would probably work. $\endgroup$ – bubba Jan 28 '14 at 22:36
  • $\begingroup$ Adjusted matrix? I'm not sure I know of anything by that name. Could you perhaps elaborate? $\endgroup$ – curiousjason Jan 28 '14 at 23:45
  • $\begingroup$ 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. $\endgroup$ – Algebraic Pavel Jan 30 '14 at 1:43
  • $\begingroup$ Sorry. I meant adjugate matrix. $\endgroup$ – bubba Jan 30 '14 at 7:19
15
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.