Solution for $Xa + X^Tb = c$ where $X^TX = I$? [closed]

Question

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$

Answer 1

\begin{equation} Xa = \begin{bmatrix} a_1x_{1,1} + a_2x_{1,2}\\ a_1x_{2,1} + a_2x_{2,2}\\ \end{bmatrix} \end{equation} and \begin{equation} X^Tb = \begin{bmatrix} b_1x_{1,1} + b_2x_{2,1}\\ b_1x_{1,2} + b_2x_{1,2}\\ \end{bmatrix} \end{equation} and \begin{equation} 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} \end{equation} but $X$ is a rotation matrix gives us that \begin{equation} 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} \end{equation} (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 \begin{equation} 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} \end{equation} and therefore (by using the triangle inequality) you don't have a solution if for example \begin{equation} \frac{|(a_1+b_1)|}{\sqrt{2}} +\frac{|(b_2- a_2)|}{\sqrt{2}} < |c_1| \end{equation} and like wise for the second condition \begin{equation} \frac{|(a_2+b_2)|}{\sqrt{2}} +\frac{|(a_1- b_1)|}{\sqrt{2}} < |c_2| \end{equation} 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{equation} \begin{array} & ax & + & by & =& c_1\\ cx & + & dy & =& c_2 \\ x^2 & + & y^2 & =& 1 \\ \end{array} \end{equation}

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{equation} \begin{array} & ax & + & by & =& c_1 \\ cx & + & dy & =& c_2 \\ \end{array} \end{equation} 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.

Answer 2

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).

Answer 3

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}$.

Answer 4

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.

Answer 5

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.