# Solution for $Xa + X^Tb = c$ where $X^TX = I$?

There are three known $$n\times1$$ vectors: $$a, b, c$$, along with one unknown $$n\times n$$ matrix: $$X$$. I am only interested in the $$n={2,3}$$ cases.

$$X$$ is $$2\times 2$$ or $$3\times 3$$ rotation matrix with an unusual domain specific constriant:

• $$X^TX = XX^T = I$$
• $$Xa + X^Tb = c$$

Is there a solution for $$X$$ in terms of $$a,b,c$$? Based on where the problem came from, I know there isn't always a solution, but I have stumped myself trying to figure out how to solve it when there is one.

I have tried working out the $$2\times 2$$ case element-wise, and arrived at the following, equally(?) difficult problem:

$$X = \begin{bmatrix}x_{11} & x_{12} \\ -x_{12} & x_{11}\end{bmatrix}$$

$$\begin{bmatrix}a_1+b_1 & b_2-a_2 \\ a_2+b_2 & a_1-b_1\end{bmatrix}\begin{bmatrix}x_{11}\\x_{12}\end{bmatrix}=c$$

$$Ax = c$$ where $$x^Tx=1$$

$$$$Xa = \begin{bmatrix} a_1x_{1,1} + a_2x_{1,2}\\ a_1x_{2,1} + a_2x_{2,2}\\ \end{bmatrix}$$$$ and $$$$X^Tb = \begin{bmatrix} b_1x_{1,1} + b_2x_{2,1}\\ b_1x_{1,2} + b_2x_{1,2}\\ \end{bmatrix}$$$$ and $$$$Xa+X^Tb = \begin{bmatrix}a_1x_{1,1} + a_2x_{1,2} + b_1x_{1,1} + b_2x_{2,1}\\ a_1x_{2,1} + a_2x_{2,2}+ b_1x_{1,2} + b_2x_{2,2}\\ \end{bmatrix} = \begin{bmatrix}(a_1+b_1)x_{1,1} + a_2x_{1,2} + b_2x_{2,1}\\ (a_2+b_2)x_{2,2} + a_1x_{2,1} + b_1x_{1,2}\\ \end{bmatrix} = \begin{bmatrix}c_1 \\ c_2\\ \end{bmatrix}$$$$ but $$X$$ is a rotation matrix gives us that $$$$Xa+X^Tb = \begin{bmatrix}(a_1+b_1)\cos\theta - a_2\sin\theta + b_2\sin \theta \\ (a_2+b_2)\cos\theta + a_1\sin\theta - b_1\sin\theta\\ \end{bmatrix} = \begin{bmatrix}(a_1+b_1)\cos\theta +(b_2- a_2)\sin\theta \\ (a_2+b_2)\cos\theta + (a_1 - b_1)\sin\theta\\ \end{bmatrix}$$$$ (if you only have $$X^TX= I$$ then you have to consider the extra case there $$\sin \theta \to -\sin \theta$$; i.e. rotation composed with reflection. Notice that $$X$$ is a rotation implies $$X^TX= I$$!) and therefore that $$$$Xa+X^Tb = \begin{bmatrix}(a_1+b_1)\cos\theta +(b_2- a_2)\sin\theta \\ (a_2+b_2)\cos\theta + (a_1 - b_1)\sin\theta\\ \end{bmatrix} = \begin{bmatrix}c_1 \\ c_2\\ \end{bmatrix}$$$$ and therefore (by using the triangle inequality) you don't have a solution if for example $$$$\frac{|(a_1+b_1)|}{\sqrt{2}} +\frac{|(b_2- a_2)|}{\sqrt{2}} < |c_1|$$$$ and like wise for the second condition $$$$\frac{|(a_2+b_2)|}{\sqrt{2}} +\frac{|(a_1- b_1)|}{\sqrt{2}} < |c_2|$$$$ and you can probably come up with all kinds of other tests for failure, but here is the most general one:

An alternative/equivalent way to look at it is that you have an overdetermined system of 3 equations and 2 unknowns of the form

$$$$\begin{array} & ax & + & by & =& c_1\\ cx & + & dy & =& c_2 \\ x^2 & + & y^2 & =& 1 \\ \end{array}$$$$

where $$a = a_1+b_1$$ , $$b=a_2- b_2$$, $$c = a_2+b_2$$, and $$d = a_1- b_1$$; which is highly unlikely to have solutions.

Therefore you have solutions iff the solution to the system of equations $$$$\begin{array} & ax & + & by & =& c_1 \\ cx & + & dy & =& c_2 \\ \end{array}$$$$ also satisfies the condition $$x^2 + y^2 = 1$$.

If you want to work out the $$n=3$$ case you can do the same exact thing but use the Euler angles; it will be long and tedious but you can probably get some kind of condition on the solutions.

You can possibly try this as well. Note that the orthogonality requirement can be relaxed using Schur complement as $$\begin{bmatrix}I&X\\X^\top & I \end{bmatrix} \succeq 0$$. So, we have the following: $$\max_{X\in R^{n\times n}} ~~ ||c-Xa-X^\top b||_2\\ \hspace{-3cm}\mbox{subject to}\\ ~~~~~~~~~~~~\begin{bmatrix}I&X\\X^\top & I \end{bmatrix} \succeq 0.$$ Note that if the solution to this convex problem $$X^*$$ does not satisfy $$||c-Xa-X^\top b||^2_2=0$$, there does not exist a solution to the original problem.

Hope this partial treatment helps. And, thanks to Aaron for pointing out an error earlier.

• Note that $(Xa)^T(X^Tb)\neq a^Tb$.You don't end up with $X^TX$, you get $(X^T)^2$. – Aaron May 15 at 15:06
• Yikes! Thanks for that. My bad. Will think about getting around it. – DSM May 15 at 15:42

An obvious necessary condition is that |a|, |b| and |c| can be sides of a triangle. The two-dimensional case can be analyzed further geometrically. If the triangle inequalities are satisfied, there are vectors congruent to a and b which form a triangle with c. The condition you require is that these vectors can be obtained either by rotating a and b in opposite directions (if X is proper orthogonal, and in this case the bisector of the angle between a and b stays the same), or by reflection across some axis (if X is improper orthogonal).

As a beginning of a search for solutions, we can take norms of each side. We then get

$$||a||^2 + ||b||^2 + 2 b\cdot (X^2 a)=||c||^2,$$

which is enough to fix the angle between $$b$$ and $$X^2 a$$.

Similarly, multiplying through by $$X$$ and then dotting with $$b$$, we can conclude that

$$b\cdot (Xc)=||b||^2+b\cdot (X^2 a)=||b||^2+\frac{||c||^2-||a||^2-||b||^2}{2}=\frac{||b||^2+||c||^2-||a||^2}{2}.$$

Therefore, we know the angle that $$b$$ makes with $$Xc$$. Similar calculations show us the angle that $$a$$ makes with $$X^T c$$. In two dimensions, this is enough to find $$X$$ geometrically if it exists in most cases, and otherwise to say that there is no such solution. The geometry is slightly more involved in 3 dimensions, and I'm not immediately sure if there is more useful information to be extracted through dot products to help.

Here is an approach for $$\mathbb R^3$$, inspired by Michael Renardy's answer.

Let us temporarily expand the problem to $$Aa+Bb=c$$, where $$A,B\in O_n(\mathbb R)$$. Assuming that $$|a|,|b|$$, and $$|c|$$ satisfy the triangle inequality, we can find a solution, $$(A_0,B_0)$$. However, the space of all solutions is $$(MA_0,MB_0)$$ where $$Mc=c$$ and $$M\in O_n(\mathbb R)$$. Thus, we've reduced the problem to:

Given $$A,B\in O_n(\mathbb R)$$ and $$c\in \mathbb R^n$$, does there exist $$X\in O_n(\mathbb R)$$ such that $$Xc=c \quad \text{and} \quad I=AXBX.$$

Since $$AX$$ and $$BX$$ are inverses, they commute, and so $$BXAX=I$$ too. Evaluating at $$c$$, we get 3 equations, $$Xc=c, \quad X(Bc)=A^Tc, \quad X(Ac)=B^Tc.$$ Assuming that $$c, Ac, Bc$$ span your space (which happens in $$\mathbb R^3$$ for most $$(A,B,c)$$-triples), this specifies a unique candidate $$X$$ to test to see if it actually satisfies the problem.

Explicitly, if $$P$$ is the matrix whose columns are $$c,Ac, Bc$$ respectively, and $$Q$$ is the matrix whose columns are $$c, B^Tc, A^Tc$$ respectively, then $$X=QP^{-1}$$. We just need to check that $$XX^T=I$$ and $$AXBX=I$$. or see that these equations are violated.

You can solve the $$n=2$$ case relatively easily with complex numbers:

$$a$$, $$b$$ and $$c$$ can be represented by complex numbers and the rotation matrix by a complex number z with modulus 1.

So the equations are:

$$za+z^{-1}b=c$$ with $$|z|=1$$.

The equation is equivalent to $$az^2-cz+b=0$$

which you can solve immediately using the quadratic formula:

$$z=\frac{c\pm\sqrt{c^2-4ab}}{2a}.$$

Clearly we only have solution to the problem if $$|\frac{c+\sqrt{c^2-4ab}}{2a}|=1$$ or $$|\frac{c-\sqrt{c^2-4ab}}{2a}|=1.$$

We can analyse further to obtain simpler conditions for a solution to exist by taking the modulus which gives $$(za+b/z)(\bar{a}/z+\bar{b}z)=|c|^2$$ or $$2\Re(\bar{a}b/z^2)=|c|^2-|a|^2-|b|^2$$. The inequality $$|\Re(z)|\leq|z|$$ implies $$||c|^2-|a|^2-|b|^2|\leq 2|a||b|$$ which is equivalent to the triangle inequality holding for $$|a|$$, $$|b|$$ and $$|c|$$ which as Michael Renardy noted is obvious geometrically and is clearly a necessary condition for a solution to exist. However it is also a sufficient condition.

In fact if $$\bar{a}b=re^{\mu}$$ and we set $$z=e^{i\theta}$$ the equation reduces to $$2\Re(re^{\mu-2\theta})=|c|^2-|a|^2-|b|^2$$ or $$2r\cos(\mu-2\theta)=|c|^2-|a|^2-|b|^2.$$ or $$\cos(\mu-2\theta)=(|c|^2-|a|^2-|b|^2)/(2|a||b|).$$ and hence if the triangle inequality condition is satisfied we have $$|\cos(\mu-2\theta)|\leq 1$$ which gives us a solution for $$\theta \in \mathbb{R}$$ and hence the rotation $$z=e^{i\theta}$$.