Evaluate the determinant of a Hessenberg matrix

The following question is taken from here exercise $1$:

Question Evaluate the determinant: \begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ -y_1 & x_1 & 0 & \dots & 0 \\ 0 & -y_2 & x_2 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & x_n \end{vmatrix}

Since this is a competition question, I suppose the normal determinant formula will not work. Indeed, tedious and messy calculations are inevitable if one just expand the determinant.

I observe that the matrix has $-y_i$ at super diagonal for all $1\leq i \leq n.$ However, I do not think this helps.

Any hint would be appreciated.

Solution 1:

Expanding along the final column results in

$$a_n\cdot(-1)^{n+2} \begin{vmatrix} -y_1 & * & *&*&* \\ 0& -y_2& *&*&*\\ 0& 0 & -y_3&*&*\\ \vdots&\vdots&\vdots & \ddots&*\\ 0&0&0&\cdots &-y_n \end{vmatrix} + x_n\cdot \begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_{n-1} \\ -y_1 & x_1 & 0 & \dots & 0 \\ 0 & -y_2 & x_2 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & x_{n-1} \end{vmatrix}$$

The first determinant is easy to calculate (it is $(-1)^n\cdot y_1\cdot y_2\cdots y_n$), while the second one is similar to the first, only smaller. So, if we define the determinant you wanted to calculate as $D_n$, you have

$$D_{n} = a_n\cdot y_1\cdot y_2\cdots y_n + x_nD_{n-1}$$

Now expanding that $D_{n-1}$ part further can yield some sort of solution (I don't see it being particularly pretty, however...)

Edit:

If I am not mistaken, the final result is

$$a_0x_1x_2\cdots x_n + a_1y_1x_2x_3\cdots x_n + \cdots + a_iy_1y_2\cdots y_i x_{i+1}\cdots x_n + \cdots + a_ny_1y_2\cdots y_n$$

or, written without all the dots:

$$\sum_{k=0}^n \left(a_k\prod_{i=1}^{k} y_i\prod_{i=k+1}^n x_i\right).$$

I don't see any obvious way to simplify this, however.

Solution 2:

Partition the matrix as $$ A=\left( \begin{array}{c|ccc} a_0&a_1&\cdots&\cdots & a_n \\ \hline -y_1&x_1\\ 0&-y_2&x_2\\ \vdots&&\ddots&\ddots\\ 0&&&y_n&x_n \end{array} \right) =\pmatrix{a_0&\mathbf a^\top\\ \mathbf v&L}. $$ Then, using Schur complement, we get $\det A=(a_0-\mathbf a^\top L^{-1}\mathbf v)\det(L)$. As $L$ is lower bidiagonal, $L^{-1}\mathbf v$ can be calculated easily using forward substitution, and we obtain $$ L^{-1}\mathbf v=\left(-\frac{y_1}{x_1},\ -\frac{y_1y_2}{x_1x_2},\ \cdots,\ -\frac{y_1\cdots y_n}{x_1\cdots x_n}\right)^\top. $$ Hence $\det A = \left(a_0+\sum_{k=1}^na_k\prod_{i=1}^k\frac{y_i}{x_i}\right)\prod_{i=1}^nx_i.$

Solution 3:

For a general Hessenberg matrix, there is a recurrence relation derived in Cahill et al. (2003) ("Fibonacci determinants," College Math. J. 33, pp. 221-225). If we change notation slightly and use $a_{i,j}$ to denote the entry in row $i$ and column $j$ of $A$, then Cahill's recurrence (transposed for an $(n+1)\times(n+1)$ upper Hessenberg matrix) is:

\begin{align} d_0 & = 1 \\ d_1 & = a_{1,1} \\ d_k & = a_{k,k} d_{k-1} + \sum_{i=1}^{k-1} \left[ (-1)^{k-i} a_{i,k} \prod_{j=i}^{k-1} a_{j+1,j} d_{i-1} \right] \\ \det A & = d_{n+1} \end{align}

This recurrence can be implemented with $\Theta(n^2)$ arithmetic complexity by using $\Theta(n)$ scratch storage to build up the partial products $\prod$, as implemented here for Julia.

For your specific Hessenberg matrix above, you can see that most of the terms in the sum are zero and the cost is considerably reduced. In your original notation, the recurrence simplifies to:

\begin{align} d_1 & = a_0 \\ d_k & = x_{k-1} d_{k-1} + a_{k-1} \prod_{j=1}^{k-1} y_j \\ \det A & = d_{n+1} \end{align}

which can be implemented in $\Theta(n)$ arithmetic operations with $\Theta(1)$ additional storage (using a recurrence to compute the $\prod$ as we go along). (This is essentially the same as the $D_n$ recurrence derived above by another poster.)