# Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix

$$A =\left(\begin{array}{ccccccc} d_1&a_1\\c_2&d_2&a_2\\&c_3&d_3&a_3\\&&&\ddots\\&&&&\ddots\\&&&&c_{n-1}&d_{n-1}&a_{n-1}\\&&&&&c_n&d_n \end{array}\right)$$

and

$$f_i =\left|\begin{array}{ccccccc} d_1&a_1\\c_2&d_2&a_2\\&c_3&d_3&a_3\\&&&\ddots\\&&&&\ddots\\&&&&c_{i-1}&d_{i-1}&a_{i-1}\\&&&&&c_i&d_i \end{array}\right|$$

then it is true that the determinants $f_i$ satisfy a three-term recurrence:

$$f_i = d_if_{i-1} - c_ia_{i-1}f_{i-2}$$ for $$f_0=1\text{ and }f_{-1}=0$$

If we are given a symmetric tridiagonal matrix

$$A =\left(\begin{array}{ccccccc} d_1&a_1\\a_1&d_2&a_2\\&a_2&d_3&a_3\\&&&\ddots\\&&&&\ddots\\&&&&a_{n-2}&d_{n-1}&a_{n-1}\\&&&&&a_{n-1}&d_n \end{array}\right)$$

is it possible to calculate the determinant more efficiently than using the recurrence relation?

In other words, can we write a function that theoretically performs quicker than the following code (barring any language/programming-specific optimizations):

double det(double* d, int count, double* a) {
double f0 = 1;
double f1 = d[0];
double ftemp;

for (int i = 1; i < count; i++) {
ftemp = f1;
f1 = d[i]*f1 - a[i-1]*a[i-1]*f0;
f0 = ftemp;
}
return f1;
}

• Indeed, use x*x instead of pow(x,2) – Algebraic Pavel Nov 21 '13 at 10:21
• @AlgebraicPavel that is true, but I'm talking more algorithmically as opposed to specifically the code I wrote. Regardless, I changed the code to include the improvement :) – Alex Brooks Nov 21 '13 at 16:45
• I'd be interested in a bit more general question: How does one efficiently compute the eigenvalues of such matrices? – Semiclassical Jul 24 '14 at 15:03

If you're asking if either of these determinants can be solved/calculated by a sub-linear time algorithm, the answer is obviously no because the $a_i$'s and $d_i$'s can all have different values and thus you need to read each of them at least once (and use the value read in some operation), so that gives $2n$ (minus some small constant, which I can't be bothered to calculate) a lower bound for the symmetric one and $3n$ for the general tridiagonal matrix determinant. Asymptotically, both are $\Omega(n)$ of course.
However if the values are known to be all the same, then you can have a constant-time, closed-form formula, e.g. the answer is the Fibonacci number if $a_i=-1$ and $c_i=d_i=1$. There are several papers about such determinants; here's an example one. A constant-time time algorithm for such closed formulas assumes the result is small enough to fit in a register, otherwise if you need arbitrary-precision arithmetic, then it's no longer proper to consider them constant time.