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

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?

edit retag close merge delete

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!

( 2020-01-21 17:44:17 -0600 )edit

Sort by » oldest newest most voted

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

more

Thank you so much!

( 2020-01-25 23:21:45 -0600 )edit