# 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. Nov 14, 2017 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 ? Nov 14, 2017 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!) Nov 14, 2017 at 10:06
• @BCLC: Yes you are wrong. Anything that requires inductive or recursive definitions necessarily require induction, whether or not you notice it. For example, proving $\sum_{k=1}^n k = n·(n+1)/2$ requires induction even if you use the pairing trick. Oct 25, 2021 at 5:30
• @user21820 thanks. how specifically am i wrong in my case please? perhaps i used induction but didn't even realise it?
– BCLC
Oct 25, 2021 at 5:47

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 ? Nov 11, 2017 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). Nov 11, 2017 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). Nov 12, 2017 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. Nov 13, 2017 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. Nov 13, 2017 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.