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.

$\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\mathrm{\lambda }y+2xz\,2\mathrm{\lambda }z+2xy-2z\,2\mathrm{\lambda }x+3x^2+2yz\,x^2+y^2+z^2-1\right\}$

$\mathrm{tord}≔\mathrm{tdeg}\left(\mathrm{\lambda }\,x\,y\,z\right)$

$\mathrm{tord}≔\mathrm{tdeg}\left(\mathrm{\lambda }\,x\,y\,z\right)$

$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\,yz\,xz\,\mathrm{\lambda }z\,y^2\,{\mathrm{\lambda }}^2\,z^3\right],table\left(\left[\mathrm{\lambda }=5\,1=1\,z=2\,xz=8\,\mathrm{\lambda }z=9\,x=4\,yz=7\,z^2=6\,y^2=10\,z^3=12\,{\mathrm{\lambda }}^2=11\,y=3\right]\right)$

$\mathrm{Mx}≔\mathrm{MultiplicationMatrix}\left(x\,\mathrm{ns}\,\mathrm{rv}\,G\,\mathrm{tord}\right)$

$\mathrm{My}≔\mathrm{MultiplicationMatrix}\left(y\,\mathrm{ns}\,\mathrm{rv}\,G\,\mathrm{tord}\right)$

$\mathrm{Mz}≔\mathrm{MultiplicationMatrix}\left(z\,\mathrm{ns}\,\mathrm{rv}\,G\,\mathrm{tord}\right)$

$\mathrm{Mlambda}≔\mathrm{MultiplicationMatrix}\left(\mathrm{\lambda }\,\mathrm{ns}\,\mathrm{rv}\,G\,\mathrm{tord}\right)$

$\mathrm{LinearAlgebra}\left[\mathrm{Norm}\right]\left(\mathrm{Mx}·\mathrm{My}-\mathrm{My}·\mathrm{Mx}\,\mathrm{\infty }\right)$

$0$

$\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]$

$\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)$

$\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\\ \mathrm{-3}& 1& \mathrm{-1}\\ 3& \mathrm{-1}& \frac{3}{2}\end{array}\right]$

$\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\\ \mathrm{-3}& 1& \mathrm{-1}\end{array}\right]$

$\mathrm{M1}·\mathrm{M2}-\mathrm{M1}·\mathrm{M2}$

$\left[\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right]$

$\mathrm{LinearAlgebra}\left[\mathrm{Eigenvectors}\right]\left(\mathrm{M1}\right)$

$\left[\begin{array}{c}\frac{5}{4}+\frac{\sqrt{65}}{4}\\ \frac{5}{4}-\frac{\sqrt{65}}{4}\\ 0\end{array}\right],\left[\begin{array}{ccc}\frac{1}{\frac{5}{4}+\frac{\sqrt{65}}{4}}& \frac{1}{\frac{5}{4}-\frac{\sqrt{65}}{4}}& \frac{1}{3}\\ -\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)}& 1\\ 1& 1& 0\end{array}\right]$

$\mathrm{LinearAlgebra}\left[\mathrm{Eigenvectors}\right]\left(\mathrm{M2}\right)$

$\left[\begin{array}{c}3\\ -\frac{3}{4}+\frac{\sqrt{65}}{4}\\ -\frac{3}{4}-\frac{\sqrt{65}}{4}\end{array}\right],\left[\begin{array}{ccc}\frac{1}{3}& \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)}\\ 1& \frac{14}{-\frac{25}{2}+\frac{\sqrt{65}}{2}}& \frac{14}{-\frac{25}{2}-\frac{\sqrt{65}}{2}}\\ 0& 1& 1\end{array}\right]$

$\mathrm{e1}≔-2p^3+2p^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}≔-2s^2+s^4-4s^{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)$

$\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}$

$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$

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