Numerical Analysis HT24, Eigenvalues
Flashcards
Suppose $f(x) = \sum^n _ {i = 0} c _ i x^i$ and $c _ n \ne 0$. How is the companion matrix for $f$ defined, first in Course - Numerical Analysis HT24U and then in Course - Rings and Modules HT24U?
Numerical analysis definition:
\[\begin{bmatrix} -\frac{c _ {n-1} }{c _ n} & -\frac{c _ {n-2} }{c _ n} & \cdots & -\frac{c _ 1}{c _ n} & -\frac{c _ 0}{c _ n} \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}\]Rings and modules definition:
\[\begin{bmatrix} 0 & 0 & \cdots & 0 & -\frac{c _ 0}{c _ n} \\ 1 & 0 & \cdots & 0 & -\frac{c _ 1}{c _ n} \\ 0 & 1 & \cdots & 0 & \vdots \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & -\frac{c _ {n-1} }{c _ n} \end{bmatrix}\]The companion matrix for $f(x) = \sum^n _ {i = 0} c _ i x^i$ is defined as
\[C = \begin{bmatrix} -\frac{c _ {n-1} }{c _ n} & -\frac{c _ {n-2} }{c _ n} & \cdots & -\frac{c _ 1}{c _ n} & -\frac{c _ 0}{c _ n} \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}\]
How can you quickly justify that the eigenvalues of $C$ are the roots of $f$?
If $p(\lambda) = 0$, then $Cx = \lambda x$ where
\[x = \begin{bmatrix}\lambda^{n-1} \\ \lambda^{n-2} \\ \vdots \\ \lambda \\ 1\end{bmatrix}\]since all but the top row shift the entries of the vectors “up by one”, and then at the top row we end up with $-\sum^{n-1} _ {i = 0} \frac{c _ {i} }{c _ n} \lambda^i = \lambda^n$ by the fact that $\lambda$ is a root.
Bite-sized
Why does the companion-matrix construction imply no finite-step eigenvalue algorithm exists for $n \ge 5$?
Every polynomial $p$ of degree $n$ is the characteristic polynomial of some companion matrix $C$. A finite-step eigenvalue algorithm would compute the eigenvalues of $C$ (= roots of $p$) in finitely many arithmetic operations — but by Abel-Galois, no formula in radicals exists for general degree-$n \ge 5$ polynomials. So no such algorithm exists; eigenvalue computation is necessarily iterative.
The companion-matrix eigenvector for eigenvalue $\lambda$ (NA HT24 convention with $-c _ i/c _ n$ in the top row) is $x = $ $[\lambda^{n-1}, \lambda^{n-2}, \ldots, \lambda, 1]^\top$.