DIMACS TR: 95-32
Multiplicative equations over commuting matrices
Authors: L. Babai, R. Beals, J-y. Cai, G. Ivanyos, E.M. Luks
ABSTRACT
We consider the solvability of the equation A_1^x_1 * ... * X_k^x_k = B
and generalizations, where the A_i and B are given commuting
matrices over an algebraic number field F. In the semigroup
membership problem, the variables x_i are constrained to be
nonnegative integers. While this problem is NP-complete for
variable k, we give a polynomial time algorithm if k is fixed.
In the group membership problem, the matrices are assumed to
be invertible, and the variables x_i may take on negative values.
In this case we give a polynomial time algorithm for variable
k and give an explicit description of the set of all solutions
(as an affine lattice).
The results generalize recent work of Cai, Lipton, and
Zalcstein [CLZ] where the case k=2 is solved using Jordan
Normal Forms (JNF). We achieve greater clarity simplicity,
and generality by eliminating the use of JNF's and referring
to elementary concepts of the structure theory of algebras
instead (notably, the radical and the local decomposition.
Partial solutions are combined using algorithms for (affine
lattices. The special case of 1*1 matrices was recently solved
by G. Ge and we heavily rely on his results.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-32.ps.gz
DIMACS Home Page