A simple determinant. [determinant of a companion matrix]

I have to find determinant of $$A := \begin{bmatrix}0 & 0 & 0 & ... &0 & a_0 \\ -1 & 0 & 0 & ... &0 & a_1\\ 0 & -1 & 0 & ... &0 & a_2 \\ 0 & 0 & -1 & ... &0 & a_3 \\ \vdots &\vdots &\vdots & \ddots &\vdots&\vdots \\0 & 0 & 0 & ... &-1 & a_{n-1} \end{bmatrix} + t I_{n \times n}$$

It is not a difficult thing to do. My method is as follows :

$$\begin{bmatrix}0 & 0 & 0 & ... &0 & a_0 \\ -1 & 0 & 0 & ... &0 & a_1\\ 0 & -1 & 0 & ... &0 & a_2 \\ 0 & 0 & -1 & ... &0 & a_3 \\ \vdots &\vdots &\vdots & \ddots &\vdots&\vdots \\0 & 0 & 0 & ... &-1 & a_{n-1} \end{bmatrix} + t I_{n \times n} = \begin{bmatrix}t & 0 & 0 & ... &0 & a_0 \\ -1 & t & 0 & ... &0 & a_1\\ 0 & -1 & t & ... &0 & a_2 \\ 0 & 0 & -1 & ... &0 & a_3 \\ \vdots &\vdots &\vdots & \ddots &\vdots&\vdots \\0 & 0 & 0 & ... &-1 & a_{n-1} + t \end{bmatrix}$$

Performing the row reduction of type $R_{k+1} \to R_{k+1} + \dfrac{1}{t}R_k$

I get an upper triangular matrix

$$\begin{bmatrix}t & 0 & 0 & ... &0 & a_0 \\ 0 & t & 0 & ... &0 & a_1 + \dfrac {a_0} t\\ 0 & 0 & t & ... &0 & a_2 + \dfrac{a_1}{t} + \dfrac {a_0} {t^2} \\ 0 & 0 & 0 & ... &0 & a_3 + \dfrac{a_2}{t} + \dfrac{a_1}{t^2} + \dfrac {a_0} {t^3} \\ \vdots &\vdots &\vdots & \ddots &\vdots&\vdots \\0 & 0 & 0 & ... &0 & a_{n-1} + t + \sum_{k=0}^{n-2} \dfrac{a_{k}}{t^{(n-1) - k }} \end{bmatrix}$$

Determinant of which is $t^n + \sum^{n-1}_{k = 1} a_k t^{k}$.

My friend says this is not a rigorous proof and that I have to use induction to prove $\det A = t^n + \sum^{n-1}_{k = 1} a_k t^{k}$. She says that I have only found a formula for $\det A$ and I can't be sure if it works for all $n\in \Bbb N$ without a proof. Is she correct ?

• Listen to your friend. I've a solid background in logic and she is absolutely correct here. If you don't believe her or me, please ask any professional logician instead of trying to judge between (sometimes wrong) answers from strangers online. – user21820 Nov 14 '17 at 4:58
• @user21820 I didn't find any of the answers convincing, hence no green tick. Since you're a professional logician, will a proof that uses "dots" - like mine - accepted in academic papers ? Or you have to prove it using induction (or something else) every time ? – user8277998 Nov 14 '17 at 9:57
• Mathematical papers do not usually give completely rigorous proofs, but they often give at least enough details to convince their intended audience (who could be experts in that field) that there exists some rigorous proof. But the authors should know how to do it rigorously. Modern mathematics is founded on formal systems and not intuition. In your case, it seems you do not quite know what is a rigorous proof, so if you learn basic logic you will understand what I mean. (Come to the Logic chat-room if you wish to further discuss!) – user21820 Nov 14 '17 at 10:06

Yes, the method is completely rigorous, because here $t$ is, algebraically, an indeterminate.

If the coefficients of the matrix are supposed to be in a field $F$, then the computation you make takes place in the field $F(t)$ of rational functions in the indeterminate $t$. No problem here in considering $t^{-1}$, because $t$ is a nonzero element of the field.

To be picky, induction should be needed, but laying out the argument is very easy.

• "To be picky, induction should be needed" Why so ? – user8277998 Nov 11 '17 at 22:13
• @DuncanRamage That's why I said “to be picky”; just be aware that induction is being used (and its formalization in the present case is trivial). – egreg Nov 11 '17 at 23:08
• @123 and DuncanRamage: "Performing the row reduction of type ..." is actually not a single row reduction, but $n-1$ row reductions applied in a row (no pun intended). And the order of these reductions matters. So, yes, there is a hidden induction in your proof, unless you replace the $n-1$ row reductions by a multiplication by some triangular matrix (recommended if you want to formalize the proof). – darij grinberg Nov 12 '17 at 6:38
• @DuncanRamage: I think that if you do it properly, you can avoid making mistakes. Nevertheless, using dots in place of precise statements always relies on pattern matching by the reader to figure out what the intended meaning is, so it can be useful in rough work but not in a rigorous proof. – user21820 Nov 13 '17 at 9:00
• @DuncanRamage: The asker explicitly says "My friend says this is not a rigorous proof", so it's necessary to be pedantic to explain the situation fully to the asker. By avoiding the technical detail, you are not helping the asker at all. – user21820 Nov 13 '17 at 18:53

The argument can be made rigorous by the following identity: let $U$ be the final triangular matrix and let $D$ be the matrix containing only a subdiagonal of $1, \cdots, 1$. Then one has

$$\left(I - \frac{1}{t} D\right) U = (A + t I)$$ hence $\det(A+tI)= \det(I - \frac{1}{t} D) \det (U) = \det(U)$

It means that this process is actually an $LU$ decomposition of $A+tI$.

For a complete calculation, let

$$\renewcommand{\arraystretch}{2} \begin{array}{rcl}{P}_{0}&=&0\\ {P}_{i}&=&\displaystyle \sum _{p = 0}^{i-1} {a}_{p} {t}^{p} \quad i \geqslant 1\\ L&=&{\left({{\delta}}_{i}^{j}-{t}^{{-1}} {{\delta}}_{i}^{j+1}\right)}_{i , j}\\ U&=&{\left(t {{\delta}}_{i}^{j}+{t}^{1-i} {P}_{i} {{\delta}}_{j}^{n}\right)}_{i , j} \end{array}$$

Then, using ${P}_{i}-{P}_{i-1} = {a}_{i-1} {t}^{i-1}$ for $i \geqslant 1$,

$$\renewcommand{\arraystretch}{2} \begin{array}{rcl}{\left(L U\right)}_{i , j}&=&\displaystyle \sum _{k = 1}^{n} \left({{\delta}}_{i}^{k}-{t}^{{-1}} {{\delta}}_{i}^{k+1}\right) \left(t {{\delta}}_{k}^{i}+{t}^{1-k} {P}_{k} {{\delta}}_{j}^{n}\right)\\ &=&t {{\delta}}_{i}^{j}+{t}^{1-i} {P}_{i} {{\delta}}_{j}^{n}-{{\delta}}_{i}^{j+1}-{t}^{1-i} {P}_{i-1} {{\delta}}_{j}^{n}\\ &=&t {{\delta}}_{i}^{j}-{{\delta}}_{i}^{j+1}+{a}_{j-1} {{\delta}}_{j}^{n}\\ &=&{\left(A+t I\right)}_{i , j} \end{array}$$

where $\delta_i^j$ is Kronecker's delta.

$-A$ is the companion matrix for the polynomial $$p(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1} + x^n.$$ Hence the eigenvalues of $-A$ are the roots $r_k$ of this polynomial. Since adding a multiple of the identity to a matrix just shifts eigenvalues, the eigenvalues of $A + tI$ are the quantities $t-r_k$. Hence, since the determinant of a matrix is the product of its eigenvalues, we have $$\det(A + tI) = (t - r_1)(t - r_2) \dots (t-r_n) = p(t)$$ as required.