 Groebner - Maple Programming 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{\lambda }g:$
 > $J≔\mathrm{convert}\left(\mathrm{VectorCalculus}\left[\mathrm{Gradient}\right]\left(F,\left[\mathrm{\lambda },x,y,z\right]\right),\mathrm{set}\right)$
 ${J}{≔}\left\{{2}{}{y}{}{\mathrm{\lambda }}{+}{2}{}{x}{}{z}{,}{2}{}{z}{}{\mathrm{\lambda }}{+}{2}{}{x}{}{y}{-}{2}{}{z}{,}{2}{}{x}{}{\mathrm{\lambda }}{+}{3}{}{{x}}^{{2}}{+}{2}{}{y}{}{z}{,}{{x}}^{{2}}{+}{{y}}^{{2}}{+}{{z}}^{{2}}{-}{1}\right\}$ (1)
 > $\mathrm{tord}≔\mathrm{tdeg}\left(\mathrm{\lambda },x,y,z\right)$
 ${\mathrm{tord}}{≔}{\mathrm{tdeg}}{}\left({\mathrm{\lambda }}{,}{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{\lambda }}{,}{{z}}^{{2}}{,}{y}{}{z}{,}{x}{}{z}{,}{z}{}{\mathrm{\lambda }}{,}{{y}}^{{2}}{,}{{\mathrm{\lambda }}}^{{2}}{,}{{z}}^{{3}}\right]{,}{table}{}\left(\left[{1}{=}{1}{,}{z}{}{\mathrm{\lambda }}{=}{9}{,}{x}{=}{4}{,}{z}{=}{2}{,}{{z}}^{{3}}{=}{12}{,}{{z}}^{{2}}{=}{6}{,}{y}{}{z}{=}{7}{,}{y}{=}{3}{,}{{\mathrm{\lambda }}}^{{2}}{=}{11}{,}{{y}}^{{2}}{=}{10}{,}{\mathrm{\lambda }}{=}{5}{,}{x}{}{z}{=}{8}\right]\right)$ (3)
 > $\mathrm{Mx}≔\mathrm{MultiplicationMatrix}\left(x,\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
  (4)
 > $\mathrm{My}≔\mathrm{MultiplicationMatrix}\left(y,\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
  (5)
 > $\mathrm{Mz}≔\mathrm{MultiplicationMatrix}\left(z,\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
  (6)
 > $\mathrm{Mlambda}≔\mathrm{MultiplicationMatrix}\left(\mathrm{\lambda },\mathrm{ns},\mathrm{rv},G,\mathrm{tord}\right)$
  (7)

Verify that the matrices commute

 > $\mathrm{LinearAlgebra}\left[\mathrm{Norm}\right]\left(\mathrm{Mx}·\mathrm{My}-\mathrm{My}·\mathrm{Mx},\mathrm{\infty }\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]{,}{table}{}\left(\left[{1}{=}{1}{,}{\mathrm{x_1}}{=}{3}{,}{\mathrm{x_2}}{=}{2}\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}·\mathrm{M2}-\mathrm{M1}·\mathrm{M2}$
 $\left[\begin{array}{ccc}{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}\left[\mathrm{Eigenvectors}\right]\left(\mathrm{M1}\right)$
 $\left[\begin{array}{c}{0}\\ \frac{{5}}{{4}}{+}\frac{\sqrt{{65}}}{{4}}\\ \frac{{5}}{{4}}{-}\frac{\sqrt{{65}}}{{4}}\end{array}\right]{,}\left[\begin{array}{ccc}\frac{{1}}{{3}}& \frac{{1}}{\frac{{5}}{{4}}{+}\frac{\sqrt{{65}}}{{4}}}& \frac{{1}}{\frac{{5}}{{4}}{-}\frac{\sqrt{{65}}}{{4}}}\\ {1}& {-}\frac{{2}{}\left({-}\frac{{5}}{{4}}{+}\frac{{3}{}\sqrt{{65}}}{{4}}\right)}{{5}{}\left(\frac{{1}}{{4}}{+}\frac{\sqrt{{65}}}{{4}}\right)}& {-}\frac{{2}{}\left({-}\frac{{5}}{{4}}{-}\frac{{3}{}\sqrt{{65}}}{{4}}\right)}{{5}{}\left(\frac{{1}}{{4}}{-}\frac{\sqrt{{65}}}{{4}}\right)}\\ {0}& {1}& {1}\end{array}\right]$ (14)
 > $\mathrm{LinearAlgebra}\left[\mathrm{Eigenvectors}\right]\left(\mathrm{M2}\right)$
 $\left[\begin{array}{c}{-}\frac{{3}}{{4}}{+}\frac{\sqrt{{65}}}{{4}}\\ {-}\frac{{3}}{{4}}{-}\frac{\sqrt{{65}}}{{4}}\\ {3}\end{array}\right]{,}\left[\begin{array}{ccc}\frac{{14}}{\left({-}\frac{{25}}{{2}}{+}\frac{\sqrt{{65}}}{{2}}\right){}\left({-}\frac{{3}}{{4}}{+}\frac{\sqrt{{65}}}{{4}}\right)}& \frac{{14}}{\left({-}\frac{{25}}{{2}}{-}\frac{\sqrt{{65}}}{{2}}\right){}\left({-}\frac{{3}}{{4}}{-}\frac{\sqrt{{65}}}{{4}}\right)}& \frac{{1}}{{3}}\\ \frac{{14}}{{-}\frac{{25}}{{2}}{+}\frac{\sqrt{{65}}}{{2}}}& \frac{{14}}{{-}\frac{{25}}{{2}}{-}\frac{\sqrt{{65}}}{{2}}}& {1}\\ {1}& {1}& {0}\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{\phi }}^{3}-4{\mathrm{\phi }}^{3}s{p}^{2}+5{\mathrm{\phi }}^{3}{s}^{3}p-{\mathrm{\phi }}^{3}{s}^{5}:$
 > $\mathrm{e2}≔-2s{p}^{3}-2{\mathrm{\phi }}^{3}{s}^{2}+{\mathrm{\phi }}^{3}{s}^{4}-3{\mathrm{\phi }}^{3}{s}^{2}p+2{\mathrm{\phi }}^{3}p:$
 > $\mathrm{e3}≔-2{s}^{2}+{s}^{4}-4{s}^{2}p+{\mathrm{\phi }}^{2}+1+4p:$
 > $G≔\mathrm{Basis}\left(\left[\mathrm{e1},\mathrm{e2},\mathrm{e3}\right],\mathrm{tdeg}\left(s,p,\mathrm{\phi }\right)\right):$
 > $\mathrm{ns},\mathrm{rv}≔\mathrm{NormalSet}\left(G,\mathrm{tdeg}\left(p,s,\mathrm{\phi }\right)\right):$
 > $\mathrm{Mphi}≔\mathrm{MultiplicationMatrix}\left(\mathrm{\phi },\mathrm{ns},\mathrm{rv},G,\mathrm{tdeg}\left(p,s,\mathrm{\phi }\right)\right)$
  (16)
 > $\mathrm{P37}≔\mathrm{sort}\left(\mathrm{factor}\left(\mathrm{LinearAlgebra}\left[\mathrm{CharacteristicPolynomial}\right]\left(\mathrm{Mphi},\mathrm{\phi }\right)\right)\right)$
 ${\mathrm{P37}}{≔}\left({{\mathrm{\phi }}}^{{2}}{-}{3}\right){}\left({{\mathrm{\phi }}}^{{37}}{-}{61}{}{{\mathrm{\phi }}}^{{34}}{+}{336}{}{{\mathrm{\phi }}}^{{33}}{-}{240}{}{{\mathrm{\phi }}}^{{32}}{+}{2052}{}{{\mathrm{\phi }}}^{{31}}{-}{12120}{}{{\mathrm{\phi }}}^{{30}}{+}{8400}{}{{\mathrm{\phi }}}^{{29}}{-}{30456}{}{{\mathrm{\phi }}}^{{28}}{+}{175113}{}{{\mathrm{\phi }}}^{{27}}{-}{88548}{}{{\mathrm{\phi }}}^{{26}}{+}{241040}{}{{\mathrm{\phi }}}^{{25}}{-}{1364385}{}{{\mathrm{\phi }}}^{{24}}{+}{338994}{}{{\mathrm{\phi }}}^{{23}}{-}{1081984}{}{{\mathrm{\phi }}}^{{22}}{+}{6241506}{}{{\mathrm{\phi }}}^{{21}}{+}{642162}{}{{\mathrm{\phi }}}^{{20}}{+}{2319507}{}{{\mathrm{\phi }}}^{{19}}{-}{15790278}{}{{\mathrm{\phi }}}^{{18}}{-}{12287376}{}{{\mathrm{\phi }}}^{{17}}{+}{1386909}{}{{\mathrm{\phi }}}^{{16}}{+}{11212992}{}{{\mathrm{\phi }}}^{{15}}{+}{55894536}{}{{\mathrm{\phi }}}^{{14}}{-}{19889496}{}{{\mathrm{\phi }}}^{{13}}{+}{53738964}{}{{\mathrm{\phi }}}^{{12}}{-}{128353329}{}{{\mathrm{\phi }}}^{{11}}{+}{44215308}{}{{\mathrm{\phi }}}^{{10}}{-}{172452240}{}{{\mathrm{\phi }}}^{{9}}{+}{160917273}{}{{\mathrm{\phi }}}^{{8}}{-}{42764598}{}{{\mathrm{\phi }}}^{{7}}{+}{217615248}{}{{\mathrm{\phi }}}^{{6}}{-}{115440795}{}{{\mathrm{\phi }}}^{{5}}{+}{17124210}{}{{\mathrm{\phi }}}^{{4}}{-}{139060395}{}{{\mathrm{\phi }}}^{{3}}{+}{39858075}{}{{\mathrm{\phi }}}^{{2}}{+}{39858075}\right){}{\left({{\mathrm{\phi }}}^{{2}}{+}{1}\right)}^{{6}}{}{{\mathrm{\phi }}}^{{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}\left[\mathrm{Basis}\right]\left(\left[\mathrm{e1},\mathrm{e2},\mathrm{e3}\right],\mathrm{plex}\left(p,s,\mathrm{\phi }\right)\right):$
 > $\mathrm{normal}\left(\frac{\mathrm{P37}}{L\left[1\right]}\right)$
 ${{\mathrm{\phi }}}^{{41}}{}{\left({{\mathrm{\phi }}}^{{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