The eigenvalues of a square matrix $A$ coincide with the roots of its characteristic polynomial $p[A]$. Conversely, if I have a polynomial
$$
a_0 + a_1 x + \cdots + a_{n-1}x^{n-1} + x^n ~,
$$
I can define a companion matrix
$$
A[p]=\begin{bmatrix}
0 & 0 & \dots & 0 & -a_0 \\
1 & 0 & \dots & 0 & -a_1 \\
0 & 1 & \dots & 0 & -a_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \dots & 1 & -a_{n-1}
\end{bmatrix}.$$
The characteristic polynomial of the matrix $A[p]$ is the original polynomial $p$.
The companion matrix defined in this way is not Hermitian.
Edit: Consider only hyperbolic polynomials, i.e., polynomials which have only real roots.
However, the companion matrix is not the only matrix whose characteristic polynomial is the polynomial $p$. For an example, just consider the diagonal matrix of the eigenvalues ${\rm diag}{(\lambda_1,\lambda_2,\ldots,\lambda_n)}$. This matrix is indeed Hermitian, but one needs to calculate eigenvalues, which can be a difficult task for large matrix sizes.
Therefore my question is:
Is it possible to define a "companion" matrix (a matrix whose characteristic polynomial is the given polynomial $p$) which is Hermitian, and which is easier to calculate than the diagonal matrix of the eigenvalues ${\rm diag}{(\lambda_1,\lambda_2,\ldots,\lambda_n)}$? With easy to calculate I mean a matrix which can be written in terms of the parameters $a_i$ and without calculating the eigenvalues.
Best Answer
The answer is no in general since Hermitian matrices have real eigenvalues. So for example, there is no Hermitian matrix whose characteristic polynomial is $X^2+1$.
Even if you restrict to polynomials with real roots, I doubt you can find a simple formula : I think that if there is a rational formula that works for every polynomial with real roots, it should also apply to all polynomials. Let me explain what I mean precisely. We'll use the following lemma which states that when rational equations hold for polynomial with real roots, they should hold everywhere. Denote $\mathbb{C}_{n,u}[X]$ the set of monic complex polynomials of degree $n$.
Lemma : Let $f$ be a rational function
$$\begin{eqnarray*}f :& \mathbb{C}_{n,u} & \longrightarrow \mathbb{C}^N\\ & P &\longmapsto f(P)\end{eqnarray*}$$
such that $f$ is zero on polynomial with real roots. Then $f$ is zero.
Proof :
The map
$$\begin{eqnarray*}p_n :& \mathbb{C}^n & \longrightarrow \mathbb{C}_{n,u}[X]\\ & (\lambda_1, \ldots, \lambda_n) &\longmapsto p_n(\lambda_1, \ldots, \lambda_n) = \prod_{i = 1}^n (X-\lambda_i)\end{eqnarray*}$$
is also a rational map (meaning the coefficients of a polynomial are rational functions of its roots, and we can actually compute them, those are called elementary symmetric polynomials). By hypothesis, the function $f \circ p_n$ is zero on $\mathbb{R}^n$. But since $f \circ p_n$ is rational, it is actually zero everywhere, and because $p_n$ is surjective (every polynomial is split in $\mathbb{C}$), then $f$ is zero.
Now assume there is a rational function
$$\begin{eqnarray*}A_n :& \mathbb{C}_{n,u}[X] & \longrightarrow \mathcal{M}_n(\mathbb{C})\\ & P &\longmapsto A_n(P)\end{eqnarray*}$$
(by that I mean that the coefficients of the matrix $A_n(P)$ are rational functions of the coefficients of $P$) such that the characteristic polynomial of $A_n(P)$ is $P$ whenever $P$ has real roots. This means the rational function $P \longmapsto \det(XI_n - A_n(P)) - P$ is zero on polynomial with real roots, so it's zero everywhere, which means the characteristic polynomial of $A_n(P)$ is always $P$ without assumption on the roots of $P$.
Assume moreover that $A_n(P)$ is hermitian whenever $P$ has real roots. Then I claim $A_n(P)$ is hermitian for any real polynomial $P$ from the same kind of argument. Indeed denote $A_n^* : P \longmapsto \left[A_n(P^*)\right]^*$, where $P^*$ denotes the complex conjugate of the polynomial $P$, and $\left[A_n(P^*)\right]^*$ is the conjugate transpose of the matrix $A_n(P^*)$. This is a rational function (beware that $P \mapsto [A_n(P)]^*$ is not rational however !). Our assumption is that the rational function $A_n - A_n^*$ is zero on all polynomial with real roots, so it's zero everywhere. When $P$ is real, this means $A_n(P)$ is hermitian (because $A_n(P) = A_n^*(P) = [A_n(P)]^*$, the last equality being only true when $P$ is real). This yields a contradiction if $P$ is a real polynomial with complex roots.