Factorization of permutations on a triple Cartesian product of a set

Question

Let $X$ be a finite set, let's say the numbers from 1 to $N$. We consider permutations on $X^3$, which we can also regard as a bijective map $U: X^3\to X^3$. We say that $U$ is factorizable if there exist bijective maps $A,B,C$, all of them $X^2\to X^2$, such that $$U_{123}=C_{23}B_{13}A_{12}$$ Here the notation is such that $U$ acts on the triple product, and 1, 2, 3 stand for the components, and for example $A_{12}$ acts on the first two components only, whereas it leaves the third component invariant. It is clear that not every U is factorizable, because the number of possibilities for $U$ is $(N^3)!$, whereas the number of factorizable maps is limited by $((N^2)!)^3$, which is smaller.

Questions: Are there easy conditions to check, if I want to find out whether $U$ is factorizable? What would be a good algorithm for factorization? Brute force check works of course (we can check all possibilities for $A, B, C$ and see whether their product reproduces $U$), but this is not efficient if $N$ starts to increase.

Motivation: The question comes from physics, this is some simple model for more complicated interactions. We would have three particles on a line, each of them having an internal label with $N$ possibilities. When particles get exchanged, the labels can change, but only for those particles who meet at the same spot. In this interpretation, a factorized permutation corresponds to factorized scattering of particles in a process, where the leftmost and rightmost particles get exchanged, while the middle one stays in place. Factorizability means that there is no true three-particle interaction in the system, just two-particle scattering.

Remark: This question was first posted to math.stackexchange, but there was no reply in a few weeks.

Answer 1

I claim that one can (at least usually) compute a factorization of $U$ as $C_{2,3}B_{1,3}A_{1,2}$ in a reasonable amount of time as long as a factorization exists. My sort of algorithm for factorizing $U$ may be far from the most efficient algorithm for factorizing $U$, but the idea behind my algorithm is quite simple and applies to a vast collection of problems.

If $Z$ is a finite set, then define the Hamming distance metric $d$ on the symmetric group $S_Z$ by letting $d(f,g)=|\{x\in X:f(x)\neq g(x)\}|$.

Given a bijection $U:X^3\rightarrow X^3$, define a loss function $L_U:(S_{X^2})^3\rightarrow\mathbb{Z}$ by letting $L_U(A,B,C)=d(U,C_{2,3}B_{1,3}A_{1,2})$ where $d$ denotes the Hamming distance between two permutations.

One can then use evolutionary computation to find $A,B,C$ such that the loss $L_U(A,B,C)$ is minimized, and once we get $L_U(A,B,C)=0$, we have $U=C_{2,3}B_{1,3}A_{1,2}$.

A reasonable choice of a mutation operator in this evolutionary computation will be to first select a permutation $D$ from the three permutations $A,B,C$ and then replace $D$ with $D\cdot(a,b)$ where $a,b$ are selected uniformly at random from the collection of all pairs $a,b\in X$ such that $a\neq b$ (i.e. we differ $D$ by a transposition).