Deterministic polynomial-time commutative Edmonds problem
The input is $n, s \ge 1$ and matrices $A_1, \dots, A_s \in \mathbb{Q}^{n \times n}$, each entry written as a fraction with a signed binary numerator and a positive binary denominator. Substituting random values for the indeterminates below decides the question in randomised polynomial time, by the Schwartz–Zippel lemma, and Kabanets and Impagliazzo showed that a deterministic polynomial-time algorithm would imply $\mathrm{NEXP} \not\subseteq \mathrm{P/poly}$ or that the permanent of integer matrices has no polynomial-size division-free arithmetic formulas. Ivanyos, Karpinski, Qiao and Santha give deterministic polynomial-time algorithms over $\mathbb{Q}$ when the space spanned by $A_1, \dots, A_s$ has a basis of rank-one matrices or can be brought to upper triangular form by one change of row and column bases, in either case possibly over an extension field. For non-commuting indeterminates, Garg, Gurvits, Oliveira and Wigderson test in deterministic polynomial time whether $x_1A_1 + \dots + x_sA_s$ is invertible over the free skew field.
Problem. Is there a deterministic algorithm that, given such $A_1, \dots, A_s$, decides whether $$\det(x_1A_1 + \dots + x_sA_s)$$ is the zero polynomial in commuting indeterminates $x_1, \dots, x_s$ over $\mathbb{Q}$, equivalently whether the space $\{c_1A_1 + \dots + c_sA_s : c_1, \dots, c_s \in \mathbb{Q}\}$ contains no nonsingular matrix, using a number of bit operations bounded by a polynomial in the length of the input?
Source: Edmonds (1967), §7; in this form (nonsingularity over ℚ, bit complexity), OpenProblemsInNLA, after Ivanyos, Karpinski, Qiao and Santha (2015).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CO
- Keywords
- derandomization, OpenProblemsInNLA, polynomial identity testing, symbolic determinants
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{edmonds1967,
author = {Edmonds, Jack},
title = {Systems of distinct representatives and linear algebra},
journal = {J. Res. Nat. Bur. Standards Sect. B},
volume = {71B},
number = {4},
year = {1967},
pages = {241--245},
doi = {10.6028/jres.071B.033},
}
@article{ivanyos2015,
author = {Ivanyos, G{\'a}bor and Karpinski, Marek and Qiao, Youming and Santha, Miklos},
title = {Generalized {W}ong sequences and their applications to {E}dmonds' problems},
journal = {J. Comput. System Sci.},
volume = {81},
number = {7},
year = {2015},
pages = {1373--1386},
doi = {10.1016/j.jcss.2015.04.006},
eprint = {1307.6429},
archivePrefix = {arXiv},
}
@article{kabanets2004,
author = {Kabanets, Valentine and Impagliazzo, Russell},
title = {Derandomizing polynomial identity tests means proving circuit lower bounds},
journal = {Comput. Complexity},
volume = {13},
number = {1-2},
year = {2004},
pages = {1--46},
doi = {10.1007/s00037-004-0182-6},
}
@article{garg2020,
author = {Garg, Ankit and Gurvits, Leonid and Oliveira, Rafael and Wigderson, Avi},
title = {Operator scaling: theory and applications},
journal = {Found. Comput. Math.},
volume = {20},
number = {2},
year = {2020},
pages = {223--290},
doi = {10.1007/s10208-019-09417-z},
eprint = {1511.03730},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ac09,
author = {Townsend, Alex},
title = {{AC-09}: Deterministic polynomial-time commutative Edmonds problem},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-09/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00184, "Deterministic polynomial-time commutative Edmonds problem", clopen.solutions.