ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 04 Apr 2017 15:47:42 +0200Groebner basis to solve linear system of equationshttps://ask.sagemath.org/question/37156/groebner-basis-to-solve-linear-system-of-equations/ I am trying to solve a linear system of equation modulo some prime $p$. I have a matrix which gives me the coefficients of the polynomials (i.e., first row would be ($a, c, b, d$) for $ax+by+cz+d =0$). I would usually use solve_right(), writing my system as $Ax=b$ mod $p$, but I am intrigued by the use of Groebner basis. I have read about their implementation but I am confused at the notion of ideal to define before solving the system. I would like to solve the system in the ring $Z/pZ$. Also, can I feed a matrix to the function or should I first convert the matrix in a bunch of equations ?
Any clarification would be welcome !Tue, 04 Apr 2017 00:21:15 +0200https://ask.sagemath.org/question/37156/groebner-basis-to-solve-linear-system-of-equations/Answer by tmonteil for <p>I am trying to solve a linear system of equation modulo some prime $p$. I have a matrix which gives me the coefficients of the polynomials (i.e., first row would be ($a, c, b, d$) for $ax+by+cz+d =0$). I would usually use solve_right(), writing my system as $Ax=b$ mod $p$, but I am intrigued by the use of Groebner basis. I have read about their implementation but I am confused at the notion of ideal to define before solving the system. I would like to solve the system in the ring $Z/pZ$. Also, can I feed a matrix to the function or should I first convert the matrix in a bunch of equations ?
Any clarification would be welcome !</p>
https://ask.sagemath.org/question/37156/groebner-basis-to-solve-linear-system-of-equations/?answer=37167#post-id-37167Groebner bases are somehow overkill: they are used for polynomial systems (involving equations like $ax^3y^4+by^5z+cxz+d=0$).
Here your system is linear, so linear algebra (matrix computations) is definitely the appropriate tool. It is much faster, can handle larger system, etc.
If you want to work modulo some prime p, you should define your matrices over the finite field ``GF(p)``:
sage: matrix(GF(5), [[1, 2, 4, 2], [2, 4, 4, 0], [0, 4, 4, 1], [2, 0, 0, 2]])
If you really want to use ideals, you can easily define your polynomials over ``GF(p)``, here is an example:
sage: R.<x,y,z> = PolynomialRing(GF(5)) ; R
Multivariate Polynomial Ring in x, y, z over Finite Field of size 5
sage: P = 2*x+3*y+5*z+2
sage: Q = 2*x+y+5*z+2
sage: S = x+y+z
sage: I = R.ideal([P,Q,S]) ; I
Ideal (2*x - 2*y + 2, 2*x + y + 2, x + y + z) of Multivariate Polynomial Ring in x, y, z over Finite Field of size 5
sage: I.variety()
[{y: 0, z: 1, x: 4}]
Note that when the variety is not zero dimensional, you might encounter issues.
sage: I = R.ideal([P,Q])
sage: I.variety()
ValueError: The dimension of the ideal is 1, but it should be 0
In linear words, this case corresponds to to having a non-trivial kernel, a case that is very well handled with matrices, see the following list of examples:
- https://ask.sagemath.org/question/37042/how-to-find-solution-to-the-following-matrix/
- https://ask.sagemath.org/question/36948/how-to-simplify-solve-result-r_i-variables/
- https://ask.sagemath.org/question/35227/basic-question-about-annihilator/
- https://ask.sagemath.org/question/31009/linear-equations-with-infinite-solutions/
- https://ask.sagemath.org/question/31163/enumerate-all-solutions-to-linear-system-over-finite-field/
- https://ask.sagemath.org/question/32145/solving-system-of-linear-equations-over-gf2/
- https://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/
Tue, 04 Apr 2017 15:47:42 +0200https://ask.sagemath.org/question/37156/groebner-basis-to-solve-linear-system-of-equations/?answer=37167#post-id-37167