2
$\begingroup$

Let us assume $A$,$B$ and $C$ are known affine transformation matrices in homogeneous 2D space.

If it should happen that $C=A^m B^n$ for some unknown $m,n$, is there a way to detect this short of trying all the combinations? If one of $A,B$ is an identity matrix this can be determined by examining the eigenvectors, but is there an equivalent way of doing this for a product such as this?

The use-case is that I am examining a grid-like structure generated by composing transformations as described above, and I want to know if an arbitrary transformation I get can in fact be expressed as a product of exponentiated "primitive" transformations that I already know.

$\endgroup$
  • $\begingroup$ What are we given, and what are we trying to find? Are we given $C$, $m$, and $n$? $\endgroup$ – Omnomnomnom Jun 9 '15 at 20:23
  • $\begingroup$ @Omnomnomnom edited to specify. $\endgroup$ – Mike L. Jun 9 '15 at 21:02
  • $\begingroup$ Are you investigating sort of Multigrid Methods ? Like in: DoubleGrid Calculus , TripleGrid Calculus . $\endgroup$ – Han de Bruijn Jun 15 '15 at 8:35
  • $\begingroup$ @HandeBruijn Probably not; the grid I speak of exists in the linear space and can be visualized by repeatedly transforming a single point by the $A^m B^n$ combination. $\endgroup$ – Mike L. Jun 15 '15 at 16:07
  • $\begingroup$ Aren't $A$ and $B$ simply translations then? $\endgroup$ – Han de Bruijn Jun 16 '15 at 18:59
1
+50
$\begingroup$

If $A$ and $B$ commute, you can use the matrix logarithm! Sure, it's not unique but solutions only vary by integer multiples of $2\pi i$ you can check by hand whether $\log C$ looks like $$ \log(C) = q2\pi i I + n\log(A) + m\log(A) $$

for integers $q,n,m$. Each entry in $\log(C)$ corresponds to a linear equation $q,n,m$ must solve. It's complex, but that doesn't matter. It's now a linear system.

Here's why commuting matters. In the real setting, $\log(ab) = \log(a)+\log(b)$ is always true. However, in the matrix setting addition does commute but multiplication may not. It turns out that $$ \log(AB) = \log(A)+\log(B) \quad\text{mod}\;2\pi i I $$ is only guaranteed for $A$ and $B$ which commute. So while you can do the computation described above for $A$ and $B$ which don't commute, it'll just give you garbage. The equation $C=A^nB^m$ need not have any relation with $\log(C) = q2\pi i I + n\log(A) + m\log(A)$.

Computing logarithms is not too hard numerically. Just use the Taylor series. Computing them by hand is not too bad if $A$ or $B$ is diagonalizable.

If you go the numeric route, just be sure to check that the candidate $n$ and $m$ actually work. The matrix log can be a little sensitive near the edges of it's interval of convergence.

I know that this $A$ and $B$ commuting is a fairly special case, but you gotta start somewhere. I'll keep thinking of what to do in the more general case.

$\endgroup$
  • $\begingroup$ The commutativity condition is fairly restrictive, but it does hold at least in the most common cases (translation-translation, translation/scale-translation and even if there's one rotation in the mix). What happens if they are not commutative and I try this? $\endgroup$ – Mike L. Jun 15 '15 at 16:19
  • $\begingroup$ Edited to address your question. $\endgroup$ – Zach Stone Jun 15 '15 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.