using Plots, LinearAlgebra

All roots of Polynomial: method of Companion Matrix

The problem of finding all the roots of a polynomial

$$ p(x) = x^N + \left( c_0 + c_1 x + c_2 x^2 + \ldots + c_{N-1} x^{N-1} \right) $$

can be formulated as that of finding all the eigenvalues of the companion matrix $\mathcal{C}$:

$$ \begin{aligned} \mathcal{C} = \begin{bmatrix} 0 & 0 & 0 & \ldots & -c_0 \\ 1 & 0 & 0 & \ldots & -c_1 \\ 0 & 1 & 0 & \ldots & -c_3 \\ & & \ldots & & \\ 0 & 0 & \ldots & 1 & -c_{N-1} \end{bmatrix} \end{aligned} $$

function Cmatrix(cv)
    
    ndim = length(cv)
    cmat = zeros(ndim, ndim)

    for i1 in 2:ndim
        cmat[i1, i1-1] = 1
    end

    cmat[:, end] .= -cv[:]
    return cmat
    
end

Cmatrix (generic function with 1 method)

cv = [0.5, 0.8, -0.7, 2.0]

p_poly = x -> x^4 + cv[1] + cv[2]*x + cv[3]*x^2 + cv[4]*x^3 
eigen(Cmatrix(cv)).values

4-element Vector{ComplexF64}:
  -2.3952925651438783 + 0.0im
 -0.38303594384056605 + 0.0im
  0.38916425449222247 - 0.6273119801408027im
  0.38916425449222247 + 0.6273119801408027im

# only complex roots show up
plot(range(-3, 1, length=40), p_poly, label="p(x)", xlabel="x")