Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the main diagonal all equal -1 and entries on even lower diagonals equal zero. For example:
$$\begin{pmatrix}
a_{11} & a_{12} & a_{13} & a_{14} \\
-1 & a_{22} & a_{23} & a_{24} \\
0 & -1 & a_{33} & a_{34} \\
0 & 0 & -1 & a_{44}
\end{pmatrix}$$
I accidentally found a very nice expression for the determinant of these matrices.
For $i \leq j$ in $\mathbb{N}$ let $[i, \ldots, j]$ denote the interval of successive integers starting at $i$ and ending at $j$. There are $2^{n-1}$ ways to partition the interval $[1, \ldots, n]$ into subintervals (e.g. $[1, 2, 3][4][5, \ldots, n]$ would be such a partition): for each of the $n-1$ comma's in $[1, \ldots, n]$ we can decide whether or not to replace it by a ']['.
Now in order to compute the determinant of matrix $A$ of the form above, all we need to do is the following:
- Write down the $2^{n-1}$ partitions of $[1, \ldots, n]$ into subintervals.
- In each partition replace each subinterval $[i, \ldots, j]$ with the matrix-entry $a_{ij}$ and interpret the resulting string of matrix entries as a product
- Sum all the $2^{n-1}$ terms. (No minus signs involved!)
The result is $\det A$.
Weird, huh? As a free bonus we note that the determinant expression for the complete Bell polynomials can be computed in this way.
Since this identity is not terribly hard to prove my question is: is this known? But also a more conceptual explanation, perhaps linking the interval partitions here to the set partitions in the definition of Bell polynomial would be welcome.
UPDATE: Per request of Darij Grinberg I will give a proof and some easy applications to financial mathematics.
Proof by induction on $n$: Write $A_{ij}$ for the matrix obtained by crossing out row $i$ and column $j$ from $A$. We divide the partitions of the interval $[1, \ldots, n]$ into two types: those that end in $[n]$ (short-tailed) and those that end in $[i, \ldots, n]$ for some $i < n$ (long tailed). The long tailed partitions do not contain any intervals starting with $n$ or ending in $n-1$ so if we apply our three step process described above to this set only we obtain an expression in the elements of $A_{n, n-1}$ which (after the right renumberings) can be seen to equal $\det(A_{n, n-1})$ by the induction hypothesis.
When we apply our three step procedure to the short tailed partitions we obtain in an even more straightforward application of the induction hypothesis the number $a_{n,n} \cdot \det(A_{n, n})$.
So what remains to be shown is that $\det(A) = \det(A_{n, n-1}) + a_{n,n}\det(A_{n,n})$ but this is just Laplace's cofactor expansion formula for the determinant, applied to the last row of $A$.
Interpretation of the determinant in case $A$ is constant along diagonals: Suppose $A$ has $1$'s on the first (= main) and second (= the one just above) diagonal and $0$'s everywhere else (except for the $-1$'s on the zeroth diagonal of course) then the above states that $\det A$ equals the number of ways of tiling a path of length $n$ by tiles of length 1 and 2, which is well known to be the $n$'th Fibonacci number. By putting $1$'s on different diagonals we can similarly find determinant identities for the Tribonacci numbers or, more financially interesting, for the number of ways to pay an $n/100$-dollar bill with coins only.
Staying in the realm of money: if instead of just $0$'s and $1$'s we fill the diagonals with numbers from the real interval $[0, 1]$ (just one number repeated over and over per diagonal) the above count turns into a probability. For instance if we take $n= 40$, put $0$'s in the main diagonal, $1/12$'s in the second diagonal, $1/6$ in the third diagonal etc, upto $0$'s in diagonals 13 to 40, the determinant of $A$ will give us the probability of landing exactly on Go (rather than just passing it) after one round trip in a game of Monopoly.
What I would be really interested in are interpretations of these determinants in case the entries on each diagonal are not constant (but follow some other pattern enabling the interpretation).
Best Answer
Here is one easy interpretation for nonconstant entries on the first subdiagonal. Substituting $-a_{21},-a_{32},\dots,-a_{n,n-1}$ in place of the $-1$'s yields a weighted count, where each edge $(i,i+1)$ on the path from $1$ to $n$ has weight $a_{i+1,i}$, and the weight of the subpath from $i$ to $j$ is the product of the weights of its edges, $\prod_{k=i}^{j-1}{a_{i+1,i}}$. This is useful, for example, if there are multiple edges between successive vertices.