How do you rewrite a determinant of a matrix into a polynomial by induction?

Question

$$\det\begin{bmatrix} {x} & {0} & {\cdots} & {\cdots} & {0} & {a_{1}} \\ {-1} & {x} & {0} & {\cdots} & {0} & {a_{2}} \\ {\ddots} & {\ddots} & {\ddots} & {\ddots} & {\vdots} & {\vdots} \\ {\cdots} & {0} & {-1} & {x} & {0} & {a_{n-3}} \\{\cdots} & {\cdots} & {0} & {-1} & {x} & {a_{n-2}} \\{\cdots} & {\cdots} & {\cdots} & {0} & {-1} & {a_{n-1}+x} \end{bmatrix}=a_1+a_2x+\cdots+a_{n-1}x^{n-2}+x^{n-1}$$

How can I replace the determinant on the left by induction to get $a_1+a_2x+\cdots+a_{n-1}x^{n-2}+x^{n-1}$? I need this to determine the determinant of the companion matrix and I don't understand how this step is done. Thanks in advance!

Answer 1

We wish to prove the following by induction:

$$ \det \begin{pmatrix} t & 0 & \cdots & 0 & a_0 \\ -1 & t & \cdots & 0 & a_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & -1 & t+a_{n-1} \end{pmatrix} =a_0+a_1t+\cdots+a_{n-1}t^{n-1}+t^n $$

When $n=1$ we have that

$$ \det \begin{pmatrix} a_0+t \end{pmatrix} =a_o+t $$

Now supposing that we've proved the claim holds for $n$, we will try to prove the claim holds for $n+1$. Starting with

$$ \det \begin{pmatrix} t & 0 & \cdots & 0 & a_0 \\ -1 & t & \cdots & 0 & a_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & -1 & t+a_n \end{pmatrix} $$

we do co-factor expansion on the first row we get

$$ t\cdot\det \begin{pmatrix} t & 0 & \cdots & 0 & a_1 \\ -1 & t & \cdots & 0 & a_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & -1 & t+a_n \end{pmatrix} +(-1)^n\cdot a_0\cdot\det \begin{pmatrix} -1 & t & \cdots & 0 \\ 0 & -1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & -1 \end{pmatrix} $$

The determinant on the right is $(-1)^n$, and from our induction hypothesis, the determinant of the left is $a_1+a_2t+\cdots+a_nt^{n-1}+t^n$. Hence we have that

$$ \begin{align*} \det \begin{pmatrix} t & 0 & \cdots & 0 & a_0 \\ -1 & t & \cdots & 0 & a_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & -1 & t+a_n \end{pmatrix} &= t\cdot(a_1+a_2t+\cdots+a_nt^{n-1}+t^n)+(-1)^n\cdot a_0\cdot(-1)^n\\ &= a_1t+\cdots+a_nt^n+t^{n+1}+a_o \\ &= a_0+a_1t+\cdots+a_nt^n+t^{n+1} \end{align*} $$

This shows the claim holds for $n+1$ assuming it held for $n$.

Answer 2

This issue is in connection with the classical Horner's method (https://en.wikipedia.org/wiki/Horner%27s_method).

Let us explain it WLOG on the $4 \times 4$ case:

$$M_4=\left(\begin{array}{rrrc} t& 0& 0& a\\ -1& t& 0& b\\ 0& -1& t& c\\ 0& 0& -1& d + t \end{array}\right)$$

We have to prove that its determinant $D_4$ is:

$$D_4=a+bt+ct^2+dt^3+t^4$$

i.e., we have to prove that (by Horner's "factorization"): :

$$D_4=(a+t\underbrace{(b+t(c+t(d+t)))}_{A})\tag{1}$$

This factorization happens to be in direct connection with cascade Laplace expansion(s) with respect to the first row. Indeed, in a first step:

$$D_4=(-1) \ a \ \underbrace{\det(\Delta)}_{(-1)^3} + t \det(M_3)\tag{2}$$

(Explanation of the subscript : $\Delta$ is a $3 \times 3$ upper triangular matrix with $-1$ entries on its diagonal).

otherwise said

$$D_4=(a+t(...))$$

which is in perfect matching with the beginning of expression (1) where the dots are exactly expression $A$.

Now we can proceed in the same way on the lower degree polynomial $A$, and then, again and again, this recurrence ending by a $1 \times 1$ matrix with unique entry $(d+t)$ whose determinant is... itself.

Remarks :

1) see this question and the interesting answer by Marc van Leeuwen.

2) it must be added that Horner's scheme has some other interesting applications ; among them, polynomial division and derivation, all well described in the article cited at the beginning of this answer.

3) one could object that the cancellation of minus signs in (2) may not happen in some other cases. In fact, in the general case of a $n \times n$ matrix, one has $(-1)^{n+1} a$ times the determinant of a triangular matrix having $n-1$ entries $(-1)$ on its diagonal, resulting into a final $+1$ coefficient.