Ask Your Question
0

Grobner basis

asked 2016-12-05 04:03:07 -0500

Nilesh gravatar image

updated 2016-12-06 03:42:28 -0500

tmonteil gravatar image

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

Comments

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

tmonteil gravatar imagetmonteil ( 2016-12-06 03:44:32 -0500 )edit

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

slelievre gravatar imageslelievre ( 2016-12-06 06:27:14 -0500 )edit

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

asante gravatar imageasante ( 2017-01-13 02:33:27 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-03-25 20:25:39 -0500

dan_fulea gravatar image

updated 2017-03-26 05:47:32 -0500

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

Stats

Asked: 2016-12-05 04:03:07 -0500

Seen: 148 times

Last updated: Mar 26