Ask Your Question
1

matrix over symbolic ring to matrix over finite field

asked 2021-03-16 04:53:18 +0200

anne gravatar image

updated 2021-03-23 03:04:03 +0200

I have a bunch of ideals defined symbolically, that I would like to decompose over GF(101).

However I think that the only symbolic computation that's happening is when I define the matrices whose minors give me the ideals.

So, once a matrix is constructed, is it possible to reduce it mod p? Thanks for any help!

EDIT 1: I have a list of variables svs = x_{i}_{j}_{k} and it is used to define a ring

R = PolynomialRing(GF(101),svs)
R.inject_variables()

Then I introduce the symbolic variables var('x, s') in order to form a list of companion matrices. For concreteness let's say I have two companion matrices, one for p = x**2 * (x-s)**3 and one for q = x - s. I make a list

L = [companion_matrix(p.coefficients(x, sparse=False), format='bottom'),
     companion_matrix(q.coefficients(x, sparse=False), format='bottom')]

Finally I create a block matrix block_matrix(R['s'], L).

Next I look at ideals of minors of this matrix. So I might have a relation like rel = [x_1_2_1, x_1_2_1*s] that I use to define an ideal I = ideal(rel). I want to apply groebner_basis and primary_decomposition to these ideals but I run into errors like Ideal_generic' object has no attribute 'groebner_basis or Not implemented.

So the question is at what point and how should I tell sage that s is no longer to be treated as a symbolic variable. By the way I = R['s'].ideal(rel) also results in a class generic ideal.

I also tried S.<s> = PolynomialRing(R) and S.ideal([x_1_2_1, x_1_2_1*polynomial(s, base_ring=R)]) which did not work.

Sorry for being such a data types ignoramus!

EDIT 2: Here's a non-minimal example of how the x_i_j_k end up in my (block) matrices.

Use inputs

mu1, mu2, mu = [1,1],[1,1],[2,2]

on

def mu_vars(mu):
    svs = [] 
    for i in range(1,2):
        for j in range(i+1,2+1):
            for k in range(0,mu[j-1]):
                svs.append('x_{}_{}_{}'.format(i,j,k+1))
    return svs

svs = mu_vars(mu) 
R = PolynomialRing(GF(101),svs)  
R.inject_variables()

def insert_row(mat,row):
    return matrix(mat.rows()[:mat.nrows()]+[row]+mat.rows()[mat.nrows():])

def upper_row_matrix(row):
    symbMat = []
    for i in range(row,2):
        mat = matrix(mu[row-1]-1,mu[i])
        v = [var(v) for v in svs if v.startswith('x_{}_{}'.format(row,i+1))]
        d = insert_row(mat,v)
        symbMat.append(d)
    return symbMat

var('x,s')

def mu_matrix(mu1,mu2):
    symbMat = []
    for i in range(0,2):
        row = [] + [0]*i
        p = x**(mu1[i])*(x-s)**(mu2[i])
        row.append(companion_matrix(p.coefficients(x,sparse=False),format='bottom'))
        row += upper_row_matrix(i+1)
        symbMat.append(row)
    return block_matrix(R['s'],symbMat)

Run m = mu_matrix(mu1,mu2) to get

[      0       1|      0       0]
[      0       s|x_1_2_1 x_1_2_2]
[---------------+---------------]
[      0       0|      0       1]
[      0       0|      0       s]

consider m.minors(2)[29] which is x_1_2_1*s. Then for example the ideal ideal(m.minors(2)[29]) does not have a groebner basis. In particular the call ideal(m.minors(2)[29]).groebner_basis() ends in error.

edit retag flag offensive close merge delete

Comments

2

Please give us a small concrete example, with self-contained code.

FrédéricC gravatar imageFrédéricC ( 2021-03-16 09:35:43 +0200 )edit

Edited. No self-contained code. But enough detail I think to render the issue intelligible.

anne gravatar imageanne ( 2021-03-22 02:46:20 +0200 )edit
1

Yes, please add a complete block of code that ends in an error. So far, it is not clear how e.g. x_1_2_1 ends up in the matrix (with the current code, it doesn't). Also, the best way to solve your issue will be to skip the symbolic ring altogether.

rburing gravatar imagerburing ( 2021-03-22 11:59:22 +0200 )edit

@rburing my bad, thanks - added how the x's appear in the matrix. How would you skip the symbolic ring if your matrices involve companion matrices?

anne gravatar imageanne ( 2021-03-23 02:49:44 +0200 )edit

2 Answers

Sort by » oldest newest most voted
1

answered 2021-03-23 07:35:53 +0200

rburing gravatar image

In the code you added, the ideal ends up in a univariate polynomial ring over a multivariate polynomial ring, rather than a multivariate polynomial ring with an extra variable.

Here is a version (avoiding the symbolic ring) where the ideal ends up in the correct ring:

mu1, mu2, mu = [1,1],[1,1],[2,2]

def mu_vars(mu):
    svs = [] 
    for i in range(1,2):
        for j in range(i+1,2+1):
            for k in range(0,mu[j-1]):
                svs.append('x_{}_{}_{}'.format(i,j,k+1))
    return svs

svs = mu_vars(mu) 
R = PolynomialRing(GF(101), ['s'] + svs, order='degrevlex')
s = R.gen(0)

def insert_row(mat,row):
    return matrix(R, mat.rows()[:mat.nrows()]+[row]+mat.rows()[mat.nrows():])

def upper_row_matrix(row):
    symbMat = []
    for i in range(row,2):
        mat = matrix(R, mu[row-1]-1,mu[i])
        v = [v for v in svs if v.startswith('x_{}_{}'.format(row,i+1))]
        d = insert_row(mat,v)
        symbMat.append(d)
    return symbMat

def mu_matrix(mu1,mu2):
    x = polygen(R)
    symbMat = []
    for i in range(0,2):
        row = [] + [0]*i
        p = x**(mu1[i])*(x-s)**(mu2[i])
        row.append(companion_matrix(p.coefficients(sparse=False),format='bottom'))
        row += upper_row_matrix(i+1)
        symbMat.append(row)
    return block_matrix(R,symbMat)

m = mu_matrix(mu1,mu2)

R.ideal(m.minors(2)[29]).groebner_basis()

You may want to adapt the monomial ordering.

A good rule of thumb is that it is better to be explicit than implicit: when defining matrices and ideals, specify the ring that they are to be defined over. And avoid the symbolic ring when possible.

(The above could also be adapted so that the extra variable s is not in R but in a second polynomial ring.)

edit flag offensive delete link more
0

answered 2021-03-22 11:48:46 +0200

Emmanuel Charpentier gravatar image

updated 2021-03-22 13:57:10 +0200

The problem is that, fundamentally, a symbolic expression is a tree whose leaf nodes are variables, whereas a polynomial is a list of (monomial, coefficient) pairs the monomials being themselves lists of (indeterminate, power) pairs; the fact that the notations "^", "+" and "*" are homonyms is (almost) an historical accident. A symbolic expression may have an analytic meaning, a polynomial is strictly algebraic.

There is no built-in way for Sage to construct the list you wish to build from your tree. However, it can be done using the (accidental) common representation... as a character string. The following horror works :

sage: Lv = ("x", "y")
sage: Li = ("u", "v")
sage: var(Lv)
(x, y)
sage: R1=PolynomialRing(GF(101), Li)
sage: P = x^2 - x*y + y^3
sage: S = repr(P)
sage: for r in zip(Lv, Li) : S = S.replace(r[0], r[1])
sage: Q = R1(S)
sage: Q
v^3 + u^2 - u*v
sage: Q.parent()
Multivariate Polynomial Ring in u, v over Finite Field of size 101

but keep in mind that this is a pure typographical manipulation, with no intrinsic mathematical meaning at the level of the symbols used. (This has of course a mathematical meaning in terms of manipulation of strings..., but this is irrelevant to your problem).

HTH,

EDIT : PS : note that you can obtain directly a relevant polynomial by :

sage: Q2 = P.polynomial(base_ring=GF(101))
sage: Q2
y^3 + x^2 - x*y
sage: Q2.parent()
Multivariate Polynomial Ring in x, y over Finite Field of size 101

but the notations are becoming extremely confusing, since :

sage: x.parent()
Symbolic Ring

As far as I know, Sage has no built-in way to substitute an indeterminate for another in a multivariate polynomial, so working (temporarily) in PolynomialRing(GF(101), ["x", "y", "u", "v"]) is a dead end.

Of course, if you don't have to denote the individual indeterminates and work on them at the individual level, you can get away with working only with polynomials :

sage: P
y^3 + x^2 - x*y
sage: T1 = P.polynomial(base_ring=GF(101))
sage: T2 = (x^3-y^2).polynomial(base_ring=GF(101))
sage: T1+T2
x^3 + y^3 + x^2 - x*y - y^2
sage: (T1+T2).parent()
Multivariate Polynomial Ring in x, y over Finite Field of size 101

Again, you might confuse your readers with such pranks.

EDIT : clarified the definition of a polynomial.

edit flag offensive delete link more

Comments

Thank you very much. We seem to have found a similar solution, which does not obviously involve replacing variables; namely, to work over a different multivariate ring S (over a field) which contains the (same) symbol 's' as a variable. So s.parent() is SR, but when s appears as a generator g of an ideal defined over S, g.parent() is S, e.g. Multivariate Polynomial Ring in x_1_2_1, x_1_2_2, x_1_2_3, x_1_3_1, x_1_3_2, x_1_4_1, x_1_4_2, x_2_3_1, x_2_3_2, x_2_4_1, x_2_4_2, x_3_4_1, x_3_4_2, s over Finite Field of size 101. So I guess symbols can be overloaded..

anne gravatar imageanne ( 2021-03-23 02:55:37 +0200 )edit

As far as understand it, they belong to different sets of names (namespaces ?).

  • In the global space names, the Python variable s points to (is bound to) some Python object recognized as a symbolic variable whose printing name is 's'.

  • The elements of m point to Python objects recognized as polynomials whose inderterminale happens to have the print name 's'.

When s appears somewhere in code, the local then the clobal space of names are searched for the string 's'. Unless s has received a local redefinition (e. g. you might have written s= m[1][2].parent().gens()[0] somewhere in a function), the global value (which is a symbolic variable) wiil be retrieved.

This community of print names si the only common point between the symbolic variable and the indeterminate

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2021-03-23 18:58:35 +0200 )edit

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: 2021-03-16 04:53:18 +0200

Seen: 119 times

Last updated: Mar 23