Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to show that the determinant of the following $(n\times n)$ matrix

$$ \begin{pmatrix} 5 & 2 & 0 &0&0&\cdots & 0\\ 2 & 5 & 2 & 0&0&\cdots & 0\\ 0 & 2 &5&2&0 & \cdots & 0\\ \vdots & \vdots& \vdots& \vdots& \vdots& \vdots& \vdots\\ 0 & \cdots& & 0& 2 &5& 2\\ 0 & \cdots & & \cdots&\cdots& 2 &5 \end{pmatrix} $$

is equal to $\frac13(4^{n+1}-1)$?

share|improve this question
    
I would suggest induction. It's going to be a little fiddly though. –  Matt Pressland Dec 29 '12 at 11:54
    
Induction would work using block determinants. –  Daryl Dec 30 '12 at 2:30

4 Answers 4

Let $M_n$ be the $n \times n$ matrix. Calculate the determinant by expanding along the first row and then by the second column, we get $ Det(M_n) = 5 Det(M_{n-1} ) - 4 Det(M_{n-2})$.

Let $Det(M_n) = D_n$, so $D_n$ satisfies the recurrence relation $D_n - 5 D_{n-1} + 4 D_{n-2} = 0$, with initial values $D_0 = 1, D_1 = 5$. The characteristic equation $x^2 - 5x + 4$ has roots $x= 4, 1$, so the solution has form $A4^n + B1^n$. Plugging in the initial values, we get $A= \frac {4}{3}, B= -\frac {1}{3}$, which yields the value $D_n = \frac {1}{3} (4^{n+1} - 1)$.


$D_0 = 1$ because it is the empty product, which by definition has the value 1. If you do not like to use $D_0 = 1$, you can just calculate $D_1 = 5$ and $D_2 = 5 \times 5 - 2 \times 2 = 21$ and then find the values of $A, B$.

share|improve this answer

We will generalize Calvin Lin's answer a bit i.e. let $$A_n = \begin{bmatrix} a & b & 0 & 0 & \cdots & 0\\ c & a & b & 0 & \cdots & 0\\ 0 & c & a & b & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & a & b\\ 0 & 0 & 0 & \cdots & c & a \end{bmatrix}$$ We then have $$\det(A_n) = a \det(A_{n-1}) - bc \det(A_{n-2})$$ Calling $\det(A_n) = d_n$ we have the recurrence, $$d_n = a d_{n-1} - bc d_{n-2}$$ The characteristic equation is $$x^2 - ax + bc = 0 \implies \left(x - \dfrac{a}2 \right)^2 - \left(\dfrac{a}2 \right)^2 + bc = 0$$ Hence, $$\left(x - \dfrac{a}2\right)^2 = \dfrac{a^2 - 4bc}4 \implies x = \dfrac{a \pm \sqrt{a^2-4bc}}2$$ Hence, we have $$d_n = k_1 \left( \dfrac{a + \sqrt{a^2-4bc}}2\right)^n + k_2 \left( \dfrac{a - \sqrt{a^2-4bc}}2\right)^n$$ We have $d_1 = a$ and $d_2 = a^2 - bc$. We then get that $d_0 = 1$. Hence, $$k_1 + k_2 = 1$$ $$a (k_1 + k_2) + (k_1 - k_2)\sqrt{a^2-4bc} = 2a \implies k_1 - k_2 = \dfrac{a}{\sqrt{a^2-4bc}}$$ Hence, \begin{align} k_1 = \dfrac{a + \sqrt{a^2-4bc}}{2\sqrt{a^2-4bc}}; & k_2 = -\dfrac{a-\sqrt{a^2-4bc}}{2\sqrt{a^2-4bc}} \end{align} Hence, $$\color{red}{\det(A_n) = \dfrac1{\sqrt{a^2-4bc}} \left( \left( \dfrac{a + \sqrt{a^2-4bc}}2\right)^{n+1} - \left( \dfrac{a - \sqrt{a^2-4bc}}2\right)^{n+1}\right)}$$ Plug in $a = 5$ and $b=c=2$, to get $$\det(A_n) = \dfrac13 \left( 4^{n+1} - 1\right)$$

share|improve this answer
    
For some reason, this is my first time seeing the off diagonal elements being different, though it clearly doesn't change anything in the proof. –  Calvin Lin Dec 31 '12 at 11:49

Your determinant is equal to $$ 2^n\det\begin{bmatrix}2x & 1 & 0 & 0 & 0 & \cdots & 0\\ 1 & 2x & 1 & 0 & 0 & \cdots & 0\\ 0 & 1 & 2x & 1 & 0 & \cdots & 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots &\vdots\\ 0 & \cdots & 0 & 1 & 2x & 1 & 0\\ 0 & \cdots & 0 & 0 & 1 & 2x & 1\\ 0 & \cdots & 0 & 0 & 0 & 1 & 2x\end{bmatrix}=:2^nD_n(x), $$ with $x=5/4$. As in Calvin Lin's answer, $D_n(x)$ satisfies a recurrence, namely $D_n(x)=2xD_{n-1}(x)-D_{n-2}(x)$, which can be obtained by expanding $D_n(x)$ by minors on its first row and then expanding the $(n-1)$-by-$(n-1)$ determinant one gets in the second term by minors on its first column. This is the defining recurrence for the Chebyshev polynomials of the first and second kinds, which are denoted $T_n(x)$ and $U_n(x)$. Furthermore, $U_0(x)=1=D_0(x)$ and $U_1(x)=2x=D_1(x)$. So $D_n(x)=U_n(x)$.

The Chebyshev Polynomials are related to expansions of trigonometric or hyperbolic functions. In the case of polynomials of the second kind, $$ \begin{aligned} U_n(\cos t)&=\frac{\sin (n+1)t}{\sin t},\\ U_n(\cosh t)&=\frac{\sinh (n+1)t}{\sinh t}. \end{aligned} $$ Using the second of these, we let $\cosh t=\frac{5}{4}$ and find that $e^t=\frac{1}{2}$ or $2$. Choosing one of these solutions, say $e^t=2$, one can evaluate both $\sinh (n+1)t$ and $\sinh t$. The end result is the given formula.

share|improve this answer

The determinant can also be verified using block determinants.

Define $A^{(k)}$ to be the $k\times k$ matrix of the form$$A^{(k)}:= \begin{bmatrix} 5 & 2 & 0 &0&0&\cdots & 0\\ 2 & 5 & 2 & 0&0&\cdots & 0\\ 0 & 2 &5&2&0 & \cdots & 0\\ \vdots & \vdots& \vdots& \vdots& \vdots& \vdots& \vdots\\ 0 & \cdots& & 0& 2 &5& 2\\ 0 & \cdots & & \cdots&\cdots& 2 &5 \end{bmatrix}. $$ This can be expressed as $$A^{(k)}=\begin{bmatrix}A^{(k-1)}&u\\u^T&5\end{bmatrix},$$ where $u=[0,0,0,\ldots,2]^T$ is a $k\times1$ vector.

It follows form the block determinant form that $$ \det\left(A^{(k)}\right)=\det\left(A^{(k-1)}\right)\det\left(5-u^T{\left(A^{(k-1)}\right)}^{-1}u\right), $$ which can be simplified dramatically by the structure of $u$ as $$ \det\left(A^{(k)}\right)=\det\left(A^{(k-1)}\right)\left(5-4{\left(A^{(k-1)}\right)}^{-1}_{n,n}\right). $$ Furthermore, $$\left(A^{(k-1)}\right)^{-1}_{n,n}=\frac{(-1)^{n+n}\det\left(A^{(k-2)}\right)}{\det\left(A^{(k-1)}\right)}=\frac{\det\left(A^{(k-2)}\right)}{\det\left(A^{(k-1)}\right)}.$$ The recurrence relation for the determinant can then be written as, upon simplifying, $$\det\left(A^{(k)}\right)=5\det\left(A^{(k-1)}\right)-4\det\left(A^{(k-2)}\right),$$ from which the required form of the determinant can be verified similarly to the previous answers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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