5
$\begingroup$

I have a matrix, $M$, size of approximately $20\times 25$, over a polynomial ring $\mathbb{Q}[x_1, \cdots, x_n]$ and a number $r$ such that I would like to test whether or not there exist values for the $x_i$ such that the $\text{rank }M\leq r$.

The most natural approach to me is to take the $r+1 \times r+1$ minors and consider the ideal that these minors generate. However, the issue is that if I wish to test rank $r = 6$, for example, the sheer number of minors and the following Groebner basis calculation take an exceedingly long time to compute (on the order of weeks in some cases). I am currently using SageMath software to do these computations.

I should state that I have already leveraged putting the matrix in a partial Smith normal form and the sparsity of matrix, when possible.

Are there any other algorithms I could employ in addition to (or in lieu of) the above strategy?

Improve this question
$\endgroup$
5
  • $\begingroup$ Rather than using all minors of a fixed size, often choosing a few randomly chosen ones is enough. If you get the empty scheme, then you are done. Otherwise, you might be able to find points which have a chance of having small rank... $\endgroup$
    – damiano
    Mar 7, 2020 at 6:42
  • $\begingroup$ How would you define "few". Do you have any reference for theorems that precisely state and prove your assertion that only choosing a few randomly is enough? I do not see any reason why often it would suffice to only choose random ones. I have not imposed any genericity conditions on the matrix whatsoever $\endgroup$
    – bark
    Mar 7, 2020 at 7:54
  • $\begingroup$ I took @damiano's comment to be giving a one-sided test. That is, the assertion seems to be only that often a random selection of minors can show you that the rank cannot be made less than $r$. $\endgroup$
    – Louis Deaett
    Mar 8, 2020 at 3:10
  • $\begingroup$ @LouisDeaett Thank you for the clarification. I am still unsure as to why this is "often" the case, unless I impose the condition that the matrix is generic $\endgroup$
    – bark
    Mar 8, 2020 at 4:09
  • 1
    $\begingroup$ Indeed, as @LouisDeaett says, I only meant it as a one-sided test. Still, you can squeeze out a little bit more, if you do have solutions satisfying the few minors you tested. Such solutions correspond to matrices with some minors forced to be zero. If you are lucky (which has often been the case in my experience), then you may find that the matrices actually have small rank. $\endgroup$
    – damiano
    Mar 9, 2020 at 9:11

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.