# How to decompose matrix transformations

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.

• What are we given, and what are we trying to find? Are we given $C$, $m$, and $n$? – Omnomnomnom Jun 9 '15 at 20:23
• @Omnomnomnom edited to specify. – Mike L. Jun 9 '15 at 21:02
• Are you investigating sort of Multigrid Methods ? Like in: DoubleGrid Calculus , TripleGrid Calculus . – Han de Bruijn Jun 15 '15 at 8:35
• @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. – Mike L. Jun 15 '15 at 16:07
• Aren't $A$ and $B$ simply translations then? – Han de Bruijn Jun 16 '15 at 18:59

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.

• 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? – Mike L. Jun 15 '15 at 16:19
• Edited to address your question. – Zach Stone Jun 15 '15 at 18:06