Ideals of spaces of degenerate matrices (Q2144235)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Ideals of spaces of degenerate matrices
scientific article

    Statements

    Ideals of spaces of degenerate matrices (English)
    0 references
    0 references
    0 references
    1 June 2022
    0 references
    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)\).
    0 references
    multilinear algebra
    0 references
    tensor calculus
    0 references
    computational aspects of algebraic
    0 references
    algebraic geometry
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references