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 nth 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.

Post a comment or leave a trackback: Trackback URL.


  • Marc van Leeuwen  On November 4, 2011 at 5:11 am

    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.

    • nbloomf  On November 4, 2011 at 8:17 am

      Thanks! I think it is fixed now.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: