ECCC-Report TR19-114https://eccc.weizmann.ac.il/report/2019/114Comments and Revisions published for TR19-114en-usSun, 08 Sep 2019 09:43:31 +0300
Paper TR19-114
| Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties) |
Visu Makam,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2019/114The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: ${\rm SING}_{n,m}$, consisting of all $m$-tuples of $n\times n$ complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in ${\rm 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: ${\rm 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 ${\rm SING}_{n,m}$.
To prove this result we identify precisely the group of symmetries of ${\rm 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.Sun, 08 Sep 2019 09:43:31 +0300https://eccc.weizmann.ac.il/report/2019/114