DIMACS TR: 95-32

Multiplicative equations over commuting matrices

Authors: L. Babai, R. Beals, J-y. Cai, G. Ivanyos, E.M. Luks


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