3
$\begingroup$

Let

$$f_n := \begin{vmatrix} a_1 & b_1 \\ c_1 & a_2 & b_2 \\ & c_2 & \ddots & \ddots \\ & & \ddots & \ddots & b_{n-1} \\ & & & c_{n-1} & a_n \end{vmatrix}$$

Apparently, the determinant of the tridiagional matrix above is given by the recurrence relation

$$f_n = a_n f_{n-1} - c_{n-1} b_{n-1}f_{n-2}$$

with initial values $f_0 = 1$ and $f_{-1} = 0$ (according to Wikipedia). Can anyone please explain to me how they came to this recurrence relation? I don't really understand how to derive it.

$\endgroup$
2
$\begingroup$

The recurrence is obtained by developing the determinant along the last column (or, equivalently, along the last row).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

For $n \ge 2$ using Laplace expansion on the last row gives \begin{align} f_n &= \begin{vmatrix} a_1 & b_1 \\ c_1 & a_2 & b_2 \\ & c_2 & \ddots & \ddots \\ & & \ddots & \ddots & b_{n-3} \\ & & & c_{n-3} & a_{n-2} & b_{n-2} \\ & & & & c_{n-2} & a_{n-1} & b_{n-1} \\ & & & & & c_{n-1} & a_n \end{vmatrix} \\ &= (-1)^{2n-1} c_{n-1} \begin{vmatrix} a_1 & b_1 \\ c_1 & a_2 & b_2 \\ & c_2 & \ddots & \ddots \\ & & \ddots & \ddots & b_{n-3} \\ & & & c_{n-3} & a_{n-2} \\ & & & & c_{n-2} & b_{n-1} \end{vmatrix} + (-1)^{2n} a_n \begin{vmatrix} a_1 & b_1 \\ c_1 & a_2 & b_2 \\ & c_2 & \ddots & \ddots \\ & & \ddots & \ddots & b_{n-2} \\ & & & c_{n-2} & a_{n-1} \end{vmatrix} \\ &= - c_{n-1} (-1)^{2(n-1)} b_{n-1} \begin{vmatrix} a_1 & b_1 \\ c_1 & a_2 & b_2 \\ & c_2 & \ddots & \ddots \\ & & \ddots & \ddots & b_{n-3} \\ & & & c_{n-3} & a_{n-2} \end{vmatrix} + a_n f_{n-1} \\ &= a_n f_{n-1} - c_{n-1} b_{n-1} f_{n-2} \end{align} as recurrence relation.

For the initial conditions:

From comparing the above formula with matrices for $n=1$ and $n=2$ we get: $$ f_1 = a_1 f_0 - c_0 b_0 f_{-1} \overset{!}{=} a_1 \\ f_2 = a_2 f_1 - c_1 b_1 f_0 \overset{!}{=} a_1 a_2 - c_1 b_1 $$ The latter implies $f_0 = 1$ and the former $f_{-1} = 0$.

| cite | improve this answer | |
$\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.