# Computing an orthogonal matrix subject to linear constraints

I am looking for a method to solve the matrix equation $$DXa = Xb$$ where $D\in \mathbb{R}^{n\times n}$ is diagonal, $a, b\in \mathbb{R}^{n}$ and $X$ is the unknown orthogonal $n\times n$ matrix such that $X^TX = I$. The matrices $a$ and $b$ have unit norm, and $D$ has diagonal entries of unit magnitude, so that the matrix equation is consistent.

-
This looks heavily underdetermined, as you want to solve $n$ equations for $n(n-1)/2$ variables. Is what you wrote really what you want? –  Arnold Neumaier Nov 19 '12 at 11:57
Yes, it is underdetermined. For now, I am interested in finding any solution. –  Victor Liu Nov 19 '12 at 13:09
Why do your conditions on $a$, $b$, and $D$ imply the consistency of the equations? For $n=1$ consistency already requires the additional condition $Da=b$. –  Arnold Neumaier Nov 19 '12 at 15:14
All I meant was I believe that there should always be a solution. For me D is in practice something like +1, -1, +1, -1, ... on the diagonal. –  Victor Liu Nov 19 '12 at 20:32

Generalizing Arnold's example, suppose $D = I$. Then the problem is to find an orthogonal $X$ satisfying $X(a-b) = 0$, which is possible only when $a = b$.

Interestingly, in 2D with $D = \text{diag}(1, -1)$, one can always find a plane rotation $X$ that does the job. Evidently the solvability for arbitrary unit-norm $a$, $b$ depends only on $D$. What is the general condition that makes the problem solvable? Is it something like $D$ has negative determinant, i.e., it has an odd number of -1's on the diagonal?

-
In your example, if we generalize from dimension two to dimension $2n$, with $D = \mathrm{diag}(I,-I)$, is it still always possible? Because that is essentially the problem I have (I think for me the dimension is actually $2n+1$ with the $I$ block being of size 1 larger than the $-I$ block). –  Victor Liu Nov 22 '12 at 7:36

Your belief that there should always be a solution is wrong for $n=1$ if $D=a=1$ and $b=-1$, which satisfies all your requirements.

Thus it seems unlikely that one can say anything in general.

Posing the linear and the orthogonality constraint as a least squares problems in the Frobenius norm, and submitting it to an unconstrained optimization routine is probably the only thing one can do.

-
What I meant was I believe the input data should always be consistent. I was thinking there is a variation of Gram-Schmidt that can make this work, but I can't seem to figure it out. –  Victor Liu Nov 19 '12 at 21:15