Abstract

We consider the problem of computing a grevlex Gröbner basis for the set $F_r(M)$ of minors of size $r$ of an $n\times n$ matrix $M$ of generic linear forms over a field of characteristic zero or large enough. Such sets are not regular sequences; in fact, the ideal $\langle F_r(M) \rangle$ cannot be generated by a regular sequence. As such, when using the general-purpose algorithm $F_5$ to find the sought Gröbner basis, some computing time is wasted on reductions to zero. We use known results about the first syzygy module of $F_r(M)$ to refine the $F_5$ algorithm in order to detect more reductions to zero. In practice, our approach avoids a significant number of reductions to zero. In particular, in the case $r=n-2$, we prove that our new algorithm avoids all reductions to zero, and we provide a corresponding complexity analysis which improves upon the previously known estimates.

Citation
@inproceedings{gopalakrishnan2023refined,
  author = {Gopalakrishnan, Sriram and Neiger, Vincent and Safey El Din, Mohab},
  title = {Refined F5 Algorithms for Ideals of Minors of Square Matrices},
  year = {2023},
  isbn = {9798400700392},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3597066.3597077},
  doi = {10.1145/3597066.3597077},
  booktitle = {Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation},
  pages = {270–279},
  numpages = {10},
  keywords = {Multivariate cryptography, Real algebraic geometry., Polynomial system solving, Determinantal ideals, Gr\"{o}bner basis},
  location = {Troms\o{}, Norway},
  series = {ISSAC '23}
}