Given matrices $A,B,C,D\in\Bbb K^{n\times n}$ where $\Bbb K$ is a ring is there an efficient technique to compute set $O$ with $OO'=I$ where $'$ is transpose and $\mathsf{Det}(O)=\pm1$ such that $$A=OCO'$$ $$B=ODO'$$ holds?
2 Answers
$\begingroup$
$\endgroup$
5
Here is one approach, which may efficiently show lack of solution in some cases.
Make square matrix $O$ with entries variables. We have $O'=O^{-1}$ and $O'$ is the transpose.
Mulitply by $O'$. Since $OO'=I$ we get:
$O'A=CO',O'B=DO'$.
This is systems of $2n^2$ linear equations over $K$ in $n^2$ variables.
If the linear system doesn't have solution, there is no solution to the problem.
In addition we need the constraint $\det(O)=\pm 1$, which might be intractable to compute symbolically.
If the linear system doesn't have solution, there is no solution.
If $K$ is a field, find basis for the solutions and try to substitute in the nonlinear constraint, searching for solution in it.
-
$\begingroup$ how do you know 'efficiently solvable'? I have $n^2/2$ variable at a minimum and also are you claiming O is unique? $\endgroup$– user76479Commented Jan 1, 2016 at 9:41
-
$\begingroup$ @Arul Yes, you have exactly n^2 variables, but the system is linear. If $K$ is a field, just compute basis of the big linear system. It might have infinitely many solutions. Ask about complexity of solving linear equations if you doubt "efficiently". $\endgroup$– joroCommented Jan 1, 2016 at 9:49
-
$\begingroup$ it seems to me that you are implying there are always infinite solutions $\endgroup$– user76479Commented Jan 1, 2016 at 9:58
-
$\begingroup$ @Arul I didn't wrote this. Search the web for solutions of linear equations. There might no solution. $\endgroup$– joroCommented Jan 1, 2016 at 10:01
-
$\begingroup$ @Arul So far my answer is wrong. I need additional nonlinear constraint $det(O)=\pm$. If the linear system doesn't have solution, it is not needed. $\endgroup$– joroCommented Jan 1, 2016 at 10:25
$\begingroup$
$\endgroup$
This question is very poorly stated. Where are the necessary conditions linking the matrices $A,B,C,D$ ? We assume that $K$ is a commutative ring with unity.
$OO^T=I$ implies that $\det(O)^2=1$ and $\det(O)$ is a unit, that implies that $O^T=O^{-1}$, $O^TO=I$ and $AB=OCDO^T$. Now $A=OCO^T$ over $\mathbb{C}$ means that $A,C$ are orthogonally similar, that is the object of the Specht theorem. Here the necessary part of this theorem is valid and can be written: $tr(W(A,A^T))=tr(W(C,C^T))$ for any word $W$ in two non-commuting variables. Similar relations link $(B,D)$, $(AB,CD)$ and also $(BA,DC)$. Moreover $A,C$ (resp. $B,D$) have same characteristic polynomial and, in particular, same determinant.
It remains to add the $2n^2$ joro's equations. Roll up your Sleeves.
