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

1 Answer 1

23
$\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, 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.$$

$\endgroup$
1
  • $\begingroup$ I feel like I just went on an entire journey. Impressive proof. $\endgroup$
    – Serge
    Jan 2 at 7:33

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.