# Is it possible to find a companion matrix of a polynomial which is also hermitian?

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.

• Presumably this should be for the case where the $\lambda_j$ are all real. The existence of such a matrix would then constitute a proof that the given polynomial's roots are all real. That doesn't make things hopeless, since there are methods (e.g. with Sturm's theorem) for deciding this without computing the computing the roots, but it does mean it's not going to be trivial. – Robert Israel Jul 31 '15 at 23:33
• Assume all eigenvalues are real (see edits). I am not interested only in the existence but rather on how to calculate that. An idea that comes to my mind (but perhaps is wrong) is to use a unitary transformation to make the companion matrix hermitian. – sintetico Jul 31 '15 at 23:35
• A unitary transformation can't make something hermitian unless it's already hermitian. – Robert Israel Jul 31 '15 at 23:37
• so I was right regarding the fact that I was wrong... – sintetico Jul 31 '15 at 23:38

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.

• Ok, I am sorry I was not clear. Let us consider only polynomials which have real roots and no complex root. Could you please be so nice to delete this answer, or better consider the case of polynomials with real roots? – sintetico Jul 31 '15 at 23:30
• Please don't delete it. The observation was a good answer to the original form of the question, and helps narrow down the possibilities for an answer to the revised question. – Robert Israel Jul 31 '15 at 23:40
• I hope that other people will answer though... – sintetico Jul 31 '15 at 23:42
• Well, this also does not answer my question. You demonstrate that if there is a rational formula to obtain a generalized companion matrix from the Frobenius companion matrix, this holds both for if eigenvalues are real or complex. However, this gives no information on the hermitianicity of the resulting generalized companion matrix in the case that eigenvalues are real. Also, I am not searching for theorem of existence here, but with how this generalized matrix can be constructed. – sintetico Aug 1 '15 at 12:08
• @sintetico : I think it does answer at least partly. I've inserted an explanation as to why if such a "rational companion matrix" were Hermitian for hyperbolic polynomials, it should also be hermitian for all real polynomials (which is impossible from the first observation). I'm sorry, but it's rather a result of non existence... – Joel Cohen Aug 1 '15 at 14:12

It's a little sad to see the previous discouraging answer accepted relatively quickly. In fact, there is a construction due to Miroslav Fiedler and improved by Gerhard Schmeisser that constructs a tridiagonal matrix whose characteristic polynomial is (up to a constant factor) the input polynomial, by using a modified Euclidean algorithm to effectively generate Sturmian sequences (which was mentioned by Robert Israel in a comment to the OP). If the subdiagonal elements ($$c_k$$ in the notation of Schmeisser's paper) generated are all positive, then the tridiagonal matrix is indeed symmetric, and thus has its roots all real.

See the papers for more details. Mathematica code implementing the construction can be found here; it should not be too difficult to adapt it to other languages.