Eigenvalues of companion matrix of $4x^3 - 3x^2 + 9x - 1$ I want to find all the roots of a polynomial and decided to compute the eigenvalues of its companion matrix.
How do I do that?
For example, if I have this polynomial: $4x^3 - 3x^2 + 9x - 1$, I compute the companion matrix:
$$\begin{bmatrix} 0&0&\frac{3}{4} \\ 1&0&-\frac{9}{4} \\ 0&1&\frac{1}{4} \end{bmatrix}$$
Now how can I find the eigenvalues of this matrix? Thanks in advance.  
 A: Hey There, so if I am assuming correctly for your case, you want to find eigenvalues for this matrix, which is essentially solving for your roots of the characteristic polynomial of the matrix after doing the determinant operation on it. So to go off from Robert idea, we want to use the equation,
det(A$-\lambda$ I) = $0$ $~~~$(following from this we can plug in the coefficient matrix given).
det(A$-\lambda$ I) = 
$\left[\begin{array}{ccc}
0-\lambda & 0 & \dfrac{3}{4} \\ 
1 & 0-\lambda & -\dfrac{9}{4} \\ 
0 & 1 & \dfrac{1}{4}-\lambda
\end{array} \right] = 0$, where A is your coefficient matrix and I is the identity matrix.
I = $\left[\begin{array}{ccr}
1 & 0 & 0 \\ 
0 & 1 & 0 \\ 
0 & 0 & 1
\end{array} \right]$
From here we can now find out the eigenvalues of the matrix A as follows:
$\underline {\text{Evaluation of the determinant expanding it by the minors of column 1:}}$
= $~-\lambda
\left[\begin{array}{cc}
            -\lambda & -\dfrac{9}{4} \\ 
            1 & \dfrac{1}{4}-\lambda  
\end{array} \right]
-1
\left[\begin{array}{cc}
            0 & \dfrac{3}{4} \\ 
            1 & \dfrac{1}{4}-\lambda  
\end{array} \right]
+ 0
\left[\begin{array}{rr}
            0 & \dfrac{3}{4} \\ 
            -\lambda & -\dfrac{9}{4}  
\end{array} \right]
$ 
$\Rightarrow ~ -\lambda
\left[\begin{array}{c}
            \lambda^{2} -\dfrac{1}{4}\lambda + \dfrac{9}{4} \\   
\end{array} \right]
-1
\left[\begin{array}{cc}
            0 -\dfrac{3}{4} \\   
\end{array} \right] 
+ ~0
\left[\begin{array}{rr}
            0 + \dfrac{3}{4}\lambda \\   
\end{array} \right]
$ 
$\Rightarrow ~$ $-\lambda^3+\dfrac{1}{4}\lambda^2-\dfrac{9}{4}\lambda+\dfrac{3}{4}$, $~$ Hence our characteristic polynomial is now obtained. 
$$P(\lambda)=-\lambda^3+\dfrac{1}{4}\lambda^2-\dfrac{9}{4}\lambda+\dfrac{3}{4}$$
If you need assistance on how to find the characteristic polynomial by evaluating the determinant, here is a reference: Computing Determinants
\
After solving this polynomial for its roots (eigenvalues) we get the following: 
{$\lambda = (0.329,0.000) ~~ \lambda = (-0.040,-1.508) ~~ \lambda = (-0.040,1.508)$} 
I believe all the roots except for $\lambda = 0.329$ are complex conjugate roots. Can someone else please verify that those are all of the roots to this polynomial and that the ones I provided are correct, Thanks. I hope this helps out if this explanation is what you were looking for. 
A: Typically, one uses the QR algorithm on a matrix with a preliminary reduction to upper Hessenberg form (all zeroes below the subdiagonal) for determining the eigenvalues. However, since the Frobenius companion matrix is already Hessenberg to begin with, it can easily be fed into an eigenroutine without preliminary transformation (though a preliminary balancing might be necessary if the coefficients of the polynomial vary widely in magnitude).
However, it is a rather wasteful algorithm: the Frobenius companion matrix is sparse, and subjecting it to the QR algorithm causes the zeroes above the subdiagonal to be filled in quickly. However, there are now new methods that exploit the sparsity of the Frobenius companion matrix; if you're sure you do not want to investigate other methods, you should look into this new development.
A: You may want to take a look at Companion matrix to be sure that you have the right companion matrix. 
In order to find the eigenvalues of a square matrix, you need to solve
$\text{det}(A-\lambda I)=0$
where A is the matrix you are interested in and I is the identity matrix. 
You can find a couple of examples here.
