Groebner - Maple Help

Home : Support : Online Help : Mathematics : Algebra : Polynomials : Groebner : Groebner/MultiplicationMatrix

Groebner

 MultiplicationMatrix
 compute multiplication matrices
 NormalSet
 compute monomial bases

 Calling Sequence NormalSet(J, tord) MultiplicationMatrix(f, ns, rv, G, tord, characteristic=p)

Parameters

 J - Groebner basis with respect to tord or a PolynomialIdeal (zero-dimensional) tord - ShortMonomialOrder f - a polynomial ns, rv - normal set (the sequence returned by NormalSet) p - (optional) characteristic

Description

 • The NormalSet command computes a monomial basis for the quotient K[x1,...,xn]/J when J is a zero-dimensional ideal. The input can be either a Groebner basis with respect to tord or a PolynomialIdeal, in which case a Groebner basis with respect to tord is computed. The output is a sequence of two elements, ns and rv.  ns is sorted list of monomials comprising a basis for the quotient as a vector space, while rv is a table which reverses ns, i.e.: rv[ns[i]] = i for i=1..nops(ns).  The purpose of rv is to allow one to assign the coefficients of a polynomial to a vector with respect to ns in linear time.
 • The number of elements in a normal set ns is equal to the number of solutions of the system over the algebraic closure of the coefficient field.
 • The MultiplicationMatrix command constructs the multiplication matrix for a polynomial f with respect to J and tord. The rows of this matrix are the normal forms of ns[i]*f written as a vector with respect to ns, and its eigenvalues include the values of the polynomial f on the variety V(J). In particular, if f = x is a variable one obtains the x-coordinates of the solution of J among the eigenvalues of the multiplication matrix. This can be used to solve a zero-dimensional polynomial system.

Examples

Example 1: A Lagrange multiplier problem

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $f≔{x}^{3}+2xyz-{z}^{2}:$
 > $g≔{x}^{2}+{y}^{2}+{z}^{2}-1:$
 > $F≔f+\mathrm{λ}g:$
 > $J≔\mathrm{convert}\left(\mathrm{VectorCalculus}[\mathrm{Gradient}]\left(F,\left[\mathrm{λ},x,y,z\right]\right),\mathrm{set}\right)$
 ${J}{:=}\left\{{2}{}{\mathrm{λ}}{}{y}{+}{2}{}{x}{}{z}{,}{2}{}{\mathrm{λ}}{}{z}{+}{2}{}{x}{}{y}{-}{2}{}{z}{,}{2}{}{\mathrm{λ}}{}{x}{+}{3}{}{{x}}^{{2}}{+}{2}{}{y}{}{z}{,}{{x}}^{{2}}{+}{{y}}^{{2}}{+}{{z}}^{{2}}{-}{1}\right\}$ (1)
 > $\mathrm{tord}≔\mathrm{tdeg}\left(\mathrm{λ},x,y,z\right)$
 ${\mathrm{tord}}{:=}{\mathrm{tdeg}}{}\left({\mathrm{λ}}{,}{x}{,}{y}{,}{z}\right)$ (2)
 > $G≔\mathrm{Basis}\left(J,\mathrm{tord}\right):$
 > $\mathrm{ns},\mathrm{rv}≔\mathrm{NormalSet}\left(G,\mathrm{tord}\right)$
 ${\mathrm{ns}}{,}{\mathrm{rv}}{:=}\left[{1}{,}{z}{,}{y}{,}{x}{,}{\mathrm{λ}}{,}{{z}}^{{2}}{,}{y}{}{z}{,}{x}{}{z}{,}{\mathrm{λ}}{}{z}{,}{{y}}^{{2}}{,}{{\mathrm{λ}}}^{{2}}{,}{{z}}^{{3}}\right]{,}{\mathrm{table}}\left(\left[{1}{=}{1}{,}{{\mathrm{λ}}}^{{2}}{=}{11}{,}{y}{}{z}{=}{7}{,}{{y}}^{{2}}{=}{10}{,}{{z}}^{{2}}{=}{6}{,}{\mathrm{λ}}{}{z}{=}{9}{,}{x}{}{z}{=}{8}{,}{\mathrm{λ}}{=}{5}{,}{y}{=}{3}{,}{{z}}^{{3}}{=}{12}{,}{z}{=}{2}{,}{x}{=}{4}\right]\right)$ (3)
 > $\mathrm{Mx}≔\mathrm{MultiplicationMatrix}\left(x,\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
 ${\mathrm{Mx}}{:=}\left[\begin{array}{c}{\mathrm{12 x 12}}{\mathrm{Matrix}}\\ {\mathrm{Data Type:}}{\mathrm{anything}}\\ {\mathrm{Storage:}}{\mathrm{sparse}}\\ {\mathrm{Order:}}{\mathrm{Fortran_order}}\end{array}\right]$ (4)
 > $\mathrm{My}≔\mathrm{MultiplicationMatrix}\left(y,\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
 ${\mathrm{My}}{:=}\left[\begin{array}{c}{\mathrm{12 x 12}}{\mathrm{Matrix}}\\ {\mathrm{Data Type:}}{\mathrm{anything}}\\ {\mathrm{Storage:}}{\mathrm{sparse}}\\ {\mathrm{Order:}}{\mathrm{Fortran_order}}\end{array}\right]$ (5)
 > $\mathrm{Mz}≔\mathrm{MultiplicationMatrix}\left(z,\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
 ${\mathrm{Mz}}{:=}\left[\begin{array}{c}{\mathrm{12 x 12}}{\mathrm{Matrix}}\\ {\mathrm{Data Type:}}{\mathrm{anything}}\\ {\mathrm{Storage:}}{\mathrm{sparse}}\\ {\mathrm{Order:}}{\mathrm{Fortran_order}}\end{array}\right]$ (6)
 > $\mathrm{Mlambda}≔\mathrm{MultiplicationMatrix}\left(\mathrm{λ},\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
 ${\mathrm{Mlambda}}{:=}\left[\begin{array}{c}{\mathrm{12 x 12}}{\mathrm{Matrix}}\\ {\mathrm{Data Type:}}{\mathrm{anything}}\\ {\mathrm{Storage:}}{\mathrm{sparse}}\\ {\mathrm{Order:}}{\mathrm{Fortran_order}}\end{array}\right]$ (7)

Verify that the matrices commute

 > $\mathrm{LinearAlgebra}[\mathrm{Norm}]\left(\mathrm{Mx}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{My}-\mathrm{My}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{Mx},\mathrm{∞}\right)$
 ${0}$ (8)

Example 2: A geometric intersection problem

 > $\mathrm{f_1}≔3{\mathrm{x_1}}^{2}\mathrm{x_2}+9{\mathrm{x_1}}^{2}+2\mathrm{x_1}\mathrm{x_2}+5\mathrm{x_1}+\mathrm{x_2}-3:$
 > $\mathrm{f_2}≔2{\mathrm{x_1}}^{3}\mathrm{x_2}+6{\mathrm{x_1}}^{3}-2{\mathrm{x_1}}^{2}-\mathrm{x_1}\mathrm{x_2}-3\mathrm{x_1}-\mathrm{x_2}+3:$
 > $\mathrm{f_3}≔{\mathrm{x_1}}^{3}\mathrm{x_2}+3{\mathrm{x_1}}^{3}+{\mathrm{x_1}}^{2}\mathrm{x_2}+2{\mathrm{x_1}}^{2}:$
 > $G≔\mathrm{Basis}\left(\left[\mathrm{f_1},\mathrm{f_2},\mathrm{f_3}\right],\mathrm{tdeg}\left(\mathrm{x_1},\mathrm{x_2}\right)\right)$
 ${G}{:=}\left[{2}{}{{\mathrm{x_2}}}^{{2}}{-}{8}{}{\mathrm{x_1}}{-}{5}{}{\mathrm{x_2}}{-}{3}{,}{\mathrm{x_1}}{}{\mathrm{x_2}}{+}{\mathrm{x_1}}{-}{\mathrm{x_2}}{+}{3}{,}{2}{}{{\mathrm{x_1}}}^{{2}}{-}{3}{}{\mathrm{x_1}}{+}{2}{}{\mathrm{x_2}}{-}{6}\right]$ (9)
 > $\mathrm{ns},\mathrm{rv}≔\mathrm{NormalSet}\left(G,\mathrm{tdeg}\left(\mathrm{x_1},\mathrm{x_2}\right)\right)$
 ${\mathrm{ns}}{,}{\mathrm{rv}}{:=}\left[{1}{,}{\mathrm{x_2}}{,}{\mathrm{x_1}}\right]{,}{\mathrm{table}}\left(\left[{1}{=}{1}{,}{\mathrm{x_2}}{=}{2}{,}{\mathrm{x_1}}{=}{3}\right]\right)$ (10)
 > $\mathrm{M1}≔\mathrm{MultiplicationMatrix}\left(\mathrm{x_1},\mathrm{ns},\mathrm{rv},G,\mathrm{tdeg}\left(\mathrm{x_1},\mathrm{x_2}\right)\right)$
 ${\mathrm{M1}}{:=}\left[\begin{array}{ccc}{0}& {0}& {1}\\ {-}{3}& {1}& {-}{1}\\ {3}& {-}{1}& \frac{{3}}{{2}}\end{array}\right]$ (11)
 > $\mathrm{M2}≔\mathrm{MultiplicationMatrix}\left(\mathrm{x_2},\mathrm{ns},\mathrm{rv},G,\mathrm{tdeg}\left(\mathrm{x_1},\mathrm{x_2}\right)\right)$
 ${\mathrm{M2}}{:=}\left[\begin{array}{ccc}{0}& {1}& {0}\\ \frac{{3}}{{2}}& \frac{{5}}{{2}}& {4}\\ {-}{3}& {1}& {-}{1}\end{array}\right]$ (12)
 > $\mathrm{M1}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{M2}-\mathrm{M1}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{M2}$
 $\left[\begin{array}{rrr}{0}& {0}& {0}\\ {0}& {0}& {0}\\ {0}& {0}& {0}\end{array}\right]$ (13)

Read the roots of the system from the eigenvalues of the multiplication matrices M1, M2

 > $\mathrm{LinearAlgebra}[\mathrm{Eigenvectors}]\left(\mathrm{M1}\right)$
 $\left[\begin{array}{c}\frac{{5}}{{4}}{+}\frac{{1}}{{4}}{}\sqrt{{65}}\\ \frac{{5}}{{4}}{-}\frac{{1}}{{4}}{}\sqrt{{65}}\\ {0}\end{array}\right]{,}\left[\begin{array}{ccc}\frac{{1}}{\frac{{5}}{{4}}{+}\frac{{1}}{{4}}{}\sqrt{{65}}}& \frac{{1}}{\frac{{5}}{{4}}{-}\frac{{1}}{{4}}{}\sqrt{{65}}}& \frac{{1}}{{3}}\\ {-}\frac{{2}}{{5}}{}\frac{{-}\frac{{5}}{{4}}{+}\frac{{3}}{{4}}{}\sqrt{{65}}}{\frac{{1}}{{4}}{+}\frac{{1}}{{4}}{}\sqrt{{65}}}& {-}\frac{{2}}{{5}}{}\frac{{-}\frac{{5}}{{4}}{-}\frac{{3}}{{4}}{}\sqrt{{65}}}{\frac{{1}}{{4}}{-}\frac{{1}}{{4}}{}\sqrt{{65}}}& {1}\\ {1}& {1}& {0}\end{array}\right]$ (14)
 > $\mathrm{LinearAlgebra}[\mathrm{Eigenvectors}]\left(\mathrm{M2}\right)$
 $\left[\begin{array}{c}{3}\\ {-}\frac{{3}}{{4}}{+}\frac{{1}}{{4}}{}\sqrt{{65}}\\ {-}\frac{{3}}{{4}}{-}\frac{{1}}{{4}}{}\sqrt{{65}}\end{array}\right]{,}\left[\begin{array}{ccc}\frac{{1}}{{3}}& \frac{{14}}{\left({-}\frac{{25}}{{2}}{+}\frac{{1}}{{2}}{}\sqrt{{65}}\right){}\left({-}\frac{{3}}{{4}}{+}\frac{{1}}{{4}}{}\sqrt{{65}}\right)}& \frac{{14}}{\left({-}\frac{{25}}{{2}}{-}\frac{{1}}{{2}}{}\sqrt{{65}}\right){}\left({-}\frac{{3}}{{4}}{-}\frac{{1}}{{4}}{}\sqrt{{65}}\right)}\\ {1}& \frac{{14}}{{-}\frac{{25}}{{2}}{+}\frac{{1}}{{2}}{}\sqrt{{65}}}& \frac{{14}}{{-}\frac{{25}}{{2}}{-}\frac{{1}}{{2}}{}\sqrt{{65}}}\\ {0}& {1}& {1}\end{array}\right]$ (15)

Example 3: A celestial mechanics problem. System S4 (Newtonian planar 4-body problem with equal masses)

 > $\mathrm{e1}≔-2{p}^{3}+2{p}^{3}{\mathrm{φ}}^{3}-4{\mathrm{φ}}^{3}s{p}^{2}+5{\mathrm{φ}}^{3}{s}^{3}p-{\mathrm{φ}}^{3}{s}^{5}:$
 > $\mathrm{e2}≔-2s{p}^{3}-2{\mathrm{φ}}^{3}{s}^{2}+{\mathrm{φ}}^{3}{s}^{4}-3{\mathrm{φ}}^{3}{s}^{2}p+2{\mathrm{φ}}^{3}p:$
 > $\mathrm{e3}≔-2{s}^{2}+{s}^{4}-4{s}^{2}p+{\mathrm{φ}}^{2}+1+4p:$
 > $G≔\mathrm{Basis}\left(\left[\mathrm{e1},\mathrm{e2},\mathrm{e3}\right],\mathrm{tdeg}\left(s,p,\mathrm{φ}\right)\right):$
 > $\mathrm{ns},\mathrm{rv}≔\mathrm{NormalSet}\left(G,\mathrm{tdeg}\left(p,s,\mathrm{φ}\right)\right):$
 > $\mathrm{Mphi}≔\mathrm{MultiplicationMatrix}\left(\mathrm{φ},\mathrm{ns},\mathrm{rv},G,\mathrm{tdeg}\left(p,s,\mathrm{φ}\right)\right)$
 ${\mathrm{Mphi}}{:=}\left[\begin{array}{c}{\mathrm{99 x 99}}{\mathrm{Matrix}}\\ {\mathrm{Data Type:}}{\mathrm{anything}}\\ {\mathrm{Storage:}}{\mathrm{sparse}}\\ {\mathrm{Order:}}{\mathrm{Fortran_order}}\end{array}\right]$ (16)
 > $\mathrm{P37}≔\mathrm{sort}\left(\mathrm{factor}\left(\mathrm{LinearAlgebra}[\mathrm{CharacteristicPolynomial}]\left(\mathrm{Mphi},\mathrm{φ}\right)\right)\right)$
 ${\mathrm{P37}}{:=}\left({{\mathrm{φ}}}^{{2}}{-}{3}\right){}\left({{\mathrm{φ}}}^{{37}}{-}{61}{}{{\mathrm{φ}}}^{{34}}{+}{336}{}{{\mathrm{φ}}}^{{33}}{-}{240}{}{{\mathrm{φ}}}^{{32}}{+}{2052}{}{{\mathrm{φ}}}^{{31}}{-}{12120}{}{{\mathrm{φ}}}^{{30}}{+}{8400}{}{{\mathrm{φ}}}^{{29}}{-}{30456}{}{{\mathrm{φ}}}^{{28}}{+}{175113}{}{{\mathrm{φ}}}^{{27}}{-}{88548}{}{{\mathrm{φ}}}^{{26}}{+}{241040}{}{{\mathrm{φ}}}^{{25}}{-}{1364385}{}{{\mathrm{φ}}}^{{24}}{+}{338994}{}{{\mathrm{φ}}}^{{23}}{-}{1081984}{}{{\mathrm{φ}}}^{{22}}{+}{6241506}{}{{\mathrm{φ}}}^{{21}}{+}{642162}{}{{\mathrm{φ}}}^{{20}}{+}{2319507}{}{{\mathrm{φ}}}^{{19}}{-}{15790278}{}{{\mathrm{φ}}}^{{18}}{-}{12287376}{}{{\mathrm{φ}}}^{{17}}{+}{1386909}{}{{\mathrm{φ}}}^{{16}}{+}{11212992}{}{{\mathrm{φ}}}^{{15}}{+}{55894536}{}{{\mathrm{φ}}}^{{14}}{-}{19889496}{}{{\mathrm{φ}}}^{{13}}{+}{53738964}{}{{\mathrm{φ}}}^{{12}}{-}{128353329}{}{{\mathrm{φ}}}^{{11}}{+}{44215308}{}{{\mathrm{φ}}}^{{10}}{-}{172452240}{}{{\mathrm{φ}}}^{{9}}{+}{160917273}{}{{\mathrm{φ}}}^{{8}}{-}{42764598}{}{{\mathrm{φ}}}^{{7}}{+}{217615248}{}{{\mathrm{φ}}}^{{6}}{-}{115440795}{}{{\mathrm{φ}}}^{{5}}{+}{17124210}{}{{\mathrm{φ}}}^{{4}}{-}{139060395}{}{{\mathrm{φ}}}^{{3}}{+}{39858075}{}{{\mathrm{φ}}}^{{2}}{+}{39858075}\right){}{\left({{\mathrm{φ}}}^{{2}}{+}{1}\right)}^{{6}}{}{{\mathrm{φ}}}^{{48}}$ (17)

The minimal polynomial of Mphi is part of the plex Groebner basis of [e1,e2,e3] and P37 is a multiple of it.

 > $L≔\mathrm{Groebner}[\mathrm{Basis}]\left(\left[\mathrm{e1},\mathrm{e2},\mathrm{e3}\right],\mathrm{plex}\left(p,s,\mathrm{φ}\right)\right):$
 > $\mathrm{normal}\left(\frac{\mathrm{P37}}{{L}_{1}}\right)$
 ${{\mathrm{φ}}}^{{41}}{}{\left({{\mathrm{φ}}}^{{2}}{+}{1}\right)}^{{3}}$ (18)

References

 Corless, Robert M. "Groebner Bases and Matrix Eigenproblems." SIGSAM Bulletin (Communications in Computer Algebra), Vol. 30, No. 4, Issue 118, (December 1996): 26-32.
 Cox, D.; Little, J.; and O'Shea, D. Using Algebraic Geometry. Springer-Verlag, 1998