\documentclass{article}
\title{An algorithm for elimination for sets of polynomial equations}
\author{John Nixon [http://www.bluesky-home.co.uk]}
\date{September 2005}
\begin{document}
\maketitle
\section{Notes on prerequisites for single variable polynomials}
\subsection{Factors,roots,monicity}
Every polynomial $A$ with the coefficient of the highest power of the variable equal to 1
(a monic polynomial)
is the product of factors $z-z_{i}$ for each root $z_{i}$. If the factor appears $k$
times
$z_{i}$ it is said to have multiplicity $k$. $A(z_{i})=0$.
When any polynomial $A$ is divided by the coefficient of its term with highest power,
the result
is a monic polynomial $\rm{mon}(A)$, the monic form of $A$, with the same set of roots
and multiplicities as $A$.
\subsection{Greatest Common Divisor(GCD)}
The GCD of a pair of polynomials $A$ and $B$ is the product of the common factors of $A$ and $B$.
If a factor appears $k_{1}$ times in $A$ and $k_{2}$ times in $B$, in
the ${\rm GCD}(A,B)$ it appears $min(k_{1},k_{2})$ times (i.e. the smaller of $k_{1}$
and $k_{2}$).
${\rm GCD}(A,B)$ divides exactly into both $A$ and $B$, but no polynomial
of degree greater than the degree of ${\rm GCD}(A,B)$ that contains ${\rm GCD}(A,B)$
as a factor, itself divides
both $A$ and $B$ exactly. This is the meaning of Greatest Common Divisor (GCD).
GCD can also be applied
to sets of polynomials because it is obviously associative: ${\rm GCD}( {\rm GCD}(A,B), C)
={\rm GCD}(A, {\rm GCD}(B,C))$.
This polynomial is defined as ${\rm GCD}(A,B,C)$ etc. Similarly ${\rm GCD}(A,B,C,...)$
is defined. This is all analogous to the properties of GCD for positive integers.
This actually
defines the GCD to within a constant factor. To make the GCD unique I will choose it
to be monic.
\subsection{``Square-free'' reduction}
If a root of polynomial $A$ has multiplicity $k>1$, this root is also a root of the first
derivative of $A$
(i.e. $A'$)
with multiplicity $k-1$, hence the root is also a root of ${\rm GCD}(A,A')$
with multiplicity
$k-1$.
Hence $A/{\rm GCD}(A,A')$ has the same root with multiplicity 1. Thus
$A/{\rm GCD}(A,A')$
(i.e. the square-free reduction
of $A$) has the same set of distinct roots as $A$, but each has a multiplicity of 1.
\subsection{Polynomial division}
If $A_{n}$ and $B_{m}$ are polynomials of degree given by their subscripts,
and $A_{n}$ (the dividand) is divided by $B_{m}$ (the divisor) where $m\leq n$ the result is
a quotient polynomial $Q_{n-m}$ of degree $n-m$ and a remainder
polynomial $R$ of degree $< m$. i.e. $A_{n}=B_{m}Q_{n-m}+R$. This calculation can be done
by polynomial long division. In this calculation, the leading term of $A_{n}$ is
divided by the leading term of $B_{m}$ to give the quotient $Q$. Then $A^{*}=A_{n}-B_{m}Q$
is computed that now takes the place of $A_{n}$.
This calculation is repeated until the degree of $A^{*} 2$}
For each of these pairs of polynomials,
the third of the original polynomials is introduced and the algorithm is applied again to the
two polynomials involving $z_{1}$. The result is a set of triplets of polynomials, two of each
triplet not involving $z_{1}$ and the other involving $z_{1}$. After all the polynomials have
been introduced in the same way the result is a set of $p$-tuples of polynomials, all but one
of each $p$-tuple not involving $z_{1}$, but some of the other variables may be eliminated
"accidentally".
Finally, the whole procedure should be applied eliminating $z_{2}$, $z_{3}\ldots$ in the same way
that $z_{1}$ was eliminated. For elimination of $z_{j}$, the $z_{1}$ ...$z_{j-1}$ dependent polynomials
in each $p$-tuple are ignored. The final result should be a set of $p$-tuples of
polynomials with
the $j$-th polynomial in each $p$-tuple having $z_{1}$ ... $z_{j-1}$ eliminated.
Because the degrees of the polynomials with respect to the variable being eliminated are checked
at each step, there is no chance of accidental independence one of the equations on this
variable when it is supposed to be present. So, for each set of values of the variables
$z_{j}$ ,
$z_{j+1}$,... satisfying the subset of a final $p$-tuple of polynomial equations that
consists of the
$i$th for all $i\geq j$ for any fixed $j$, the $j-1$th member of the $p$-tuple has at least one solution
for $z_{j-1}$. Hence every such $p$-tuple of polynomial equations has a non-empty solution set,
justifying the term ``solution''.
One such $p$-tuple is the form that the equations are naively expected to take
using an elimination
strategy. In general several such ``solutions'' exist.
The variables and equations can be taken in different orders giving equivalent results. Must these
be identical if the same set of variables is eliminated?
To obtain explicit solutions in the case where the number of variables ($k$) equals the
number of
unknowns ($p$) using this method, after substitution at each step, $p$ separate single variable
polynomial equations have to be solved in sequence.
\section{Algebraic relations}
\newtheorem{def1}{Definition}
\begin{def1}
\label{def:1}The relation between the complex variables $z_{1}$,$z_{2}$,...$z_{l}$ is
defined to be algebraic if and
only if it can be expressed,for some $k\geq 0$, as a set of $k+1$ equations, each of the form
$A_{k}(z_{1},z_{2},...z_{l+k})=0$
where the $A$'s are polynomials with respect to each of
their arguments.
\end{def1}
To convert this to explicit form requires
elimination of the variables $z_{l+1}...z_{l+k}$.
The above elimination algorithm will reduce it to the union of the solution sets of
equations of the form
$$Q_{i}(z_{1},z_{2},...z_{l})=0$$ (which could be written as a single such equation
$\prod_{i} Q_{i}=0$)
where $Q_{i}$ are also a polynomials in each of their arguments. The degrees of freedom
in the relation is $l-1$
From Definition \ref{def:1}, it is easy to show that the following operations applied to
algebraic relations give other algebraic relations (closure):
\begin{itemize}
\item Union
\item Inversion (i.e. permutations of the variables if there are $>$ 2 of them.)
\item Composition (for $\geq $2 variables this is defined by the elimination of a
specific variable from a pair of algebraic relations usually with each relation
introducing unique variables -- a special case of intersection)
\item Addition *
\item Multiplication *
\item Intersection
The intersection of a pair of solution sets corresponding to sets of $p$-tuples of
polynomials of
the type obtained from the elimination algorithm is the solution set of another such set of
$p$-tuples of polynomials but with usually one fewer degrees of freedom (the number of
variables -
number of equations).
\end{itemize}
* For the two-variable case, if the relations $R_{1}(w_{1},z)$ and $R_{2}(w_{2},z)$ are regarded as multi-valued functions
$w_{1}(z)$ and $w_{2}(z)$
respectively, the relation corresponding to all possible values of $w_{1}(z)+w_{2}(z)$ for each
$z$ is defined as
$R_{1} +R_{2}$. Likewise for multiplication.
In general to define $+$ and $\times$, the dependent variable must be specified.
\end{document}