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. 
 A: 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.
A: 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.$
A: 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.)
A: I have published the following recurrent relation and explicit formula for the determinant at Evaluate the determinant of a Hessenberg matrix.
Let $n\ge2$ and
\begin{equation}\label{I(n)-Matrix=Eq}
P_n=
\begin{pmatrix}
p_{i,j}
\end{pmatrix}_{1\le i,j\le n}
=
\begin{pmatrix}
a_1 & c_1 & 0 & 0 & \dotsm & 0 & 0 & 0 & 0\\
a_2 & b_2 & c_2 & 0 & \dotsm & 0 & 0 & 0 & 0\\
a_3 & 0 & b_3 & c_3 & \dotsm & 0 & 0 & 0 & 0\\
a_4 & 0 & 0 & b_4 & \dotsm & 0 & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\\
a_{n-3} & 0 & 0 & 0 & \dotsm & b_{n-3} & c_{n-3} & 0 & 0\\
a_{n-2} & 0 & 0 & 0 & \dotsm & 0 & b_{n-2} & c_{n-2} & 0\\
a_{n-1} & 0 & 0 & 0 & \dotsm & 0 & 0 & b_{n-1} & c_{n-1}\\
a_n & 0 & 0 & 0 & \dotsm & 0 & 0 & 0 & b_n
\end{pmatrix},
\end{equation}
where
\begin{equation*}
p_{i,j}=
\begin{cases}
a_i, & 1\le i\le n, j=1;\\
b_i, & 2\le i=j\le n;\\
c_i, & 1\le i=j-1\le n-1;\\
0, & \text{otherwise}.
\end{cases}
\end{equation*}
(1) Recurrent relation. Let $n\ge2$ and $b_k\ne0$ for $2\le k\le n$. Then the determinant $|P_n|$ can be computed recurrently by
\begin{equation}\label{I(n)-Matrix=Recur-Eq}
|P_n|=\lambda_{1,n}\prod_{k=2}^nb_k,
\end{equation}
where
\begin{equation}\label{alpha-recur-Eq}
\lambda_{k,n}=a_k-\frac{c_k}{b_{k+1}}\lambda_{k+1,n}, \quad 1\le k\le n-1
\end{equation}
and $\lambda_{n,n}=a_n$.
(2) Explicit Formula. For $n\ge2$, the determinant $|P_n|$ can be computed explicitly by
\begin{equation}\label{I(n)-Matrix=Explicit-Eq}
|P_n|=a_1\prod_{k=2}^nb_k-\sum_{k=2}^n(-1)^k \Biggl(\prod_{\ell=1}^{k-1}c_\ell \prod_{m=k+1}^nb_m\Biggr)a_k.
\end{equation}
These two relation and formula are included in the following paper:
Feng Qi, Wen Wang, Bai-Ni Guo, and Dongkyu Lim, Several explicit and recurrent formulas for determinants of tridiagonal matrices via generalized continued fractions, Chapter 15 in: Zakia Hammouch, Hemen Dutta, Said Melliani, and Michael Ruzhansky (eds), Nonlinear Analysis: Problems, Applications and Computational Methods, SM2A 2019, pp. 233--248; Springer Book Series Lecture Notes in Networks and Systems, Volume 168, Springer, Cham, 2021; available online at https://doi.org/10.1007/978-3-030-62299-2_15.
This paper can also be downloaded from the site https://www.researchgate.net/publication/343700624
See also discussions at the site https://www.researchgate.net/post/How_to_compute_a_Hessenberg_determinant_whose_elements_are_the_Bernoulli_numbers
