Let $P\in{\mathbb R}[X]$ be a monic polynomial with roots on the unit circle. For the problem below, we may assume wlog that the roots are simple and distinct from $\pm1$. It can be shown that there exists a matrix $M\in{\bf SO}\_n({\mathbb R})$, whose characteristic polynomial is $P$ (an *orthogonal companion matrix* of $P$, in short OCM). See for instance Exercise 99 on my list <http://www.umpa.ens-lyon.fr/~serre/DPF/exobis.pdf> .
Regretfully, this exercise uses the square root of Hermitian positive definite matrices, which cannot be computed in finitely many operations.


Does there exist a construction of an OCM that uses only finitely many elementary operations (including the square root of complex numbers) ?


Thanks to the reduction to Hessenberg form, which can be done in finite time and which preserves the orthogonal group, we may restrict our attention to a Hessenberg orthogonal matrix $M$. It writes
$$\left( \begin{array}{ccccc}
 c\_1 & s\_1c\_2 & s\_1s\_2c\_3 & s\_1s\_2s\_3c\_4 & \ldots \\\\
-s\_1 & c\_1c\_2 & c\_1s\_2c\_3 & c\_1s\_2s\_3c\_4 & \ldots \\\\ 
0 & -s\_2 & c\_2c\_3 & s\_2s\_3c\_4 & \ldots \\\\ 
0 & 0 & -s\_3 & c\_3c\_4 & \ldots \\\\ 
0 & 0 & 0 & -s\_4 & \ldots 
 \end{array} \right)$$
where $(c\_j,s\_j)$ are cosine/sine pairs.



An orthogonal companion matrix
I'd do this in three steps:


1. Find any $2n \times 2n$ matrix $A$ whose eigenvalues are $e^{\pm i \theta}$.
2. Find a positive definite quadratic form preserved by $A$. In equations, we want $A P A^T = P$.
3. Find an orthonormal basis for $P$, using the [Gram-Schimdt algorithm](http://en.wikipedia.org/wiki/Gram-Schmidt). In equations, we want $S P S^T = \mathrm{Id}$.


Then $S A S^{-1}$ is orthogonal and has the required eigenvalues.




---


I can think of two ways to do step 2. The first is more purely algebraic, the second I think would be much easier to implement.


**Algebra:** Let $f(x) = \prod\_{j=1}^{n} (x-e^{i \theta\_j}) (x - e^{-i \theta\_j}) = \prod (x^2 - 2 \cos \theta\_j + 1)$ be your characteristic polynomial. Let $V$ be the ring $\mathbb{R}[x]/f(x)$. Note $1$, $x$, ..., $x^{2n-1}$ is a basis for this ring, in which multiplication can be written down algebraically in terms of the coefficients of $f$. Also, multiplication by $x$ has the desired eigenvalues, so that accomplishes part 1.


For $y \in T$, let $T(y)$ be the trace of multiplication by $y$. Also, let $y \mapsto \overline{y}$ be the automorphism of $V$ induced by $x \mapsto x^{-1}$. Again, both of these can be written down, in the monomial basis, algebraically in terms of the coefficients of $f$.


Then $\langle y,z \rangle = T(y\*\overline{z})$ is the desired positive definite quadratic form. Namely, observe that the ring $V$ is isomorphic to $\mathbb{C}^{\oplus n}$. In terms of this isomorphism, $\langle (z\_1, \ldots, z\_n), (z\_1, \ldots, z\_n) \rangle = 2 \sum |z\_i|^2$.


**In practice:** The condition that $APA^T = P$ is a linear condition on $P$. Let $W$ be the subspace of the vector space of symmetric matrices where this condition is satisfied; finding $W$ is just algebra. Now, our goal is to find a positive definite element of $W$. For large $N$, $(1/N) \left( \mathrm{Id} + AA^T + A^2 (A^{T})^2 + \cdots + A^{N-1} (A^T)^{N-1} \right)$ is positive definite and is near $W$. I would guess that the orthogonal projection of this matrix onto $W$ would probably be positive definite for large $N$.


