I am interested in finding a method to determine the least common multiple of a set of $M$ multinomials in a set of $N$ noncommutative variables. I am given a set of multinomials $A_1(x_1, x_2, ..., x_N)$, $A_2(x_1, x_2, ..., x_N)$, ..., $A_M(x_1, x_2, ..., x_N)$ where $$A_i(x_1, x_2, ..., x_N) = \sum_{l=0}^{L_i} \sum_{k_1+k_2+...+k_N=l} a_{i{k_1k_2...k_N}} \prod_{t=1}^{N} x_t^{k_t}$$ where $a_{i{k_1k_2...k_N}}$ is the complex coefficient of the multinomial term $x_1^{k_1}x_2^{k_2}...x_N^{k_N}$ in the $i^{th}$ multinomial and where $L_i$ is finite for each multinomial.
The noncommutative variables $x_1, x_2, ..., x_N$ obey the relationship $x_rx_s = q_{rs}x_sx_r$ for known complex coefficients $q_{rs}$ but there is no special relationship among the $q$'s.
I want to find a set of multinomials $B_1(x_1, x_2, ..., x_N)$, $B_2(x_1, x_2, ..., x_N)$, ..., $B_M(x_1, x_2, ..., x_N)$ such that $$\forall_i B_i(x_1, x_2, ..., x_N) A_i(x_1, x_2, ..., x_N) = C(x_1, x_2, ..., x_N).$$ I am interested in the "least common multiple" but am not picky about how one defines least. It could be that $C(x_1, x_2, ..., x_N)$ has the fewest non-zero terms or it could be that the maximum order of $C(x_1, x_2, ..., x_N)$ is as small as possible.
[Note - I really only care about finding, given what coefficients are non-zero in the $A$'s, what coefficients are non-zero in the $B$'s and in $C$, not the value of the coefficients.]