Black-box singularity testing for rational matrix pencils
Follow the latest progress by email.
Can nonsingularity of a rational-coefficient affine linear matrix pencil over the free skew field be detected by a universal nonadaptive polynomial-size list of rational matrix substitutions?
Why it matters and what counts as progress
Why it matters: A black-box evaluation list would complement deterministic white-box algorithms that inspect the pencil’s internal description.
What counts as progress: A polynomial-bit-time list construction with polynomial output size and a proof that every nonsingular pencil is detected; rectangular rank detection is an additional target.
How the problem developed
- 2015 · Theorem [1]
Hrubeš and Wigderson Connected noncommutative rational functions with matrix substitutions and developed identity testing for rational expressions; this predates polynomial-size hitting sets for general rational formulas.
- September 2023 · Hitting-set result [2]
Arvind, Chatterjee, and Mukhopadhyay Gave deterministic quasipolynomial-size hitting sets for noncommutative rational formulas at arbitrary inversion height.
- 24 Sept 2026 · Reported result [3]
OpenAI The manuscript reports polynomial-size matrix-tuple hitting lists for singularity testing of the stated noncommutative rational matrix pencils.
AI contribution
Polynomial Hitting Lists for Noncommutative Rational Formulas
For rational-coefficient affine linear matrix pencils, a universal nonadaptive polynomial-size list of rational matrix evaluations detects nonsingularity over the free skew field. The paper also gives a rank-detecting list for rectangular rational pencils, with polynomial construction and output bounds in the dimensions and variable count.
Sources
- Hrubeš and Wigderson, Non-commutative arithmetic circuits with division
- Black-box identity testing of noncommutative rational formulas in deterministic quasipolynomial time
- OpenAI rational hitting-list manuscript
- Polynomial Hitting Lists for Noncommutative Rational Formulas
- Formalization scope for rational hitting lists
- Lean proof of the parent hitting-list theorem
Website timeline
Publication dates and editorial changes.