Multiplicative equations over commuting matrices
László Babai, Robert Beals, Jin‐Yi Cai, Gábor Ivanyos, Eugene M. Luks · 1996
We consider the solvability of the equation k Y i=1 A i x i = 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 decomposit...