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
$$\begin{matrix} $\left( \begin{array}{ccccc}
c_1 & s_1c_2 & s_1s_2c_3 & s_1s_2s_3c_4 & \ldots \end{matrix}$$
$$\begin{matrix} \
-s_1 & c_1c_2 & c_1s_2c_3 & c_1s_2s_3c_4 & \ldots \end{matrix}$$
$$\begin{matrix} \
0 & -s_2 & c_2c_3 & s_2s_3c_4 & \ldots \end{matrix}$$
$$\begin{matrix} \
0 & 0 & -s_3 & c_3c_4 & \ldots \end{matrix}$$
$$\begin{matrix} \
0 & 0 & 0 & -s_4 & \ldots
\end{matrix}$$
$$\ldots$$
end{array} \right)$$
where $(c_j,s_j)$ are cosine/sine pairs.
