Characteristic polynomial of a matrix with zeros on its diagonal

Let $p(x)=x^n+a_{n-2}x^{n-2}+a_{n-3}x^{n-3}+\cdots+a_1x+a_0=(x-\lambda_1)\cdots(x-\lambda_n)$ be a polynomial with real coefficients such that every $\lambda_i$ is real.

Is there always a symmetric real $n\times n$ matrix $M$, containing only zeros on its main diagonal such that its characteristic polynomial is $p$?

-
Are $\lambda_i$ known? Or is a better solution one that uses only the $a_i$? –  adam W Dec 22 '12 at 20:50

The answer is affirmative. The conceptual construction of that zero-diagonal real symmetric matrix is rather easy. We begin with $D=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$. Let $Q$ be a real orthogonal matrix with its last column equal to $u=\frac{1}{\sqrt{n}}(1,\ldots,1)^T$ (e.g. you may consider the Householder reflection $Q=I-2vv^T/\|v\|^2$, where $v^T=u^T-(0,\ldots,0,1)$). Then $D\leftarrow Q^TDQ$ would become a real symmetric matrix whose $(n,n)$-th entry is zero. Now perform the similar procedure recursively on the leading principal submatrices of $D$, we obtain the desired matrix.

-
I agree that this answer is concise in addressing the existence question, but would like to point out that it requires more computation since it must use the leading principal submatrices at each step. I would like to also point out that this is the only answer of @user1551 that I did not completely like (Householder is better than Givens only in the non-sparse general case, not I think in this case, again speaking in terms of computation count). –  adam W Dec 25 '12 at 18:13
@adamW I completely agree to your point about Householder vs Givens. (Actually one upvote to you was mine, exactly for this reason.) Yet, apart from conceptual similicity, I used Householder reflection in my answer because it can deal with a more general theoretical problem: is every traceless complex square matrix similar to some matrix with zero diagonal? We can play the same Householder trick here, but the Givens trick is not applicable. –  user1551 Dec 26 '12 at 0:14
I like your theoretical treatment, I personally just tend to think more in terms of computational practicality. I believe the $2 \times 2$ case is still possible even with complex values (not sure if it would still be called Givens in that case), but definitely would not be as conceptually simple! –  adam W Dec 26 '12 at 21:01
@adamW Ahh, yes, you are right. It is possible to kill a diagonal entry via a similarity transform, although this may not be acieved by unitary equivalence. I should have explained things like this, then the explanation would not be as clumsy as it was. :-( –  user1551 Dec 27 '12 at 6:27
I believe that if the matrix is complex hermitian, then the transform may work (kill a diagonal entry) with a unitary matrix. The Givens plane rotation would be of the form $\pmatrix{c & s \\ -s^* & c^*}$. I do not see yet how it would be impossible (though maybe it is) to do something for the general complex matrix. If the possibility interests you enough, I can think on it some more. –  adam W Dec 28 '12 at 21:44

It is sufficient to look at the $2 \times 2$ case since if the $\lambda_i$ are known, start with the diagonal matrix and operate on the sub matrices. Pick two along the diagonal that are opposite in sign (this is always possible since the trace is zero).

An orthogonal matrix $\pmatrix{c & s \\ -s & c}$ is desired such that:

$$\pmatrix{c & s \\ -s & c}\pmatrix{\lambda_0 & 0 \\ 0 & \lambda_1}\pmatrix{c & s \\ -s & c}^{-1}=\pmatrix{0 & * \\ * & \lambda_0 + \lambda_1}$$

where $c^2 + s^2 =1$. This is the same as: \begin{align} \pmatrix{c & s \\ -s & c}\pmatrix{\lambda_0 & 0 \\ 0 & \lambda_1}\pmatrix{c & -s \\ s & c}&=\pmatrix{0 & * \\ * & \lambda_0 + \lambda_1} \\ \pmatrix{\lambda_0 c & \lambda_1 s \\ -\lambda_0 s & \lambda_1 c}\pmatrix{c & -s \\ s & c}&=\pmatrix{0 & * \\ * & \lambda_0 + \lambda_1} \\ \pmatrix{\lambda_0 c^2 + \lambda_1 s^2 & (\lambda_1 -\lambda_0) cs \\ (\lambda_1 -\lambda_0) cs & \lambda_1 c^2 + \lambda_0 s^2}&=\pmatrix{0 & * \\ * & \lambda_0 + \lambda_1} \\ \end{align}

Since it is a similarity, only the equation $\lambda_0 c^2 + \lambda_1 s^2=0$ need be solved and the trace value of $\lambda_0 + \lambda_1$ will naturally follow. Since $\lambda_0$ and $\lambda_1$ are opposite in sign, it can be solved with using only real values for $c$ and $s$.

Repeat the procedure on the sub matrices with each pair of non-zero diagonal values (the off diagonals of the sub matrices will remain as $0$ values). The end result of the entire matrix will be zero along the diagonal, since the trace is zero and all the diagonal elements are made to be zero.

It is possible to do a similar technique using only the $a_i$, beginning with the companion matrix, and finding a symmetric similarity. It is possible yet more involved to do such, but then would also not have zero elements along the sub matrix off diagonals. It also would be still possible yet slightly more complicated to deal with those non zero elements.

-
You're assuming the matrix is traceless since otherwise every matrix in its conjugacy class has some nonzero element on its diagonal, right? –  Neal Dec 22 '12 at 20:54
@Neal: Look at the definition of $p$. The coefficient of $x^{n-1}$ was assumed to be $0$. –  Dominik Dec 22 '12 at 20:57
@Dominik Oops, I missed that. Thank you! –  Neal Dec 22 '12 at 22:00