4.3 Standard Gr¨obner basis methods for solving systems of polynomial equations . 28
4.3.3 Solving systems of equations via eigenvalues end eigenvectors
−7 3,1
3 )
, (8
3,−4 3
)
. (4.42)
Note that the polynomial equation (4.41) is equivalent to the polynomial equation 9y4 − 18y3−13y2+ 30y−8 = 0obtained from the lexicographic Gr¨obner basis (4.32) computed in Example 4.
4.3.3 Solving systems of equations via eigenvalues end eigenvectors The third method for solving systems of polynomial equations based on Gr¨obner bases and on computations in the quotient ringA=C[x1, . . . , xn]/Itries to solve both problems of the lex-icographic Elimination Gr¨obner Basis Method presented in Section 4.3.1, i.e. the problem with large computational complexity of lexicographic Gr¨obner bases, and the problem with accumu-lating errors by backsubstitution.
The first problem is solved as in the previous Gr¨obner basis conversion method, i.e. by com-puting a Gr¨obner basis w.r.t. some other, more favorable, monomial ordering, e.g. the grevlex ordering. The second problem with accumulating errors by backsubstituting approximate solu-tions of one-variable polynomials to the remaining polynomials and solving these approximate equations, tries to solve the presented method by finding all solutions independently as eigen-values of several matrices or at once as eigeneigen-values and eigenvectors of a single matrix.
While the lexicographic Elimination Gr¨obner basis Method is related to Gaussian elimination used for solving systems of linear equations, this method will be related to the companion matrix method for solving a polynomial in one variable [9].
Let us consider the mappingTf:A→Aof the multiplication by a polynomialf ∈C[x1, . . . , xn] defined as
Tf([g]) = [f].[g] = [f g]∈A. (4.43) It can be shown thatTf is a linear mapping for whichTf =Tg ifff−g∈I.
In our case we are considering only systems with a finite number of solutions and thereforeA is a finite-dimensional vector space overC. For such a finite-dimensional vector space we can representTf :A→Aby its matrix with respect to some basisBofA.
To be precise, let B = ([b1], . . . ,[bs]) be a basis of A = C[x1, . . . , xn]/I, where bi ∈ C[x1, . . . , xn], i = 1, . . . , s. Usually a standard monomial basis (4.20)B = ([
xα(1)] , . . . , [xα(s)])
or other basis consisting only of monomials is the most useful here. Then we can rep-resent the multiplication mappingTf by representing the imageTf([bi])of every basis element [bi], i= 1. . . , s, in terms ofB= ([b1], . . . ,[bs]).
Definition 15. (Multiplication Matrix)We say that the complexs×smatrixMf := (mij)such
In this definition we follow the notation used in [39], where the imageTf([bj])corresponds to thejthcolumn of the multiplication matrix. In many papers, however, this image corresponds to the jth row and therefore the multiplication matrix is the transposed matrix M⊤f from our definition.
Having a Gr¨obner basisG, the multiplication matrix Mf w.r.t. the standard monomial basis B = ([
xα(1)] , . . . ,[
xα(s)])
is constructed by computing the remaindersxα(i)fG for all basis monomials[
xα(i)]
∈B, i= 1, . . . , s, as the following example shows.
Example 6. (Multiplication matrix)Let us consider our well known system of polynomials equations form Example 4 and 5, i.e. the system
2x2+y2+ 3y−12 = 0, (4.45)
x2−y2+x+ 3y−4 = 0.
The grevlex Gr¨obner basisG of the idealI defined by these two polynomials consists of the following two polynomials To compute the multiplication matrixMxfor multiplication by[x]inA, it is sufficient to compute
1. Tx([xy]) = [
Then the multiplication matrixMxhas the form
Similarly, the multiplication matrixMy for multiplication byyinAcan be constructed by com-puting
Therefore the multiplication matrixMy has the form
My =
The multiplication matrix (4.44) has several nice properties which can be used to solve sys-tems of polynomial equations (4.1). The first one is described by the following theorem.
Theorem 4. LetI be a zero-dimensional ideal and letMf be a matrix of the linear map Tf : A → Aof multiplication by a polynomialf ∈C[x1, . . . , xn]inA =C[x1, . . . , xn]/I. Then λ∈Cis an eigenvalue of the matrixMf iffλis a value of the functionf onV(I).
Proof. The proof of this theorem can be found in [39].
This theorem says that the eigenvalues of the multiplication matrices Mxi, wherexi are our variables, correspond to thexi-coordinates of the points ofV(I), i.e. to the roots of the gener-ator of the elimination idealI ∩C[xi]. This means that the solutions of the whole system of polynomial equations (4.1) can be found as eigenvalues ofnmatricesMxi, i= 1, . . . , n.
Example 7. (Companion matrix)Let’s first consider an example of one polynomial in one variablex. Let this polynomial have the form
f =
∑s i=1
cixi, (4.50)
whereciare some coefficients fromCand letcs= 1, i.e. the polynomialfis a monic polynomial.
In this case the Gr¨obner basis consists only of this polynomialf, i.e.G={f}and the monomial basisB of the quotient ringA=C[x]/I has the form
This is the well known Frobenius companion matrix [9] whose eigenvalues give solutions of the polynomial equationf(x) = 0.
Example 8. (Gr¨obner basis eigenvalue method)In the case of the system of polynomial equa-tions (4.45) from Example 6, we have
Mx=
Similarly the eigenvalues ofMy
My =
One has to try all4×4 = 16pairs to check which are the solutions. In this case, we obtain four solutions of the system (4.45), i.e.
(−2,1),(1,2),
Constructingnmultiplication matrices and computing their eigenvalues is, however, not al-ways the most efficient way, especially when the number of variablesnis larger. First we need to compute eigenvalues of a large number of matrices. Secondly, we need to combine obtained solutions for particular variablesxk, i.e. obtained values of thexk-coordinates of the points of
V(I), to complete solutions of the whole system. This requires to perform a large number of polynomial evaluations which may be quite time-consuming (in the worst caseNn, whereN is the number of solutions of the system (4.1).
To avoid this problem, the second nice property of multiplication matricesMf is usually used.
This property shows how the eigenvectors of multiplication matrices can be used to find solutions for all coordinates of the points ofV(I), i.e. to all variables.
Let us assume that the idealI =⟨f1, . . . , fm⟩is a radical ideal, i.e.I =√
I[39]. This means that the algebraA=C[x1, . . . , xn]/Ihas dimensionN, whereN is the number of solutions of our system (4.1), i.e. the number of points inV(I). Therefore, the monomial basisB (4.20) of the algebraAconsists ofN cosets
B =
Then the left eigenvectors ofMf are related to the solutions of the system of polynomial equa-tions (4.1), i.e. to the points ofV(I), in the following way:
Theorem 5. Letf ∈ C[x1, . . . , xn]be a polynomial such that the values f(p)are pairwise distinct forp ∈V(I). Then the left eigenvectors of the multiplication matrixMf have the form v=β(
pα(1), . . . ,pα(N))
forβ ∈C, β ̸= 0, and the left eigenspaces have dimension one.
Proof. Let us first take[ xα(j)]
∈B. Then from the definition (4.44) of the multiplication matrix Mf, we have for someh∈I. This together with (4.57) give us
fxα(j)=
Since for zero-dimensional idealI we have[1]∈B, it implies that(
is a left eigenvector ofMf corresponding to the eigenvalue f(p). Moreover, we are assuming that the valuesf(p) are distinct forp ∈ V(I). Therefore the multiplication matrixMf has N distinct eigenvalues and the corresponding 1-dimensional eigenspaces.
The proof of this theorem can be found also in [39].
This theorem can be used to find solutions of the system of polynomial equations (4.1) in the following way.
Letvbe a left eigenvector of the multiplication matrixMf. From Theorem 5 we know that this vector has the form assuming that we have the eigenvectorv(4.62).
If[xi]∈Bfor all variablesxi, i= 1, . . . , n, then it is easy. In this caseβaiis a coordinate of vfor alli= 1, . . . , n. Since[1] ∈B, β is also a coordinate ofv. Therefore thexi-coordinate of the solution of our system, i.e. the solution forxi, can be found as the ratio of coordinates of v, i.e.ai= βaβi.
If for somei,[xi]∈/ B, then the way of obtaining the solution forxiis not so straightforward;
however, it can be proved that we can again obtain solutions for allxi,i = 1, . . . , n, from the coordinates of the left eigenvectorsvofMf, see e.g. [39].
Example 9. (Gr¨obner basis eigenvector method)For the system of polynomial equations (4.45) from Example 6 we can take one from the two multiplication matrices, e.g.Mx
Mx=
and find solutions of the system (4.45) by computing left eigenvectors ofMx(4.63) or right eigen-vectors ofM⊤x. In this way we obtain four eigenvectors
In this case the first coordinate of these eigenvectors corresponds to[xy]∈B, the second co-ordinate to[x], the third to[y]and the fourth to[1]. Therefore, solutions forxcan be obtained by dividing the second coordinate of the eigenvector by its fourth coordinate, and the corresponding solutions foryby dividing the third coordinate of the eigenvector by the fourth coordinate.
This means that from the first eigenvector (4.64) we obtainx= −12 =−2andy= 11 = 1. In this way we obtain all four solutions of the system (4.45)
(−2,1),(1,2),
The method for solving systems of polynomial equations based on eigenvalues and eigenvec-tors of multiplication matrices was proposed in [8] and is discussed in several works [109, 110, 128, 129, 130].
Note that this method does not necessarily need to construct Gr¨obner bases. All what we need is to have representatives of cosets [f bi], for all [bi] ∈ B and some polynomial f ∈ C[x1, . . . , xn]. However, the usual way is to use the remainders of f bi on the division by a Gr¨obner basis as these representatives. Then the whole method for solving systems of polyno-mial equations based on Gr¨obner bases and multiplication matrices is described by the following algorithm.
Algorithm 5Gr¨obner basis Eigenvalue Method
1. Compute a Gr¨obner basisGw.r.t. some monomial ordering (usually grevlex ordering).
2. Compute the standard monomial basis B = {
, create the multiplication matrixMf forTf. 5. Use eigenvalues and eigenvectors ofMf to find solutions of the input system.