*** Quotient rings ***
----------------------------------------------
-- 
----------------------------------------------
-- Gröbner bases techniques enable computations in {\em quotient} polynomial rings (algebras). 
-- In particular, if the algebra is finite-dimensional as a vector space such computations boiil down to linear algebra. 
--
-- * Defining a quotient ring
--
-- * Multiplication table
--
-- * Solving systems of equations via eigenvalues

----------------------------------------------
-- Defining a quotient ring
----------------------------------------------
-- Given an ideal $I$ in a polynomial ring $R$,
k = QQ; R = k[x,y,z]; I = ideal {x^2+y^2+z^2-4, x^2+2*y^2-5, x*y*z-y} 
-- one can define the {\em quotient ring}: 
R0 = R/I; describe R0
-- The (ring) dimension of the quotient ring is $0$  
dim R0
-- iff the $k$-vector space dimension is finite. {\em Standard monomials} 
-- with respect to the monomial order (chosen for $R$) for
-- a $k$-basis for $R/I$.
B = basis R0
-- The technology behind the {\tt basis} function is simple: the basis
-- elements are exactly monomials not divisible by the generators of
-- the initial ideal of $I$,
leadTerm I
-- For a positive-dimensional quotient ring, e.g., the coordinate ring of the twisted cubic
use R; R1 = R/ideal{y-x^2, z-x^3}
-- one can not get a finite $k$-basis
dim R1
basis R1
-- but it is possible to get a part of the infinite basis given by
-- standard monomials by specifying a degree (range of degrees):
basis(3,R1)
basis(0,5,R1)

----------------------------------------------
-- Multiplication table
----------------------------------------------
-- Every element of a quotient ring is stored in its {\em normal form}, 
-- which is a linear combination of standard monomials
-- representing its coset.
use R 
f = random(2,R) 
g = random(2,R)
RtoR0 = map(R0,R) -- maps are written right-to-left
RtoR0 f
RtoR0 g
-- Note that two random quadric polynomials get rewritten in terms of standard monomials exclusively.
-- Internally this is accomplished by the polynomial division relative to a Gröbner basis.
print(f*g); RtoR0(f*g)
lift(RtoR0(f*g),R) == (f*g) % I
-- The standard basis and the multiplication table for a 0-dimensional ring
use R0; describe R0
B = flatten entries basis R0 -- a list of standard monomials
Table table(B,B,(a,b)->a*b) 
-- {\em determine} the quotient ring.

-----------------------------------------------
-- Solving systems of equations via eigenvalues
-----------------------------------------------
-- Assume $I\subset R$ is a 0-dimensional ideal, for instance, take our running example: 
print I
-- For every polynomial function $g\in R$ we can construct a multiplication matrix $M_g$ 
-- representing the operator $[f] \mapsto [gf] \in R/I$ relative to the standard basis. 
multiplicationMatrix = (g,B) -> (
    n := #B;
    matrix apply(n, i->apply(n,j->toCC coefficient(B#j,g*B#i)))
    ) 
-- Then the eigenvalues of $M_g$ are the values of the function $g$ at the points of ${\mathbb V}(I)$.
M = multiplicationMatrix(x^2+y+z,B)
eigenvalues M
-- To solve a system of polynomial equations one could compute all possible values for one of the coordinates
M = multiplicationMatrix(z,B)
eigenvalues M
-- and proceed using a back-substitution (of computed values for $z$).