首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)
  • 本地全文:下载
  • 作者:Visu Makam ; Avi Wigderson
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-43
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: SING n m , consisting of all m -tuples of n n complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING n m will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation. A sequence of recent works suggests such efficient algorithms for memberships in a general class of algebraic varieties, namely the null cones of linear group actions. Can this be used for the problem above? Our main result is negative: SING n m is not the null cone of any (reductive) group action! This stands in stark contrast to a non-commutative analog of this variety, and points to an inherent structural difficulty of SING n m . To prove this result we identify precisely the group of symmetries of SING n m . We find this characterization, and the tools we introduce to prove it, of independent interest. Our work significantly generalizes a result of Frobenius for the special case m = 1 , and suggests a general method for determining the symmetries of algebraic varieties.

  • 关键词:Hilbert;Mumford criterion ; Invariant theory ; Null cone ; PIT ; symmetries of algebraic varieties
国家哲学社会科学文献中心版权所有