# Tagged: companion matrix

## Problem 348

Let $A$ be an $n\times n$ complex matrix.
Let $p(x)=\det(xI-A)$ be the characteristic polynomial of $A$ and write it as
$p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,$ where $a_i$ are real numbers.

Let $C$ be the companion matrix of the polynomial $p(x)$ given by
$C=\begin{bmatrix} 0 & 0 & \dots & 0 &-a_0 \\ 1 & 0 & \dots & 0 & -a_1 \\ 0 & 1 & \dots & 0 & -a_2 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \dots & 1 & -a_{n-1} \end{bmatrix}= [\mathbf{e}_2, \mathbf{e}_3, \dots, \mathbf{e}_n, -\mathbf{a}],$ where $\mathbf{e}_i$ is the unit vector in $\C^n$ whose $i$-th entry is $1$ and zero elsewhere, and the vector $\mathbf{a}$ is defined by
$\mathbf{a}=\begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{bmatrix}.$

Then prove that the following two statements are equivalent.

1. There exists a vector $\mathbf{v}\in \C^n$ such that
$\mathbf{v}, A\mathbf{v}, A^2\mathbf{v}, \dots, A^{n-1}\mathbf{v}$ form a basis of $\C^n$.
2. There exists an invertible matrix $S$ such that $S^{-1}AS=C$.
(Namely, $A$ is similar to the companion matrix of its characteristic polynomial.)

## Problem 88

A complex number $z$ is called algebraic number (respectively, algebraic integer) if $z$ is a root of a monic polynomial with rational (respectively, integer) coefficients.

Prove that $z \in \C$ is an algebraic number (resp. algebraic integer) if and only if $z$ is an eigenvalue of a matrix with rational (resp. integer) entries.

Read solution

## Problem 85

Consider a polynomial
$p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,$ where $a_i$ are real numbers.
Define the matrix
$A=\begin{bmatrix} 0 & 0 & \dots & 0 &-a_0 \\ 1 & 0 & \dots & 0 & -a_1 \\ 0 & 1 & \dots & 0 & -a_2 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \dots & 1 & -a_{n-1} \end{bmatrix}.$

Then prove that the characteristic polynomial $\det(xI-A)$ of $A$ is the polynomial $p(x)$.
The matrix is called the companion matrix of the polynomial $p(x)$.