# Determinant of circulant-like matrix

Given is an $n \times n$ matrix $M_n$ with the following structure —

$$M_n = \left( \begin{array}{ccccc} a_1 & 0 & \dots & 0 & b_1 \\ b_2 & a_2 & & & 0\\ & \ddots & \ddots & & \vdots \\ & & b_{n-1} & a_{n-1} & 0\\ & & & b_n & a_n\end{array} \right),$$

with $a_i$ and $b_i \in \mathbb{R}$ where $i \in \{1,\dots,n\}$.

1.) Is there a name for this specific type of matrix? The non-zero entries in each row are shifted one position to the right compared to the previous row, which reminds me of a circulant matrix (though in that case, the rows share the same values, which is generally not the case for $M_n$).

2.) Is there a short/fast way (i.e. not just using Leibniz's formula) to compute the determinant of this type of matrix?

It might help to consider an example, so here's $M_5$ —

$$M_5 = \left( \begin{array}{ccccc} a_1 & 0 & 0 & 0 & b_1 \\ b_2 & a_2 & 0 & 0 & 0\\ 0 & b_3 & a_3 & 0 & 0\\ 0 & 0 & b_4 & a_4 & 0\\ 0 & 0 & 0 & b_5 & a_5\end{array} \right) = \left( \begin{array}{ccccc} a_1 & & & & b_1 \\ b_2 & a_2 & & & \\ & b_3 & a_3 & & \\ & & b_4 & a_4 & \\ & & & b_5 & a_5\end{array} \right)$$

This looks like a special case of a upper Hessenberg matrix. See here

https://en.wikipedia.org/wiki/Hessenberg_matrix

You can transform an upper Hessenberg matrix into a triangular matrix by using the QR factorization.

https://en.wikipedia.org/wiki/QR_decomposition

Once you've done that computation of the determinant is simple. In fact, if the matrix is big, you can use the fact that it's sparse to really speed things along.

• You can't beat $a_1 a_2 \cdots a_n + \left(-1\right)^{n-1} b_1 b_2 \cdots b_n$ in terms of speed. I think :) – darij grinberg Oct 28 '17 at 21:25

I thought a bit more about this matrix, and realised that there is actually a straightforward way to compute its determinant using co-factor expansion (also known as Laplace expansion).

The task is to compute $\det(M_n)$, with $M_n$ given as

$$M_n = \left( \begin{array}{ccccc} a_1 & 0 & \dots & 0 & b_1 \\ b_2 & a_2 & 0 & \dots & 0\\ 0 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & b_{n-1} & a_{n-1} & 0\\ 0 & \dots & 0 & b_n & a_n\end{array} \right).$$

Now, if we simply expand along the first row, we get that

$$\det(M_n) = a_1 \det\left( \begin{array}{cccc} a_2 & 0 & \dots & 0\\ \ddots & \ddots & \ddots & \vdots \\ \ddots & b_{n-1} & a_{n-1} & 0\\ \dots & 0 & b_n & a_n\end{array} \right) + (-1)^{(1+n)} b_1\det\left( \begin{array}{cccc} b_2 & a_2 & 0 & \dots \\ 0 & \ddots & \ddots & \ddots \\ \vdots & \ddots & b_{n-1} & a_{n-1} \\ 0 & \dots & 0 & b_n \end{array} \right).$$

Both these $(n-1) \times (n-1)$ matrices are triangular matrices, which means that their determinant equals the product of the diagonal entries. That is,

$$\det(M_n) = a_1 \prod_{k=2}^n a_k + (-1)^{n+1} b_1 \prod_{k=2}^n b_k\\ = \prod_{k=1}^n a_k+ (-1)^{n+1} \prod_{k=1}^n b_k.$$