1
$\begingroup$

I am stuck with the following matrix equation:

Solve for $X$:

$$X=AXA^{T}$$

where $A$, $X$ are $3\times 3$ (real) matrices and $X$ is symmetric (i.e. $X=X^{T}$).

The sketch for the solution is to rewrite the above equations as:

$$By=0$$

where $B$ should be a $6\times 6$ matrix and $y$ should be a 6-vector. Then the solution is obvious. But how to rewrite the above equation without spending lots of paper?

I know the equation can be written in the form:

$$A^{-1}X=XA^{T}$$

and be solved as Discrete Lyapunov Equation or a Sylvester Equation in general, but since both sides contain $A$ and no addition of extra element, the solution may be simpler. Furthermore, I expect the matrix $X$ to be in a particularly simple form (symmetric or even diagonal matrix).

Thanks in advance for any hints!

  • 0
    I take it you're looking for a symmetric $X$? There may also be antisymmetric solutions.2012-04-04
  • 0
    Yes, the $X$ should be symmetric. I forgot to mention that.2012-04-04
  • 0
    You see how to obtain the form $By=0$ correct? I don't immediately see a way that doesn't involve actually multiplying out $AXA^T$ (which would be the "spending lots of paper" part, I presume).2012-04-04
  • 0
    I am trying to get $By=0$ from the product by hand, but since the problem yields such linear system, I suggest there should be some straightforward analytical/numerical solution to obtain $X$.2012-04-04
  • 0
    Here's a special case with path leads to *nothing*. But I want to write it down anyways. Let $v$ be an eigenvector of $A^{T}$ with eigenvalue $\lambda = \pm 1.$ Let $u = Xv.$ Note in this very special case $\lambda$ is also an eigenvalue of $A^{-1},$ with an eigenvector $u.$ Multiply $A^{-1}X = XA^{T}$ by $v,$ to get $A^{-1}Xv = X\lambda v.$ It is easy to see that $Xv = u,$ where both $u$ and $v$ are known. Not interesting system to solve though..2012-04-04
  • 0
    I think that you need to specify $A$ (or properties of it) if you expect to find solutions in a more or less explicit way: because otherwise you can have, say, $A=I$, and then any $X$ is a solution.2012-04-04
  • 0
    Also, $X=0$ is always a solution.2012-04-04
  • 0
    copprer.hat - yes, but there is nonzero (nontrivial) solution as well2012-04-04
  • 0
    Martin: The problem arises in calibration of a rotating camera. Here $H$ is a common linear transform between images in a projective space. The only thing I know is that $H = KRK^{-1}$ where $K$ is the upper-triangular calibration matrix and $R$ is the rotation matrix. But I don't know $R$ and to solve for $K$ without knowing $R$ leads to the above equation.2012-04-04
  • 0
    This is an interesting problem. I recommend you to read the paper "a flexible new technique for camera calibration" by zhang zhengyou. Look at eq. (6). B is a 3 by 3 symmetric matrix, and b is the associated 6D vector. Although this paper is for camera calibration, I think the technique is transferable. Just an idea and a suggestion2012-04-05
  • 0
    Thanks Shiyu - I actually need the solution for camera calibration. I currently let $X$ to be in a very simple form $X=diag(f,f,1)$ where $f$ corresponds to focal length. Multiplying right hand side of the above equation and equating components of left and right matrices leads to a simple least squares problem. The results are precise enough, but it would be nice to allow for more complex calibration matrix $X$ in future (the off-diagonal elements allow to grasp aspect ratio, skew and principal point of the camera)...2012-04-06

1 Answers 1

1

Don't use paper, use silicon. The matrix $B$ (for the basis $x_{1,1},x_{1,2},x_{1,3},x_{2,2},x_{2,3},x_{3,3}$) is $$\pmatrix{ 1-{a_{{1,1}}}^{2}&-2\,a_{{1,2}}a_{{1,1} }&-2\,a_{{1,3}}a_{{1,1}}&-{a_{{1,2}}}^{2}&-2\,a_{{1,3}}a_{{1,2}}&-{a_{ {1,3}}}^{2}\\ -a_{{1,1}}a_{{2,1}}&1-a_{{1,2}}a_{{2,1 }}-a_{{1,1}}a_{{2,2}}&-a_{{1,3}}a_{{2,1}}-a_{{1,1}}a_{{2,3}}&-a_{{1,2} }a_{{2,2}}&-a_{{1,3}}a_{{2,2}}-a_{{1,2}}a_{{2,3}}&-a_{{1,3}}a_{{2,3}} \\ -{a_{{2,1}}}^{2}&-2\,a_{{2,2}}a_{{2,1}}&-2\,a_{{2 ,3}}a_{{2,1}}&1-{a_{{2,2}}}^{2}&-2\,a_{{2,3}}a_{{2,2}}&-{a_{{2,3}}}^{2 }\\-a_{{1,1}}a_{{3,1}}&-a_{{1,2}}a_{{3,1}}-a_{{1,1} }a_{{3,2}}&-a_{{1,3}}a_{{3,1}}+1-a_{{1,1}}a_{{3,3}}&-a_{{1,2}}a_{{3,2} }&-a_{{1,2}}a_{{3,3}}-a_{{1,3}}a_{{3,2}}&-a_{{1,3}}a_{{3,3}} \\ -a_{{2,1}}a_{{3,1}}&-a_{{2,2}}a_{{3,1}}-a_{{2,1}} a_{{3,2}}&-a_{{2,3}}a_{{3,1}}-a_{{2,1}}a_{{3,3}}&-a_{{2,2}}a_{{3,2}}&- a_{{2,3}}a_{{3,2}}+1-a_{{2,2}}a_{{3,3}}&-a_{{2,3}}a_{{3,3}} \\ -{a_{{3,1}}}^{2}&-2\,a_{{3,2}}a_{{3,1}}&-2\,a_{{3 ,3}}a_{{3,1}}&-{a_{{3,2}}}^{2}&-2\,a_{{3,3}}a_{{3,2}}&1-{a_{{3,3}}}^{2 }} $$

In order to have a nonzero solution, the determinant of $B$ must be $0$. This is a rather complicated polynomial of total degree 12, which factors over the rationals as $$ - ( a_{{2,3}}a_{{3,1}}a_{{1,2}}-a_{{1,2}}a_{{2,1}}-a_{{2,1}}a_{{1 ,2}}a_{{3,3}}+1+a_{{1,1}}+a_{{2,2}}+a_{{1,1}}a_{{2,2}}-a_{{1,3}}a_{{3, 1}}-a_{{2,2}}a_{{3,1}}a_{{1,3}}+a_{{2,1}}a_{{3,2}}a_{{1,3}}-a_{{2,3}}a _{{3,2}}-a_{{1,1}}a_{{2,3}}a_{{3,2}}+a_{{3,3}}+a_{{1,1}}a_{{3,3}}+a_{{ 2,2}}a_{{3,3}}+a_{{1,1}}a_{{2,2}}a_{{3,3}} ) ( a_{{2,3}}a_ {{3,1}}a_{{1,2}}+a_{{1,2}}a_{{2,1}}-a_{{2,1}}a_{{1,2}}a_{{3,3}}-1+a_{{ 1,1}}+a_{{2,2}}-a_{{1,1}}a_{{2,2}}+a_{{1,3}}a_{{3,1}}-a_{{2,2}}a_{{3,1 }}a_{{1,3}}+a_{{2,1}}a_{{3,2}}a_{{1,3}}+a_{{2,3}}a_{{3,2}}-a_{{1,1}}a_ {{2,3}}a_{{3,2}}+a_{{3,3}}-a_{{1,1}}a_{{3,3}}-a_{{2,2}}a_{{3,3}}+a_{{1 ,1}}a_{{2,2}}a_{{3,3}} ) ( -1-a_{{1,3}}a_{{3,1}}-2\,a_{{1, 2}}a_{{1,3}}{a_{{2,1}}}^{2}a_{{3,2}}a_{{3,3}}-2\,{a_{{1,2}}}^{2}a_{{2, 1}}a_{{2,3}}a_{{3,1}}a_{{3,3}}-2\,a_{{2,1}}{a_{{1,3}}}^{2}a_{{2,2}}a_{ {3,1}}a_{{3,2}}-2\,a_{{1,1}}a_{{1,2}}{a_{{2,3}}}^{2}a_{{3,1}}a_{{3,2}} -2\,a_{{1,1}}a_{{1,3}}a_{{2,1}}a_{{2,3}}{a_{{3,2}}}^{2}-2\,a_{{1,2}}a_ {{1,3}}a_{{2,2}}a_{{2,3}}{a_{{3,1}}}^{2}-a_{{1,1}}a_{{1,3}}a_{{2,1}}a_ {{3,2}}+a_{{1,1}}a_{{1,3}}a_{{2,2}}a_{{3,1}}+a_{{2,3}}a_{{2,2}}a_{{1,1 }}a_{{3,2}}+a_{{2,1}}a_{{1,2}}a_{{1,1}}a_{{3,3}}+a_{{2,2}}a_{{2,1}}a_{ {1,2}}a_{{3,3}}-a_{{2,3}}a_{{3,1}}a_{{1,2}}a_{{3,3}}+a_{{2,2}}a_{{3,1} }a_{{1,3}}a_{{3,3}}-a_{{2,1}}a_{{3,2}}a_{{1,3}}a_{{3,3}}+a_{{1,1}}a_{{ 2,3}}a_{{3,2}}a_{{3,3}}-a_{{2,1}}a_{{2,2}}a_{{3,2}}a_{{1,3}}-a_{{2,2}} a_{{2,3}}a_{{3,1}}a_{{1,2}}-a_{{1,1}}a_{{1,2}}a_{{2,3}}a_{{3,1}}+a_{{1 ,3}}{a_{{2,2}}}^{2}a_{{3,1}}+{a_{{1,1}}}^{2}a_{{2,3}}a_{{3,2}}-a_{{2,2 }}{a_{{3,3}}}^{2}a_{{1,1}}+{a_{{1,1}}}^{2}{a_{{2,2}}}^{2}{a_{{3,3}}}^{ 2}-{a_{{1,1}}}^{2}a_{{2,2}}a_{{3,3}}+{a_{{1,1}}}^{2}{a_{{2,3}}}^{2}{a_ {{3,2}}}^{2}-a_{{1,1}}{a_{{2,2}}}^{2}a_{{3,3}}+{a_{{1,2}}}^{2}{a_{{2,3 }}}^{2}{a_{{3,1}}}^{2}+{a_{{1,3}}}^{2}{a_{{2,2}}}^{2}{a_{{3,1}}}^{2}-2 \,a_{{1,1}}a_{{1,2}}a_{{2,1}}a_{{2,2}}{a_{{3,3}}}^{2}+{a_{{1,2}}}^{2}{ a_{{2,1}}}^{2}{a_{{3,3}}}^{2}+a_{{2,1}}{a_{{3,3}}}^{2}a_{{1,2}}+{a_{{1 ,3}}}^{2}{a_{{3,2}}}^{2}{a_{{2,1}}}^{2}+2\,a_{{1,2}}a_{{2,3}}a_{{3,2}} a_{{2,1}}a_{{1,1}}a_{{3,3}}-2\,{a_{{2,2}}}^{2}a_{{3,3}}a_{{1,3}}a_{{1, 1}}a_{{3,1}}+2\,a_{{2,1}}a_{{2,2}}a_{{3,3}}a_{{1,3}}a_{{1,2}}a_{{3,1}} +2\,a_{{1,3}}a_{{3,2}}a_{{2,3}}a_{{2,2}}a_{{1,1}}a_{{3,1}}+2\,a_{{1,2} }a_{{1,3}}a_{{2,1}}a_{{2,3}}a_{{3,1}}a_{{3,2}}+2\,a_{{1,1}}a_{{1,2}}a_ {{2,2}}a_{{2,3}}a_{{3,1}}a_{{3,3}}+2\,a_{{1,1}}a_{{1,3}}a_{{2,1}}a_{{2 ,2}}a_{{3,2}}a_{{3,3}}-2\,{a_{{1,1}}}^{2}a_{{2,2}}a_{{2,3}}a_{{3,2}}a_ {{3,3}}-a_{{1,2}}a_{{2,1}}+a_{{1,1}}a_{{2,2}}+a_{{1,1}}a_{{3,3}}-a_{{2 ,3}}a_{{3,2}}+a_{{2,2}}a_{{3,3}} ) $$

  • 0
    Thanks for the thorough solution. Maybe I overlooked some information about the matrices, since the final system really should be linear.2012-04-04
  • 0
    Linear in $X$, but not linear in $A$.2012-04-05
  • 0
    Oh, right. Now I know why people go so often for iterative methods when it comes to such problems...2012-04-06