Timeline for rank of an integer valued matrix
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13 at 2:18 | comment | added | Daniel Weber | Does this answer your question? Complexity of computing matrix rank over integers | |
| May 12 at 23:29 | comment | added | J. van Dobben de Bruyn | The reason why I asked if you are specifically looking for numerical algorithms is that this site focuses on theory, and it is a perfectly legitimate question to ask whether or not exact rank computations for integer matrices can be achieved using numerical computations (instead of using symbolic / arbitrary-precision arithmetic). However, it seems that the question is asking for any kind of algorithm, not necessarily a numerical one (if that distinction can even be made). So the answers to the linked question also apply. | |
| May 12 at 23:09 | comment | added | J. van Dobben de Bruyn | By "symbolic", I just mean that the computations are exact (see symbolic algebra system). These systems allow you to do exact linear algebra over various rings, including $\mathbb Z$ and $\mathbb Q$. The intermediate results will be stored in arbitrary precision integers or fractions, instead of being rounded to floating point. Instead of worrying about numerical stability, you now have to worry about the entries becoming too large, negatively impacting the space and time complexity. These issues are addressed in the question I linked. | |
| May 12 at 15:24 | comment | added | Dmitri Scheglov | @J.vanDobbendeBruyn, yes, I have particular numbers, not symbolic calculations | |
| May 12 at 6:16 | review | Close votes | |||
| May 16 at 20:14 | |||||
| May 12 at 6:00 | comment | added | J. van Dobben de Bruyn | Possible duplicate of this question. Also, since you mention that you're using NumPy, you might want to look into using SymPy or SageMath, which offer symbolic (instead of numerical) linear algebra. Or are you specifically asking about numerical algorithms? | |
| May 11 at 22:17 | history | became hot network question | |||
| May 11 at 14:57 | vote | accept | Dmitri Scheglov | ||
| May 11 at 14:41 | answer | added | Daniel Weber | timeline score: 7 | |
| May 11 at 14:21 | comment | added | Dmitri Scheglov | can you elaborate a bit, please? | |
| May 11 at 14:18 | comment | added | Daniel Weber | I believe you can compute the rank modulo a random, fairly small, prime, or even try a few different ones | |
| May 11 at 14:15 | history | asked | Dmitri Scheglov | CC BY-SA 4.0 |