## Compute the characteristic polynomial of a companion matrix

Let $p(x) = \sum_{i=0}^n c_i x^i$ be a monic polynomial (i.e. $c_n = 1$) and let $A = [a_{i,j}]$ where $a_{i,j} = -c_{i-1}$ if $j = n$, 1 if $i = j+1$, and 0 otherwise. Show that $c_A(x) = p(x)$.

Recall that $c_A(x) = \mathsf{det}(xI - A) = \mathsf{det}([x\delta_{i,j} - a_{i,j}])$, where $\delta_{i,j} = 1$ if $i = j$ and 0 otherwise.

Using the Cofactor Expansion Formula along the $n$th column (derived here), we have $\mathsf{det}(xI-A) = \sum_{i=1}^n (-1)^{i+n} (x \delta_{i,n} - a_{i,n}) \mathsf{det}(M_{i,n})$, where $M_{i,n}$ denotes the $(i,n)$ matrix minor of $xI - A$.

Evidently, we have that $(M_{k,n})_{i,j} = x$ if $i = j < k$, $-1$ if $i = j \geq k$, $-1$ if $i = j+1$ and $i < k$, $x$ if $i = j-1$ and $i \geq k$, and 0 otherwise. So $M_{k,n} = \begin{bmatrix} L & 0 \\ 0 & U \end{bmatrix}$, where $L$ is lower triangular of dimension $k-1$ and diagonal entries equal to $x$ and $U$ is upper triangular of dimension $n-k$ and diagonal entries equal to $-1$. So we have $\mathsf{det}(M_{k,n}) = (-1)^{n-k}x^{k-1}$.

So we have $c_A(x) = \sum_{i=1}^n (-1)^{i+n} (x \delta_{i,n} - a_{i,n}) (-1)^{n-i} x^{i-1}$ $= \sum_{i=1}^n (-1)^{2n} (x\delta_{i,n} - a_{i,n}) x^{i-1}$ $= x^n + \sum_{i=1}^n (-a_{i,n})x^{i-1}$ $= x^n + \sum_{i=1}^n c_{i-1}x^{i-1}$ $= x^n + \sum_{i=0}^{n-1} c_ix^i$ $= p(x)$ as desired.

This proof is incorrect, since $M_{k,n}$ is clearly not upper triangular for $k>1$. Instead it is block-triangular (i.e., of 2×2 block form with the lower left block null and touching the diagonal) with the top-left block, square of size $k-1$, being LOWER triangular with $x$’s on the diagonal, and the bottom right block of siwe $n-k$ being upper triangular with $-1$’s on the diagonal.