Ideals of spaces of degenerate matrices (Q2144235)

An algebraic version of the P vs NP problem goes back to [\textit{L. G. Valiant}, ``Completeness classes in algebra'', in: Proceedings of the 11th annual ACM symposium on theory of computing, STOC'79, Atlanta, GA, USA, April 30 -- May 2, 1, 1979. New York, NY: Association for Computing Machinery (ACM). 249--261 (1979; \url{doi:10.1145/800135.804419})] in the 70's: the problem of polynomial identity testing. A special case of it is the determinant identity testing, where a polynomial is given as a determinant of a combinations of matrices via linear forms. There is no known efficient deterministic algorithm to check if such an expression is constantly 0. Finding such an algorithm would have a major impact towards resolving Valiant's analogue of the P vs NP question. Determinant identity testing is the problem to decide membership in the algebraic variety Sing\(_{n,m}\), i.e., given a matrix tuple \(A = (A_1, \dots, A_m)\), determine whether all linear combinations of the \(A_i\) are singular. \textit{V. Makam} and \textit{A. Wigderson} [``Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties''; in: Proceedings of the 61tst annual IEEE symposium on foundations of computer science, FOCS'20, virtual conference, November 16--19, 2020. Los Alamitos, CA: IEEE Computer Society. 881--888 (2020; \url{doi:10.1109/FOCS46700.2020.00086})] asked whether the ideal generated by these equations is always radical. The present paper answers negatively to that question: the authors determine the vanishing ideal of Sing\(_{2,m}\) for all \(m \in \mathbb{N}\). Then they show that there are additional equations arising from the tensor structure. More generally, for any \(n\) and \(m \geq n^2 -n + 1\), they prove there are equations vanishing on Sing\(_{n,m}\) that are not in the ideal generated by polynomials of type \(\det(\lambda_1 +X_1 + \cdots + \lambda_m X_m)\).