{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

# Characteristic polynomial

## Problem

Let

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
1 & 4 & 16 & 64
\end{bmatrix}.
$$

Find the characteristic polynomial $p_A(x)$ of $A$.

## Thought

There are several ways to compute $p_A(x) = \det(A - xI)$, including the Laplace expansion and the permutation expansion. They are doable, but it would be easier to compute $p_A(x)$ by the formula

$$
p_A(x) = (-x)^n + s_1(-x)^{n-1} + \cdots + s_n,
$$

where

$$
s_k = \sum_{\substack{\alpha\subseteq [n]\\|\alpha| = k}}\det(A[\alpha]).
$$

## Sample answer

For $k = 1$, the set $\alpha$ can be $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$. The corresponding matrices $A[\alpha]$ are $\begin{bmatrix} 1 \end{bmatrix}$, $\begin{bmatrix} 2 \end{bmatrix}$, $\begin{bmatrix} 9 \end{bmatrix}$, $\begin{bmatrix} 64 \end{bmatrix}$ with their determinant $1$, $2$, $9$, $64$, respectively. Therefore,

$$
s_1 = \tr(A) = 1 + 2 + 9 + 64 = 76.
$$

For $k = 2$, the set $\alpha$ can be

$$
\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}.
$$

The corresponding matrices $A[\alpha]$ are

$$
\begin{bmatrix}
1 & 1 \\
1 & 2
\end{bmatrix},
\begin{bmatrix}
1 & 1 \\
1 & 9
\end{bmatrix},
\begin{bmatrix}
1 & 1 \\
1 & 64
\end{bmatrix},
\begin{bmatrix}
2 & 4 \\
3 & 9
\end{bmatrix},
\begin{bmatrix}
2 & 8 \\
4 & 64
\end{bmatrix},
\begin{bmatrix}
9 & 27 \\
16 & 64
\end{bmatrix}
$$

with their determinant $1$, $8$, $63$, $6$, $96$, $144$, respectively. Therefore,

$$
s_2 = 1 + 8 + 63 + 6 + 96 + 144 = 318.
$$

For $k = 3$, the set $\alpha$ can be

$$
\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}.
$$

The corresponding matrices $A[\alpha]$ are

$$
\begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix},
\begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 8 \\
1 & 4 & 64
\end{bmatrix},
\begin{bmatrix}
1 & 1 & 1 \\
1 & 9 & 27 \\
1 & 16 & 64
\end{bmatrix},
\begin{bmatrix}
2 & 4 & 8 \\
3 & 9 & 27 \\
4 & 16 & 64
\end{bmatrix}
$$

with their determinant $2$, $42$, $114$, $48$, respectively. Therefore,

$$
s_3 = 2 + 42 + 114 + 48 = 206.
$$

For $k = 4$, the only $\alpha$ is $\{1,2,3,4\}$ and $A[\alpha] = A$. Since $A$ is a [Vandermonde matrix](https://en.wikipedia.org/wiki/Vandermonde_matrix), one may easily calculate its determinant

$$
s_4 = \det(A) = 12.
$$

In summary, the characteristic polynomial is

$$
\begin{aligned}
p_A(x) &= (-x)^4 + s_1(-x)^3 + s_2(-x)^2 + s_3(-x) + s_4 \\
&= x^4 - 76x^3 + 318x^2 - 206x + 12.
\end{aligned}
$$

## Note

With Sage, you may run the code below or simply click [here](https://sagecell.sagemath.org/?q=nzefbn) to find the answer.

A = matrix([
    [1,1,1,1],
    [1,2,4,8],
    [1,3,9,27],
    [1,4,16,64]
])
n = A.dimensions()[0]

show((-1)**n * A.charpoly())

*This note can be found at Course website > Learning resources.*