How to compute the determinant of a tridiagonal Toeplitz matrix?

Question

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 & \cdots & 0 & 2 & 5 & 2 \\ 0 & \cdots & \cdots & \cdots & \cdots & 2 & 5 \end{pmatrix}$$

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

---

More generally:

How does one compute the determinant of the following tridiagonal matrix (where the three diagonals are constant)?

$$M_n(a,b,c) = \begin{pmatrix} a & b & 0 & 0 & 0 & \cdots & 0 \\ c & a & b & 0 & 0 & \cdots & 0 \\ 0 & c & a & b & 0 & \cdots & 0 \\ \vdots & \vdots& \vdots& \vdots & \vdots& \vdots & \vdots \\ 0 & \cdots & \cdots & 0 & c & a & b \\ 0 & \cdots & \cdots & \cdots & \cdots & c & a \end{pmatrix}$$

Here $a,b,c$ can be taken to be real numbers, or complex numbers.

In other words, the matrix $M_n(a,b,c) = (m_{ij})_{1 \le i,j \le n}$ is such that $$m_{ij} = \begin{cases} a & i = j, \\ b & i = j - 1, \\ c & i = j + 1, \\ 0 & \text{otherwise.} \end{cases}$$

There does not seem to be an easy pattern to use induction: the matrix is not a diagonal block matrix of the type $M = \bigl(\begin{smallmatrix} A & C \\ 0 & B \end{smallmatrix}\bigr)$ (where we could use $\det(M) = \det(A) \det(B)$ for the induction step), and there are no lines or columns with only one nonzero entry, so Laplace expansion gets complicated quickly.

Is there a general pattern that one could use? Or is the answer only known on a case-by-case basis? It's possible to compute the determinant by hand for small $n$:

$$\begin{align} \det(M_1(a,b,c)) & = \begin{vmatrix} a \end{vmatrix} = a \\ \det(M_2(a,b,c)) & = \begin{vmatrix} a & b \\ c & a \end{vmatrix} = a^2 - bc \\ \det(M_3(a,b,c)) & = \begin{vmatrix} a & b & 0 \\ c & a & b \\ 0 & c & a \end{vmatrix} = a^3 - 2abc \end{align}$$

But there is no readily apparent pattern and the computation becomes very difficult when $n$ gets large.

Answer 1

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

Answer 2

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.

This works for general $x,$ but as noted in Marc van Leeuwen's comment to user17762's answer, special care is required when $x=\pm1.$ Solving $\cosh t=x$ or $e^t+e^{-t}=2x$ we find $e^t=x\pm\sqrt{x^2-1},$ which yields $$ \begin{aligned} U_n(x)=U_n(\cosh t)&=\frac{(x+\sqrt{x^2-1})^{n+1}-(x-\sqrt{x^2-1})^{n+1}}{x+\sqrt{x^2-1}-(x-\sqrt{x^2-1})}\\ &=\frac{(x+\sqrt{x^2-1})^{n+1}-(x-\sqrt{x^2-1})^{n+1}}{2\sqrt{x^2-1}}. \end{aligned} $$ This clearly reduces to a polynomial in $x,$ but is more useful than the polynomial form for evaluation. When $x=\pm1,$ which is equivalent to $t=im\pi,$ l'Hôpital's rule is needed in the evaluation: $$ \begin{aligned} U_n(\pm1)=U_n(\cosh im\pi)&=\lim_{t\to im\pi}\frac{e^{(n+1)t}-e^{-(n+1)t}}{e^t-e^{-t}}\\ &=\lim_{t\to im\pi}\frac{(n+1)e^{(n+1)t}+(n+1)e^{-(n+1)t}}{e^t+e^{-t}}=(n+1)(\pm1)^n. \end{aligned} $$

Revised question: The method can be adapted to handle the more general form in the revised question of February 2015. If $bc=0$ the determinant is clearly $a^n.$ Otherwise, let $g$ be a solution to $g^2=bc$ and define $x:=\frac{a}{2g},$ $y:=\frac{b}{g}.$ Since $\frac{c}{g}=\frac{g}{b}=y^{-1},$ the more general determinant is equal to $$ g^n\det\begin{bmatrix}2x & y & 0 & 0 & 0 & \cdots & 0\\ y^{-1} & 2x & y & 0 & 0 & \cdots & 0\\ 0 & y^{-1} & 2x & y & 0 & \cdots & 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots &\vdots\\ 0 & \cdots & 0 & y^{-1} & 2x & y & 0\\ 0 & \cdots & 0 & 0 & y^{-1} & 2x & y\\ 0 & \cdots & 0 & 0 & 0 & y^{-1} & 2x\end{bmatrix}=:g^nD_n(x,y). $$ But $D_n(x,y)$ satisfies the same recurrence as $D_n(x)$ and the same initial conditions, and so $D_n(x,y)$ also equals $U_n(x).$ (It is independent of $y.$)

Answer 3

We will generalize Calvin Lin's answer a bit. 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, by using Laplace expansion twice, $$\det(A_n) = a \det(A_{n-1}) - bc \det(A_{n-2}).$$

Calling $\det(A_n) = d_n$ we have the following linear homogeneous recurrence relation: $$d_n = a d_{n-1} - bc d_{n-2}.$$

The characteristic equation is $$\begin{align} x^2 - ax + bc = 0 & \implies \left(x - \frac{a}2 \right)^2 - \left(\frac{a}2 \right)^2 + bc = 0 \\ & \implies x = \frac{a \pm \sqrt{a^2-4bc}}2. \end{align}$$

(This assumes a square roots exist. It's always the case in $\mathbb{C}$.)

Case 1: $a^2 - 4bc \neq 0$

In this case the characteristic polynomial has two distinct roots, so we have (for some constants $k_1$, $k_2$): $$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}$$

And finally: $$\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$ ($a^2 - 4 bc \neq 0$), to get $$\det(A_n) = \frac{1}{3} ( 4^{n+1} - 1)$$

Case 2: $a^2 - 4bc = 0$

If the characteristic polynomial has a double root $x = a/2$, there exist constants $k_1$, $k_2$ such that: $$d_n = (k_1 + k_2 n) \bigl(\frac{a}{2}\bigr)^n.$$

The initial conditions are $d_0 = 1$ and $d_1 = a$, thus: $$\begin{align} k_1 & = 1 & (k_1 + k_2) a = 2a \end{align}$$

If $a = 0$, then $4bc = a^2$ implies either $b$ or $c$ is zero, and $d_n = 0$ for $n \ge 1$. Otherwise $$(k_1 + k_2) a = 2a \implies k_1 + k_2 = 2 \implies k_2 = 1.$$ And finally: $$\color{red}{\det(A_n) = (n+1) \bigl(\frac{a}{2}\bigr)^n}.$$

Answer 4

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.