Set Cover.sagews

def setcover_to_gb(T,S,W,c):
    P = PolynomialRing(QQ, len(S), "x", order="lex")
    x=P.gens()
    I = list()
    for i in range(0,len(S)): 
        I.append(x[i]^2-x[i]);
    for i in range(0,len(T)):
        t = 1
        for j in range(0,len(S)):
            for k in range(0,len(S[j])):
                A=S[j]
                if A[k]==T[i]:
                    t=t*(x[j]-1);
                #end if
            #end for
        #endfor
        I.append(t);
    #endfor
    cweights = -c
    for i in range(0,len(W)):
        cweights = cweights + W[i]*x[i];
    I.append(cweights)
    I = P.ideal(I)
    print("") + str(I)
    G = I.groebner_basis()
    #print("G: ") + str(G)
    return(G);
#end function

def classicpartition_to_gb(W):
    P = PolynomialRing(QQ, len(W), "x", order="lex")
    x=P.gens()
    I = list()
    s = 0
    for i in range(0,len(W)):
        I.append(x[i]^2-1)
        s = s + W[i]*x[i];
    I.append(s)
    I = P.ideal(I)
    G = I.groebner_basis();
    print("G: ") + str(G)
    return(G);

def setcoverpartition_to_gb(T,S,W,c):
    P = PolynomialRing(QQ, len(S), "x", order="lex")
    x=P.gens()
    I = list()
    for i in range(0,len(S)): 
        I.append(x[i]^2-1);
    for i in range(0,len(T)):
        t = 1
        for j in range(0,len(S)):
            for k in range(0,len(S[j])):
                A=S[j]
                if A[k]==T[i]:
                    t=t*(x[j]-1);
                #end if
            #end for
        #endfor
        I.append(t);
    #endfor
    s = 0
    for i in range(0,len(W)):
        I.append(x[i]^2-1)
        s = s + W[i]*x[i];
    I.append(s)
    I = P.ideal(I)
    print("") + str(I)
    G = I.groebner_basis()
    print("G: ") + str(G)
    return(G);
#end function

def vertexcover_gb(G,c):
    T = G.edges
    W = (1 for j in range(G.order))
    S = list()
    for i in range(G.order()):
        S.append(G.edges_incident(i));
    setcover_to_gb(T,S,W,c);

# W = [1,1,2]
# classicpartition_to_gb(W)
# W = [1,2]
# classicpartition_to_gb(W)

T = [0,1,2]
S = [[0,1],[0,2],[1,2]]
W=[1,1,1]
print("T: ") + str(T)
print("S. ") + str(S)
setcover_to_gb(T,S,W,1)
setcover_to_gb(T,S,W,2)

print(" ")

T= [0,1,2,3]
S = [[0,1,2],[0,1,3],[0,2,3],[1,2,3]]
W = [1,1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,1)
setcover_to_gb(T,S,W,2)

print(" ")

T = [0,1,2]
S = [[0,1,2]]
W = [1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,1)

print(" ")

T = [0,1,2]
S = [[0],[1],[2]]
W = [1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,3)

print(" ")

T = [0,1,2]
S = [[0,1,2],[0],[1],[2]]
W = [1,1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,1)

print(" ")

T = [0,1,2,3]
S = [[0,1,2,3],[0],[1],[2],[1,2],[0,3]]
W = [1,1,1,1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,1)

print(" ")

T = [0,1,2,3,4,5]
S = [[0,1,2],[2,3,4],[4,5,0]]
W = [1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,3)

print(" ")

T = [0,1,2,3,4,5,6,7]
S = [[0,1],[2,3],[4,5],[6,7],[0,4],[1,5],[2,6],[3,7]]
W=[1,1,1,1,1,1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,4)

print(" ")

T = [0,1,2,3]
S = [[0,1],[2,3],[1],[3]]
W=[1,1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,2)

print(" ")

P = graphs.PetersenGraph()
plot(P)
T = P.edges()
W = (1,1,1,1,1,1,1,1,1,1)
S = list()
for i in range(P.order()):
    S.append(P.edges_incident(i));
print str(S)
print "Groebner Basis for Vertex Cover with 5 Vertices"
setcover_to_gb(T,S,W,5)
print "Groebner Basis for Vertex Cover with 6 Vertices"
setcover_to_gb(T,S,W,6)

print(" ")

T = [0,1,2,3]
S = [[0,1],[1,2,3],[2,3]]
W = [1,1,1]
print("T: ") + str(T)
print("S: ") + str(S)
setcover_to_gb(T,S,W,2)

T: [0, 1, 2] S. [[0, 1], [0, 2], [1, 2]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x0*x1 - x0 - x1 + 1, x0*x2 - x0 - x2 + 1, x1*x2 - x1 - x2 + 1, x0 + x1 + x2 - 1) of Multivariate Polynomial Ring in x0, x1, x2 over Rational Field [1] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x0*x1 - x0 - x1 + 1, x0*x2 - x0 - x2 + 1, x1*x2 - x1 - x2 + 1, x0 + x1 + x2 - 2) of Multivariate Polynomial Ring in x0, x1, x2 over Rational Field [x0 + x1 + x2 - 2, x1^2 - x1, x1*x2 - x1 - x2 + 1, x2^2 - x2] T: [0, 1, 2, 3] S: [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x0*x1*x2 - x0*x1 - x0*x2 + x0 - x1*x2 + x1 + x2 - 1, x0*x1*x3 - x0*x1 - x0*x3 + x0 - x1*x3 + x1 + x3 - 1, x0*x2*x3 - x0*x2 - x0*x3 + x0 - x2*x3 + x2 + x3 - 1, x1*x2*x3 - x1*x2 - x1*x3 + x1 - x2*x3 + x2 + x3 - 1, x0 + x1 + x2 + x3 - 1) of Multivariate Polynomial Ring in x0, x1, x2, x3 over Rational Field [1] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x0*x1*x2 - x0*x1 - x0*x2 + x0 - x1*x2 + x1 + x2 - 1, x0*x1*x3 - x0*x1 - x0*x3 + x0 - x1*x3 + x1 + x3 - 1, x0*x2*x3 - x0*x2 - x0*x3 + x0 - x2*x3 + x2 + x3 - 1, x1*x2*x3 - x1*x2 - x1*x3 + x1 - x2*x3 + x2 + x3 - 1, x0 + x1 + x2 + x3 - 2) of Multivariate Polynomial Ring in x0, x1, x2, x3 over Rational Field [x0 + x1 + x2 + x3 - 2, x1^2 - x1, x1*x2 + x1*x3 - x1 + x2*x3 - x2 - x3 + 1, x2^2 - x2, x3^2 - x3] T: [0, 1, 2] S: [[0, 1, 2]] Ideal (x^2 - x, x - 1, x - 1, x - 1, x - 1) of Multivariate Polynomial Ring in x over Rational Field [x - 1] T: [0, 1, 2] S: [[0], [1], [2]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x0 - 1, x1 - 1, x2 - 1, x0 + x1 + x2 - 3) of Multivariate Polynomial Ring in x0, x1, x2 over Rational Field [x0 - 1, x1 - 1, x2 - 1] T: [0, 1, 2] S: [[0, 1, 2], [0], [1], [2]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x0*x1 - x0 - x1 + 1, x0*x2 - x0 - x2 + 1, x0*x3 - x0 - x3 + 1, x0 + x1 + x2 + x3 - 1) of Multivariate Polynomial Ring in x0, x1, x2, x3 over Rational Field [x0 - 1, x1, x2, x3] T: [0, 1, 2, 3] S: [[0, 1, 2, 3], [0], [1], [2], [1, 2], [0, 3]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x4^2 - x4, x5^2 - x5, x0*x1*x5 - x0*x1 - x0*x5 + x0 - x1*x5 + x1 + x5 - 1, x0*x2*x4 - x0*x2 - x0*x4 + x0 - x2*x4 + x2 + x4 - 1, x0*x3*x4 - x0*x3 - x0*x4 + x0 - x3*x4 + x3 + x4 - 1, x0*x5 - x0 - x5 + 1, x0 + x1 + x2 + x3 + x4 + x5 - 1) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5 over Rational Field [x0 - 1, x1, x2, x3, x4, x5] T: [0, 1, 2, 3, 4, 5] S: [[0, 1, 2], [2, 3, 4], [4, 5, 0]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x0*x2 - x0 - x2 + 1, x0 - 1, x0*x1 - x0 - x1 + 1, x1 - 1, x1*x2 - x1 - x2 + 1, x2 - 1, x0 + x1 + x2 - 3) of Multivariate Polynomial Ring in x0, x1, x2 over Rational Field [x0 - 1, x1 - 1, x2 - 1] T: [0, 1, 2, 3, 4, 5, 6, 7] S: [[0, 1], [2, 3], [4, 5], [6, 7], [0, 4], [1, 5], [2, 6], [3, 7]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x4^2 - x4, x5^2 - x5, x6^2 - x6, x7^2 - x7, x0*x4 - x0 - x4 + 1, x0*x5 - x0 - x5 + 1, x1*x6 - x1 - x6 + 1, x1*x7 - x1 - x7 + 1, x2*x4 - x2 - x4 + 1, x2*x5 - x2 - x5 + 1, x3*x6 - x3 - x6 + 1, x3*x7 - x3 - x7 + 1, x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7 - 4) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7 over Rational Field [x0 + x5 - 1, x1 + x7 - 1, x2 + x5 - 1, x3 + x7 - 1, x4 - x5, x5^2 - x5, x6 - x7, x7^2 - x7] T: [0, 1, 2, 3] S: [[0, 1], [2, 3], [1], [3]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x0 - 1, x0*x2 - x0 - x2 + 1, x1 - 1, x1*x3 - x1 - x3 + 1, x0 + x1 + x2 + x3 - 2) of Multivariate Polynomial Ring in x0, x1, x2, x3 over Rational Field [x0 - 1, x1 - 1, x2, x3]

[[(0, 1, None), (0, 4, None), (0, 5, None)], [(0, 1, None), (1, 2, None), (1, 6, None)], [(1, 2, None), (2, 3, None), (2, 7, None)], [(2, 3, None), (3, 4, None), (3, 8, None)], [(0, 4, None), (3, 4, None), (4, 9, None)], [(0, 5, None), (5, 7, None), (5, 8, None)], [(1, 6, None), (6, 8, None), (6, 9, None)], [(2, 7, None), (5, 7, None), (7, 9, None)], [(3, 8, None), (5, 8, None), (6, 8, None)], [(4, 9, None), (6, 9, None), (7, 9, None)]] Groebner Basis for Vertex Cover with 5 Vertices Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x4^2 - x4, x5^2 - x5, x6^2 - x6, x7^2 - x7, x8^2 - x8, x9^2 - x9, x0*x1 - x0 - x1 + 1, x0*x4 - x0 - x4 + 1, x0*x5 - x0 - x5 + 1, x1*x2 - x1 - x2 + 1, x1*x6 - x1 - x6 + 1, x2*x3 - x2 - x3 + 1, x2*x7 - x2 - x7 + 1, x3*x4 - x3 - x4 + 1, x3*x8 - x3 - x8 + 1, x4*x9 - x4 - x9 + 1, x5*x7 - x5 - x7 + 1, x5*x8 - x5 - x8 + 1, x6*x8 - x6 - x8 + 1, x6*x9 - x6 - x9 + 1, x7*x9 - x7 - x9 + 1, x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 - 5) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 over Rational Field [1] Groebner Basis for Vertex Cover with 6 Vertices Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x4^2 - x4, x5^2 - x5, x6^2 - x6, x7^2 - x7, x8^2 - x8, x9^2 - x9, x0*x1 - x0 - x1 + 1, x0*x4 - x0 - x4 + 1, x0*x5 - x0 - x5 + 1, x1*x2 - x1 - x2 + 1, x1*x6 - x1 - x6 + 1, x2*x3 - x2 - x3 + 1, x2*x7 - x2 - x7 + 1, x3*x4 - x3 - x4 + 1, x3*x8 - x3 - x8 + 1, x4*x9 - x4 - x9 + 1, x5*x7 - x5 - x7 + 1, x5*x8 - x5 - x8 + 1, x6*x8 - x6 - x8 + 1, x6*x9 - x6 - x9 + 1, x7*x9 - x7 - x9 + 1, x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 - 6) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 over Rational Field [x0 - x7 + 2*x8*x9 - x8 - 2*x9 + 1, x1 - 2*x8*x9 + x8 + x9 - 1, x2 + x7 + x8*x9 - x8 - 1, x3 - x7 + x8 - x9, x4 + x7 - x8*x9 + 2*x9 - 2, x5 + x7 - x8*x9 + x8 + x9 - 2, x6 + x8*x9 - 1, x7^2 - x7, x7*x8 - x7 + x8*x9 - x8 - x9 + 1, x7*x9 - x7 - x9 + 1, x8^2 - x8, x9^2 - x9] T: [0, 1, 2, 3] S: [[0, 1], [1, 2, 3], [2, 3]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x0 - 1, x0*x1 - x0 - x1 + 1, x1*x2 - x1 - x2 + 1, x1*x2 - x1 - x2 + 1, x0 + x1 + x2 - 2) of Multivariate Polynomial Ring in x0, x1, x2 over Rational Field [x0 - 1, x1 + x2 - 1, x2^2 - x2] T: [0, 1, 2] S: [[0], [1], [2]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x0 - 1, x1 - 1, x2 - 1, x0 + x1 + x2 - 3) of Multivariate Polynomial Ring in x0, x1, x2 over Rational Field [x0 - 1, x1 - 1, x2 - 1] T: [0, 1, 2] S: [[0, 1, 2], [0], [1], [2]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x0*x1 - x0 - x1 + 1, x0*x2 - x0 - x2 + 1, x0*x3 - x0 - x3 + 1, x0 + x1 + x2 + x3 - 1) of Multivariate Polynomial Ring in x0, x1, x2, x3 over Rational Field [x0 - 1, x1, x2, x3] T: [0, 1, 2, 3] S: [[0, 1, 2, 3], [0], [1], [2], [1, 2], [0, 3]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x4^2 - x4, x5^2 - x5, x0*x1*x5 - x0*x1 - x0*x5 + x0 - x1*x5 + x1 + x5 - 1, x0*x2*x4 - x0*x2 - x0*x4 + x0 - x2*x4 + x2 + x4 - 1, x0*x3*x4 - x0*x3 - x0*x4 + x0 - x3*x4 + x3 + x4 - 1, x0*x5 - x0 - x5 + 1, x0 + x1 + x2 + x3 + x4 + x5 - 1) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5 over Rational Field [x0 - 1, x1, x2, x3, x4, x5] T: [0, 1, 2, 3, 4, 5] S: [[0, 1, 2], [2, 3, 4], [4, 5, 0]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x0*x2 - x0 - x2 + 1, x0 - 1, x0*x1 - x0 - x1 + 1, x1 - 1, x1*x2 - x1 - x2 + 1, x2 - 1, x0 + x1 + x2 - 3) of Multivariate Polynomial Ring in x0, x1, x2 over Rational Field [x0 - 1, x1 - 1, x2 - 1] T: [0, 1, 2, 3, 4, 5, 6, 7] S: [[0, 1], [2, 3], [4, 5], [6, 7], [0, 4], [1, 5], [2, 6], [3, 7]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x4^2 - x4, x5^2 - x5, x6^2 - x6, x7^2 - x7, x0*x4 - x0 - x4 + 1, x0*x5 - x0 - x5 + 1, x1*x6 - x1 - x6 + 1, x1*x7 - x1 - x7 + 1, x2*x4 - x2 - x4 + 1, x2*x5 - x2 - x5 + 1, x3*x6 - x3 - x6 + 1, x3*x7 - x3 - x7 + 1, x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7 - 4) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7 over Rational Field [x0 + x5 - 1, x1 + x7 - 1, x2 + x5 - 1, x3 + x7 - 1, x4 - x5, x5^2 - x5, x6 - x7, x7^2 - x7] T: [0, 1, 2, 3] S: [[0, 1], [2, 3], [1], [3]] Ideal (x0^2 - x0, x1^2 - x1, x2^2 - x2, x3^2 - x3, x0 - 1, x0*x2 - x0 - x2 + 1, x1 - 1, x1*x3 - x1 - x3 + 1, x0 + x1 + x2 + x3 - 2) of Multivariate Polynomial Ring in x0, x1, x2, x3 over Rational Field [x0 - 1, x1 - 1, x2, x3]

load('func_strip_zeros.sage')

#Computing for degree 2 ...  (35) 0  (25) 0s.
#print_linear_system()
# A is 10 x 10
A = matrix(QQ, 10, 10);
row = 0;
# 0: 1
A[row,4]=1;A[row,6]=-1;A[row,3]=1;A[row,5]=1;row = row + 1;
# 1: x[0]
A[row,4]=-1;A[row,0]=-1;A[row,7]=-1;A[row,6]=1;A[row,3]=-1;row = row + 1;
# 2: x[1]
A[row,6]=1;A[row,8]=-1;A[row,1]=-1;A[row,5]=-1;A[row,3]=-1;row = row + 1;
# 3: x[2]
A[row,4]=-1;A[row,2]=-1;A[row,6]=1;A[row,5]=-1;A[row,9]=-1;row = row + 1;
# 4: x[0]^2
A[row,0]=1;A[row,7]=1;row = row + 1;
# 5: x[0]*x[1]
A[row,3]=1;A[row,7]=1;A[row,8]=1;row = row + 1;
# 6: x[0]*x[2]
A[row,7]=1;A[row,9]=1;A[row,4]=1;row = row + 1;
# 7: x[1]^2
A[row,1]=1;A[row,8]=1;row = row + 1;
# 8: x[1]*x[2]
A[row,8]=1;A[row,5]=1;A[row,9]=1;row = row + 1;
# 9: x[2]^2
A[row,9]=1;A[row,2]=1;
A
det(A)
#cert := (1/2)*(x[0]^2-x[0]) + (1/2)*(x[1]^2-x[1]) + (1/2)*(x[2]^2-x[2]) + (1)*(x[0]*x[1]-x[0]-x[1]+1) + (1)*(x[0]*x[2]-x[0]-x[2]+1) + (1)*(x[1]*x[2]-x[1]-x[2]+1) + (2-1/2*x[0]-1/2*x[1]-1/2*x[2])*(x[0]+x[1]+x[2]-1);

###############################
# next example ex2.nulla
#Computing for degree 3 ...  (148) 0  (130) 0s.
#print_linear_system()
# A is 35 x 39
A = matrix(QQ, 35, 39);
row = 0;
# 0: 1
A[row,21]=-1;A[row,24]=-1;A[row,23]=-1;A[row,22]=-1;A[row,20]=-1;row = row + 1;
# 1: x[0]
A[row,22]=1;A[row,20]=1;A[row,24]=1;A[row,25]=-1;A[row,21]=1;A[row,0]=-1;row = row + 1;
# 2: x[1]
A[row,20]=1;A[row,21]=1;A[row,24]=1;A[row,23]=1;A[row,26]=-1;A[row,5]=-1;row = row + 1;
# 3: x[2]
A[row,22]=1;A[row,20]=1;A[row,10]=-1;A[row,24]=1;A[row,23]=1;A[row,27]=-1;row = row + 1;
# 4: x[3]
A[row,22]=1;A[row,21]=1;A[row,24]=1;A[row,23]=1;A[row,15]=-1;A[row,28]=-1;row = row + 1;
# 5: x[0]^2
A[row,0]=1;A[row,29]=-1;A[row,1]=-1;A[row,25]=1;row = row + 1;
# 6: x[0]*x[1]
A[row,20]=-1;A[row,30]=-1;A[row,2]=-1;A[row,26]=1;A[row,6]=-1;A[row,21]=-1;A[row,25]=1;row = row + 1;
# 7: x[0]*x[2]
A[row,31]=-1;A[row,3]=-1;A[row,27]=1;A[row,22]=-1;A[row,20]=-1;A[row,25]=1;A[row,11]=-1;row = row + 1;
# 8: x[0]*x[3]
A[row,22]=-1;A[row,32]=-1;A[row,4]=-1;A[row,28]=1;A[row,25]=1;A[row,16]=-1;A[row,21]=-1;row = row + 1;
# 9: x[1]^2
A[row,26]=1;A[row,5]=1;A[row,33]=-1;A[row,7]=-1;row = row + 1;
# 10: x[1]*x[2]
A[row,26]=1;A[row,27]=1;A[row,34]=-1;A[row,8]=-1;A[row,20]=-1;A[row,12]=-1;A[row,23]=-1;row = row + 1;
# 11: x[1]*x[3]
A[row,21]=-1;A[row,17]=-1;A[row,26]=1;A[row,23]=-1;A[row,28]=1;A[row,35]=-1;A[row,9]=-1;row = row + 1;
# 12: x[2]^2
A[row,13]=-1;A[row,10]=1;A[row,27]=1;A[row,36]=-1;row = row + 1;
# 13: x[2]*x[3]
A[row,22]=-1;A[row,23]=-1;A[row,28]=1;A[row,37]=-1;A[row,18]=-1;A[row,27]=1;A[row,14]=-1;row = row + 1;
# 14: x[3]^2
A[row,15]=1;A[row,38]=-1;A[row,28]=1;A[row,19]=-1;row = row + 1;
# 15: x[0]^3
#A[row,1]=1;A[row,29]=1;row = row + 1;
# 16: x[0]^2*x[1]
A[row,2]=1;A[row,30]=1;A[row,29]=1;row = row + 1;
# 17: x[0]^2*x[2]
A[row,3]=1;A[row,31]=1;A[row,29]=1;row = row + 1;
# 18: x[0]^2*x[3]
A[row,29]=1;A[row,4]=1;A[row,32]=1;row = row + 1;
# 19: x[0]*x[1]^2
A[row,6]=1;A[row,30]=1;A[row,33]=1;row = row + 1;
# 20: x[0]*x[1]*x[2]
A[row,30]=1;A[row,20]=1;A[row,31]=1;A[row,34]=1;row = row + 1;
# 21: x[0]*x[1]*x[3]
A[row,30]=1;A[row,21]=1;A[row,32]=1;A[row,35]=1;row = row + 1;
# 22: x[0]*x[2]^2
A[row,31]=1;A[row,11]=1;A[row,36]=1;row = row + 1;
# 23: x[0]*x[2]*x[3]
A[row,22]=1;A[row,31]=1;A[row,32]=1;A[row,37]=1;row = row + 1;
# 24: x[0]*x[3]^2
A[row,16]=1;A[row,32]=1;A[row,38]=1;row = row + 1;
# 25: x[1]^3
#A[row,33]=1;A[row,7]=1;row = row + 1;
# 26: x[1]^2*x[2]
A[row,33]=1;A[row,34]=1;A[row,8]=1;row = row + 1;
# 27: x[1]^2*x[3]
A[row,35]=1;A[row,9]=1;A[row,33]=1;row = row + 1;
# 28: x[1]*x[2]^2
A[row,12]=1;A[row,34]=1;A[row,36]=1;row = row + 1;
# 29: x[1]*x[2]*x[3]
A[row,34]=1;A[row,35]=1;A[row,37]=1;A[row,23]=1;row = row + 1;
# 30: x[1]*x[3]^2
A[row,35]=1;A[row,38]=1;A[row,17]=1;row = row + 1;
# 31: x[2]^3
#A[row,13]=1;A[row,36]=1;row = row + 1;
# 32: x[2]^2*x[3]
A[row,36]=1;A[row,14]=1;A[row,37]=1;row = row + 1;
# 33: x[2]*x[3]^2
A[row,37]=1;A[row,18]=1;A[row,38]=1;row = row + 1;
# 34: x[3]^3
#A[row,38]=1;A[row,19]=1;

L = strip_zero_matrix(A)
A = L['M'];


P.<x0,x1,x2,x3> = PolynomialRing(QQ, 4, order='lex')
#x = P.gens()
cert = (7/6-1/3*x1-1/3*x2-1/3*x3)*(x0^2-x0) + (7/6-1/3*x0-1/3*x2-1/3*x3)*(x1^2-x1) + (7/6-1/3*x0-1/3*x1-1/3*x3)*(x2^2-x2) + (7/6-1/3*x0-1/3*x1-1/3*x2)*(x3^2-x3) + (-1)*(x0*x1*x2-x0*x1-x0*x2+x0-x1*x2+x1+x2-1) + (-1)*(x0*x1*x3-x0*x1-x0*x3+x0-x1*x3+x1+x3-1) + (-1)*(x0*x2*x3-x0*x2-x0*x3+x0-x2*x3+x2+x3-1) + (-1)*(x1*x2*x3-x1*x2-x1*x3+x1-x2*x3+x2+x3-1) + (3-7/6*x0-7/6*x1-7/6*x2-7/6*x3+1/3*x0*x1+1/3*x0*x2+1/3*x0*x3+1/3*x1*x2+1/3*x1*x3+1/3*x2*x3)*(x0+x1+x2+x3-1);

#cert = (7/6-1/3*x(1)-1/3*x(2)-1/3*x(3))*(x(0)^2-x(0)) + (7/6-1/3*x(0)-1/3*x(2)-1/3*x(3))*(x(1)^2-x(1)) + (7/6-1/3*x(0)-1/3*x(1)-1/3*x(3))*(x(2)^2-x(2)) + (7/6-1/3*x(0)-1/3*x(1)-1/3*x(2))*(x(3)^2-x(3)) + (-1)*(x(0)*x(1)*x(2)-x(0)*x(1)-x(0)*x(2)+x(0)-x(1)*x(2)+x(1)+x(2)-1) + (-1)*(x(0)*x(1)*x(3)-x(0)*x(1)-x(0)*x(3)+x(0)-x(1)*x(3)+x(1)+x(3)-1) + (-1)*(x(0)*x(2)*x(3)-x(0)*x(2)-x(0)*x(3)+x(0)-x(2)*x(3)+x(2)+x(3)-1) + (-1)*(x(1)*x(2)*x(3)-x(1)*x(2)-x(1)*x(3)+x(1)-x(2)*x(3)+x(2)+x(3)-1) + (3-7/6*x(0)-7/6*x(1)-7/6*x(2)-7/6*x(3)+1/3*x(0)*x(1)+1/3*x(0)*x(2)+1/3*x(0)*x(3)+1/3*x(1)*x(2)+1/3*x(1)*x(3)+1/3*x(2)*x(3))*(x(0)+x(1)+x(2)+x(3)-1);


cert
#expand(cert)

A
for i in range(0,A.nrows()):
    row_str = ""
    for j in range (0,A.ncols()):
        #print A[i,j]
        row_str = row_str + " " + str(A[i,j])
    # end for
    print row_str

[ 0 0 0 1 1 1 -1 0 0 0] [-1 0 0 -1 -1 0 1 -1 0 0] [ 0 -1 0 -1 0 -1 1 0 -1 0] [ 0 0 -1 0 -1 -1 1 0 0 -1] [ 1 0 0 0 0 0 0 1 0 0] [ 0 0 0 1 0 0 0 1 1 0] [ 0 0 0 0 1 0 0 1 0 1] [ 0 1 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 1 1] [ 0 0 1 0 0 0 0 0 0 1] -2 A is 35 x 39 M is 30 x 35 1 30 x 35 dense matrix over Rational Field -1 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 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 1 1 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 -1 0 0 0 0 0 0 0 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 -1 0 0 0 0 1 1 1 1 0 0 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 1 0 0 0 -1 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 -1 -1 0 0 0 1 1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 -1 0 0 1 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 -1 0 0 1 0 0 1 0 0 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 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 -1 0 0 -1 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 -1 0 -1 0 0 1 0 1 0 0 0 0 0 0 -1 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 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 -1 -1 0 0 0 1 1 0 0 0 0 0 0 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 1 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 0 0 0 0 0 1 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 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 1 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 0 0 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 1 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 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 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 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 1 0 0 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 1 0 0 0 0 0 1 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 1 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 0 0 0 1 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 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 1 0 0 0 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 1 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 1 0 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 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

# this is the matrix associated with the Nullstellensatz certificate of 
# NO vertex cover of size 1 for the graph K3
# with unknown weights w0,w1,w2 on the vertices
#Computing for degree 2 ...  (35) 0  (25) 0s.
#print_linear_system()
# A is 10 x 10
A = matrix(QQ, 10, 10);
row = 0;
# 0: 1
# c6 is the constant term of the generator multiplying (w0*x0 + w1*x1)
A[row,4]=1;A[row,6]=-1;A[row,3]=1;A[row,5]=1;row = row + 1;
# 1: x[0]
A[row,4]=-1;A[row,0]=-1;A[row,7]=-1;A[row,6]=1;A[row,3]=-1;row = row + 1;
# 2: x[1]
A[row,6]=1;A[row,8]=-1;A[row,1]=-1;A[row,5]=-1;A[row,3]=-1;row = row + 1;
# 3: x[2]
A[row,4]=-1;A[row,2]=-1;A[row,6]=1;A[row,5]=-1;A[row,9]=-1;row = row + 1;
# 4: x[0]^2
A[row,0]=1;A[row,7]=1;row = row + 1;
# 5: x[0]*x[1]
A[row,3]=1;A[row,7]=1;A[row,8]=1;row = row + 1;
# 6: x[0]*x[2]
A[row,7]=1;A[row,9]=1;A[row,4]=1;row = row + 1;
# 7: x[1]^2
A[row,1]=1;A[row,8]=1;row = row + 1;
# 8: x[1]*x[2]
A[row,8]=1;A[row,5]=1;A[row,9]=1;row = row + 1;
# 9: x[2]^2
A[row,9]=1;A[row,2]=1;
A
det(A)
#cert := (1/2)*(x[0]^2-x[0]) + (1/2)*(x[1]^2-x[1]) + (1/2)*(x[2]^2-x[2]) + (1)*(x[0]*x[1]-x[0]-x[1]+1) + (1)*(x[0]*x[2]-x[0]-x[2]+1) + (1)*(x[1]*x[2]-x[1]-x[2]+1) + (2-1/2*x[0]-1/2*x[1]-1/2*x[2])*(x[0]+x[1]+x[2]-1);