Grobner basis

Grobner basis

groebner_basis

Nilesh
31 ●3 ●4 ●7

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

Dear Sir, I had again done sage computations for finding a Groebner basis of an ideal in polynomial ring in 35 variables with coefficients from finite field with 2 elements. I am not getting the output of Parity check matrix.Also, as soon as I enter a command I.groebner_basis() No output is coming. Why this is so? What to do , to get an output?

G=matrix(FiniteField(2),[[1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0,1,1,1,1,1],
                         [0,1,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,1,0,1,0,1,1,1,0,1,1,1],
                         [0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,1,1,1,0,1],
                         [0,0,0,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,1,0,0,1,1,0,1,1,0,1,0,1,1,1,1],
                         [0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1],
                         [0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,0,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,0]])
C=LinearCode(G)
C
Output: Linear code of length 35, dimension 6 over Finite Field of size 2
H=C.check_mat()
Output:  No output is coming
ToricIdeal(H)
Output:     
Ideal (-z0*z1*z2*z3*z4*z13*z14*z16*z17*z18*z19*z22*z23*z27*z28 + z34,
-z0*z1*z3*z4*z5*z7*z8*z15*z16*z18*z20*z23*z24*z26*z27 + z33,
-z0*z1*z2*z3*z5*z10*z11*z15*z17*z18*z21*z22*z24*z26*z28 + z32,
-z0*z2*z3*z4*z5*z6*z8*z12*z13*z19*z20*z23*z25*z26*z28 + z31,
-z0*z1*z2*z4*z5*z9*z11*z12*z14*z19*z21*z22*z25*z26*z27 + z30,
-z1*z2*z3*z4*z5*z6*z7*z9*z10*z20*z21*z24*z25*z27*z28 + z29) of
Multivariate Polynomial Ring in z0, z1, z2, z3, z4, z5, z6, z7, z8, z9,
z10, z11, z12, z13, z14, z15, z16, z17, z18, z19, z20, z21, z22, z23,
z24, z25, z26, z27, z28, z29, z30, z31, z32, z33, z34 over Rational
Field

P.<z0, z1, z2, z3, z4, z5, z6,z7,z8,z9,z10,z11,z12,z13,z14,z15,z16,z17,z18,z19,z20,z21,z22,z23,z24,z25,z26,z27,z28,z29,z30,z31,z32,z33,z34>=PolynomialRing(FiniteField(3),order='lex')
I=Ideal([-z0*z1*z2*z3*z4*z13*z14*z16*z17*z18*z19*z22*z23*z27*z28
 + z34, -z0*z1*z3*z4*z5*z7*z8*z15*z16*z18*z20*z23*z24*z26*z27 + z33,
-z0*z1*z2*z3*z5*z10*z11*z15*z17*z18*z21*z22*z24*z26*z28 + z32,
-z0*z2*z3*z4*z5*z6*z8*z12*z13*z19*z20*z23*z25*z26*z28 + z31,
-z0*z1*z2*z4*z5*z9*z11*z12*z14*z19*z21*z22*z25*z26*z27 + z30,
-z1*z2*z3*z4*z5*z6*z7*z9*z10*z20*z21*z24*z25*z27*z28 + 
z29,z0^3-1,z1^3-1,z2^3-1,z3^3-1,z4^3-1,z5^3-1,z6^3-1,z7^3-1,z8^3-1,z9^3-1,z10^3-1,z11^3-1,z12^3-1,z13^3-1,z14^3-1,z15^3-1,z16^3-1,z17^3-1,z18^3-1,z19^3-1,z20^3-1,z21^3-1,z22^3-1,z23^3-1,z24^3-1,z25^3-1,z26^3-1,z27^3-1,z28^3-1,z29^3-1,z30^3-1,z31^3-1,z32^3-1,z33^3-1,z34^3-1])
I.groebner_basis()
Output: No output is coming.

Comments

I do not have a check_mat method for C, which version of Sage are you using ?

tmonteil ( 8 years ago )

@Nilesh -- what is the output of version()?

slelievre ( 8 years ago )

What do you mean with Output: No output is coming, is it running, i.e. takes too long to compute the Groebner basis?

asante ( 8 years ago )

add a comment

answered 7 years ago

dan_fulea
5650 ●5 ●44 ●97

updated 7 years ago

Let us make the output come:

G = matrix(
    GF(2),
    [ [1,0,0,0,0,0, 1,1,0,1,1,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0,1,1,1,1,1],
      [0,1,0,0,0,0, 1,0,1,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,1,0,1,0,1,1,1,0,1,1,1],
      [0,0,1,0,0,0, 0,1,1,0,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,1,1,1,0,1],
      [0,0,0,1,0,0, 0,0,0,1,0,1,1,0,1,0,0,0,1,0,1,0,0,1,1,0,1,1,0,1,0,1,1,1,1],
      [0,0,0,0,1,0, 0,0,0,0,1,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1],
      [0,0,0,0,0,1, 0,0,0,0,0,0,0,1,1,0,1,1,0,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,0]] )

C = LinearCode(G)
H = C.parity_check_matrix()

print "H = %s" % H
print "The parity check matrix H is explicitly:\n%s" % H.str()

J = ToricIdeal( H )
# print "J = %s" % J
b = J.groebner_basis()
print "The Groebner basis of J is... %s" % b

This works and gives:

H = 29 x 35 dense matrix over Finite Field of size 2
The parity check matrix H is explicitly:
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1]
The Groebner basis of J is... Polynomial Sequence with 523 Polynomials in 35 Variables

(The methods have changed the name and the way to call them.)

Later edit:

I was expecting to have some short exact sequence $0\to F^6\overset G\to F^{35}\overset H\to F^{35-6}\to 0$ with the matrices $G,H$ over the arrows. (Here $F$ is the field with two elements.) But the shapes of the matrices do not fit for the product. Instead, one has to transpose the one or the other matrix, so that the following maps make sense by tacitly identifiying $F^k$ with the corresponding space of row matrices $1\times k$ : $0\to F^6\overset {\cdot G}\longrightarrow F^{35}\overset {\cdot H'}\longrightarrow F^{35-6}\to 0$ and dually $0\to F^{35-6}\overset {\cdot H}\longrightarrow F^{35}\overset {\cdot G'}\longrightarrow F^6\to 0$ and the sage check is as follows:

sage: G * H.transpose()
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: ( G * H.transpose() ) . is_zero()
True
sage: ( H * G.transpose() ) . is_zero()
True
sage: H.transpose().kernel() == G.image()
True
sage: G.transpose().kernel() == H.image()
True

link

add a comment

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

Grobner basis savecancel

Comments

1 Answer