Ask Your Question

Groebner basis to solve linear system of equations

asked 2017-04-04 00:21:15 +0200

anonymous user


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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2017-04-04 15:47:42 +0200

tmonteil gravatar image

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:

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2017-04-04 00:21:15 +0200

Seen: 1,229 times

Last updated: Apr 04 '17