Ask Your Question

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 !

edit retag close merge delete

1 answer

Sort by ยป oldest newest most voted

Groebner 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:

more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Stats

Asked: 2017-04-03 17:21:15 -0500

Seen: 534 times

Last updated: Apr 04 '17