Non-sparse Companion Matrices

Given a polynomial $p(z)$, a companion matrix can be thought of as a simple template for placing the coefficients of $p(z)$ in a matrix such that the characteristic polynomial is $p(z)$. The Frobenius companion and the more recently-discovered Fiedler companion matrices are examples. Both the Frobenius and Fiedler companion matrices have the maximum possible number of zero entries, and in that sense are sparse. In this paper, companion matrices are explored that are not sparse. Some constructions of non-sparse companion matrices are provided, and properties that all companion matrices must exhibit are given. For example, it is shown that every companion matrix realization is non-derogatory. Bounds on the minimum number of zeros that must appear in a companion matrix, are also given.