An orthogonal companion matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:05:24Z http://mathoverflow.net/feeds/question/38943 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38943/an-orthogonal-companion-matrix An orthogonal companion matrix Denis Serre 2010-09-16T09:22:58Z 2010-10-11T08:00:17Z <p>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 <em>orthogonal companion matrix</em> of $P$, in short OCM). See for instance Exercise 99 on my list <a href="http://www.umpa.ens-lyon.fr/~serre/DPF/exobis.pdf" rel="nofollow">http://www.umpa.ens-lyon.fr/~serre/DPF/exobis.pdf</a> . Regretfully, this exercise uses the square root of Hermitian positive definite matrices, which cannot be computed in finitely many operations.</p> <p>Does there exist a construction of an OCM that uses only finitely many elementary operations (including the square root of complex numbers) ?</p> <p>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 &amp; s_1c_2 &amp; s_1s_2c_3 &amp; s_1s_2s_3c_4 &amp; \ldots \\ -s_1 &amp; c_1c_2 &amp; c_1s_2c_3 &amp; c_1s_2s_3c_4 &amp; \ldots \\ 0 &amp; -s_2 &amp; c_2c_3 &amp; s_2s_3c_4 &amp; \ldots \\<br> 0 &amp; 0 &amp; -s_3 &amp; c_3c_4 &amp; \ldots \\ 0 &amp; 0 &amp; 0 &amp; -s_4 &amp; \ldots<br> \end{array} \right)$$ where $(c_j,s_j)$ are cosine/sine pairs.</p> http://mathoverflow.net/questions/38943/an-orthogonal-companion-matrix/38989#38989 Answer by Victor Protsak for An orthogonal companion matrix Victor Protsak 2010-09-16T16:22:45Z 2010-09-16T16:22:45Z <p>You can use the <a href="http://en.wikipedia.org/wiki/Cayley_transform" rel="nofollow">Cayley transform</a> and reduce this problem to generating a skew-symmetric matrix with a prescribed characteristic polynomial. For example, this works in the $3\times 3$ case (although when $n$ is odd, $1$ is always an eigenvalue). I have not thought about it thoroughly, but presumably, methods used in Inverse Symmetric Eigenvalue Problem should apply in the skew-symmetric case. </p> http://mathoverflow.net/questions/38943/an-orthogonal-companion-matrix/38999#38999 Answer by David Speyer for An orthogonal companion matrix David Speyer 2010-09-16T17:35:44Z 2010-09-17T11:11:09Z <p>I'd do this in three steps:</p> <ol> <li><p>Find any $2n \times 2n$ matrix $A$ whose eigenvalues are $e^{\pm i \theta}$.</p></li> <li><p>Find a positive definite quadratic form preserved by $A$. In equations, we want $A P A^T = P$. </p></li> <li><p>Find an orthonormal basis for $P$, using the <a href="http://en.wikipedia.org/wiki/Gram-Schmidt" rel="nofollow">Gram-Schimdt algorithm</a>. In equations, we want $S P S^T = \mathrm{Id}$. </p></li> </ol> <p>Then $S A S^{-1}$ is orthogonal and has the required eigenvalues.</p> <hr> <p>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.</p> <p><strong>Algebra:</strong> 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.</p> <p>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$.</p> <p>Then <code>$\langle y,z \rangle = T(y*\overline{z})$</code> 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$.</p> <p><strong>In practice:</strong> 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$.</p>