Computing a Basis of Polynomials (As a Vector Space)

asked 5 years ago

RaymondChou

43 ●2 ●3 ●10

updated 4 years ago

FrédéricC

5426 ●4 ●44 ●121

Hello everyone! I'm fairly new to sage, so this is probably super simple but I can't quite figure it out.

So $S_n$ acts on the multivariate polynomial ring $M = \mathbb{C} [x_1,x_2,...,x_n,y_1,y_2,...y_n]$ by simply $\sigma*x_i = x_{\sigma(i)}$ (and same for the $y_i$ 's). This turns $M$ into a $S_n$ -Module, and by extension of linearity a module of the group ring $\mathbb{C}S_n$ .

This isn't the important part however; I'm studying submodules of the thing above, and the problem right now is I have a bunch of polynomials (hundreds) of considerable length, but I want a minimal generating set (only additively). Is there a command that does this quickly without having to convert everything into a giant $(n+1)^{n+1}$ -dimensional vector space?

Thanks so much in advance!

Comments

I ended up spending the weekend implementing it (with my caveman programming skills), so it's not the most elegant thing in the world...but if anyone wants to use what I have, please feel free to contact me!

RaymondChou ( 5 years ago )

add a comment

answered 5 years ago

mwageringel
691 ●10 ●23

One way to do this in Sage is to compute an echolonization of the coefficient matrix of the polynomials:

sage: R.<x1,x2,y1,y2> = QQ[]
sage: s = Sequence([x1^2, x2^2, x1^2+x1*x2+x2^2, x1^2-x1*x2, x1*y1+x1^3, y1^2+y1*y2+y2^2])
sage: C, m = s.coefficient_matrix(); C, m
(
                           [ x1^3]
                           [ x1^2]
[ 0  1  0  0  0  0  0  0]  [x1*x2]
[ 0  0  0  1  0  0  0  0]  [ x2^2]
[ 0  1  1  1  0  0  0  0]  [x1*y1]
[ 0  1 -1  0  0  0  0  0]  [ y1^2]
[ 1  0  0  0  1  0  0  0]  [y1*y2]
[ 0  0  0  0  0  1  1  1], [ y2^2]
)
sage: B = C.row_space().basis_matrix(); B
[1 0 0 0 1 0 0 0]
[0 1 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 1 1 1]
sage: (B * m).list()
[x1^3 + x1*y1, x1^2, x1*x2, x2^2, y1^2 + y1*y2 + y2^2]

This does convert everything to a large vector space however, but it is only as large as necessary to encode all the monomials that occur in the sequence of polynomials.

Note that this assumes you are working over an exact field such as QQ. Over an inexact field such as ℂ, this problem is more delicate. In that case, I would start by looking at the singular value decomposition of C, but the quality of the result largly depends on the input polynomials:

U, D, V = matrix(CDF, C, sparse=False).SVD()

link

Comments

Thank you so much!

RaymondChou ( 5 years ago )

add a comment

Your Answer

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

Computing a Basis of Polynomials (As a Vector Space)

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Computing a Basis of Polynomials (As a Vector Space) savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Computing a Basis of Polynomials (As a Vector Space)