Try our Free Online Math Solver!

Polynomials
Roots
Lemma 3. Let a be a root of f ∈F[x]. Then (x − a) divides f(x).
Proof.
Write
f = q(x − a) + r
where deg(r) < 1. But then r must be 0, done.
Lemma 4. Any nonzero polynomial f ∈F[x] has at
most deg(f) many roots.
Proof.
Use the last lemma and induction on the degree.
Decomposition
So if deg(f) = n and f has n roots we decompose f completely into linear terms:
Of course, there may be fewer roots, even over a rich field such as R: f =
x^2 + 2 has no
roots.
This problem can be fixed by enlarging R to the field of complex numbers C (the
socalled
algebraic completion of R).
More Roots
Note that over arbitrary rings more roots may well exist.
For example over R = Z_{15} the equation x^2 − 4 = 0 has four roots: {2, 7, 8, 13}.
But of course
Exercise 6. Using the Chinese Remainder Theorem explain why there are
four roots in
the example above. Can you generalize?
PointValue Represenation
The fact that a nonzero polynomial of degree n can have at most n roots can
be used to
show that the interpolating polynomial
is unique: suppose g is another interpolating polynomial so that g(a_{i}) = b_{i}.
Then f − g has n + 1 roots and so is identically zero.
Hence we have an alternative representation for polynomials: we can give a
list of
pointvalue pairs rather than a list of coefficients.
To the naked eye this proposal may seem absurd: why bother with a
representation that
is clearly more complicated? As we well see, there are occasions when
pointvalue is
computationally superior to coefficient list .
Suppose we have two univariate polynomials f and g of degree bound n.
Using the brute force algorithm (i.e., literally implementing the definition
of multiplication
in
we
can compute the product
ring operations.
Now suppose we are dealing with real polynomials . There is a bizarre way to
speed up
multiplication:
• Convert f and g into pointvalue representation where the
support points are carefully chosen.
• Multiply the values pointwise to get h.
• Convert h back to coefficient representation.
FFT
It may seem absurd to spend all the effort to convert between coefficient
representation
and pointvalue representation. Surprisingly, it turns out that the conversions
can be
handled in
(n log n) steps using a technique called Fast Fourier Transform.
But the pointwise multiplication is linear in n, so the whole algorithm is just (n log n).
Theorem 2. Two real polynomials of degree bound n can be multiplied in
(n log n)
steps.
Take a look at CLR for details.
Vandermonde Matrices
Here is another look at conversions between coefficient and pointvalue
representation,
i.e., between evaluation and interpolating.
Definition 7. Define the n by n Vandermonde matrix by
Lemma 5.
Evaluation versus Interpolation
It follows that the Vandermonde matrix is invertible iff all the x_{i}
are distinct. Now
consider a polynomial
To evaluate f at points we can use matrixbyvector multiplication:
But given the values we can obtain the coefficient vector by
Implicit Representation
Recall our alternative way of defining polynomials: formal expressions
involving ring
elements and the variables using operations plus and times .
We have used this implicit representation in several places already, without
any protest
from the audience.
• The expressions
encountered
in the root decomposition.
• The description of the determinant of a Vandermonde
matrix
• Using interpolation and evaluation to retrieve the secret in
Shamir’s method.
So?
More precisely , we could consider polynomials to be arbitrary expressions
built from
• the variables x_{1}, . . . , x_{n},
• elements in the ground ring,
• addition , subtraction and multiplication.
Obviously we can recover the explicit polynomial (i.e. the coefficient list)
from these
explicit representations.
Example 1. Polynomial expands to
We just have to expand (multiply out) to get the “classical form”.
What exactly is meant by “expanding” a polynomial?
Expanding Polynomials
We want to bring a multivariate polynomial
into normal form. First
we apply rewrite rules to push multiplication to the bottom of the tree until we
have a
sum of products :
Then we collect terms with the same monomial and adjust the coefficent.
Some terms may cancel here (we don’t keep monomials with coefficent 0).
Computationally it is probably best to first sort the terms (rather than
trying to do pattern
matching at a distance).
The problem is that it may take exponential time to perform the expansion:
there may be
exponentially many terms in the actual polynomial.
Polynomial Identities
A task one encounters frequently in symbolic computation is to check whether
two
polynomials are equivalent, i.e., whether an equation between polynomials
holds in the sense that for all
Definition 8. Two polynomials
are equivalent if for all
In particular f is identically zero if
and 0 are equivalent.
In other words, two polynomials are equivalent iff b
Notation:
Zero Testing
Note that the polynomial identity can be rewritten as
Problem:
How can we check whether a multivariate polynomial
is identically zero?
Note: The polynomial may not be given in normal form, but as in the example
in a much
shorter, parenthesized form. We want a method that is reasonably fast without
having to
expand out the polynomial first.
Using Roots
Assume that the ground ring is a field F.
Suppose f has degree d. As we have seen, in the univariate case there are at
most d
roots and d roots determine the polynomial (except for a multiplicative
constant).
So we could simply check if the polynomial vanishes at, say, a = 0, 1, 2, . .
. , d: f will
vanish on all d + 1 points iff it is identically zero.
Requires only d + 1 evaluations of the polynomial (in any form).
Unfortunately, the roots for multivariate polynomials are a bit more complicated.
A Quadratic Surface
The Key Lemma
Lemma 6. Let
be of degree d and
a set of cardinality s.
Then f is not identically zero then f has at most
Proof.
The proof is by induction on n.
The set S here could be anything. For example, over Q we might choose
S = {0, 1, 2, . . . , s − 1}.
Schwartz’s Method
The main application of the lemma is to give a probabilistic algorithm to
check whether a
polynomial is zero.
Suppose f is not identically zero and has degree d.
Choose a point
uniformly at random and evaluate
Then
So by selecting S of cardinality 2d the error probability is 1/2.
Note that the number of variables plays no role in the error bound.
A Real Algorithm
To lower the error bound, we repeat the basic step k times.
// is f identically zero ?
do k times
pick a uniformly at random in Sˆn
if( f(a) != 0 )
return false;
od
return true;
Note that the answer false is always correct.
Answer true is correct with error bound " provided that
Certainty
With more work we can make sure the f really vanishes.
Corollary 1. Let
be of degree d and
a set of cardinality
s > d. If f vanishes on
then f is identically zero.
But note that for finite fields we may not be able to select a set of
cardinality higher than
d.
Recall the example over Z_{2}: in this case we can essentially only choose S =
Z_{2}, so only
degree 1 polynomials can be tackled by the lemma.
That’s fine for univariate polynomials (since any monomial x^{i} simplifies to x)
but useless
for multivariate polynomials.
Application
Recall that a perfect matching in a bipartite graph is a subset M of the
edges such that
the edges do not overlap and every vertex is incident upon one edge in M.
There is a polynomial time algorithm to check whether a perfect matching
exists, but
using Schwartz’s Lemma one obtains a faster and less complicated algorithm.
Suppose the vertices are partitioned into u_{i} and v_{i}, i = 1, . . . , n .
Define a n × n matrix A by
Note that the determinant of A is a polynomial whose nonzero terms look like
Testing Perfect Matchings
Proposition 4. The graph has a perfect matching iff
the determinant of A is not
identically zero.
Proof.
If the graph has no perfect matching then all the terms in the determinant are 0
(they all
involve at least one non edge).
But if the graph has a perfect matching it must have the
form
where π is a permutation.
But then the determinant cannot be 0 since the
corresponding monomial cannot be
cancelled out.
Prev  Next 