A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) invariant theory and representationtheory, linear algebra, optimization, linear system theory, quantum information theory, and naturally in non-commutativealgebra.

Authors

• Ankit Garg 0001
• Leonid Gurvits
• Rafael Oliveira 0002
• Avi Wigderson

Keywords

• Testing
• Algorithm design and analysis
• Complexity theory
• Optimization
• Electronic mail
• Quantum mechanics
• Algebra
• Identification Test
• Polynomial-time Algorithm
• Deterministic Time
• Rationality Test
• Deterministic Polynomial-time Algorithm
• Lower Bound
• Running Time
• Invertible
• Rank Of Matrix
• Linear Algebra
• Exponential Time
• Quantum Operations
• Invariant Theory
• Word Problems
• Quantum Information Theory
• Linear System Theory
• Upper Bound
• Function Of Variables
• Diagonal Matrix
• Positive Matrix
• Commutative Algebra
• Rational Function
• Completely Positive
• Upper Triangular
• Left-invariant
• Matrix Integrity
• Transition Probability Matrix
• Tensor Product
• Arithmetic Operations
• Positive Diagonal Matrix
• Non-commutative computation
• Rational identity