TY - GEN

T1 - Multiplicative equations over commuting matrices

AU - Babai, László

AU - Beals, Robert

AU - Cai, Jin Yi

AU - Ivanyos, Gábor

AU - Luks, Eugene M.

PY - 1996/1/28

Y1 - 1996/1/28

N2 - We consider the solvability of the equation (Equation presented) and generalizations, where the Ai and B are given commuting matrices over an algebraic number field F. In the semigroup membership problem, the variables xi 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 xi 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 special case of 1 × 1 matrices was recently solved by Guoqiang Ge; we heavily rely on his results.

AB - We consider the solvability of the equation (Equation presented) and generalizations, where the Ai and B are given commuting matrices over an algebraic number field F. In the semigroup membership problem, the variables xi 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 xi 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 special case of 1 × 1 matrices was recently solved by Guoqiang Ge; we heavily rely on his results.

UR - http://www.scopus.com/inward/record.url?scp=84906731094&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906731094&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84906731094

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 498

EP - 507

BT - Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996

PB - Association for Computing Machinery

T2 - 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996

Y2 - 28 January 1996 through 30 January 1996

ER -