Structural Operations on Polynomials

Structural operations on polynomials.

Here is a polynomial in one variable:

Expand expands out products and powers, writing the polynomial as a simple sum of terms:

Factor performs complete factoring of the polynomial:

FactorTerms pulls out the overall numerical factor fromt:

There are several ways to write any polynomial. The functionsExpand,FactorTerms, andFactor give three common ways.Expand writes a polynomial as a simple sum of terms, with all products expanded out.FactorTerms pulls out common factors from each term.Factor does complete factoring, writing the polynomial as a product of terms, each of as low degree as possible.

When you have a polynomial in more than one variable, you can put the polynomial in different forms by essentially choosing different variables to be "dominant".Collect[poly,x] takes a polynomial in several variables and rewrites it as a sum of terms containing different powers of the "dominant variable"x.

Here is a polynomial in two variables:

Collect reorganizes the polynomial so thatx is the "dominant variable":

If you specify a list of variables,Collect will effectively write the expression as a polynomial in these variables:

Controlling polynomial expansion.

This avoids expanding parts which do not containx:

This avoids expanding parts which do not contain objects matchingb[_]:

Expanding powers and logarithms.

The Wolfram System does not automatically expand out expressions of the form(ab)^c except whenc is an integer. In general it is only correct to do this expansion ifa andb are positive reals. Nevertheless, the functionPowerExpand does the expansion, effectively assuming thata andb are indeed positive reals.

The Wolfram System does not automatically expand out this expression:

PowerExpand does the expansion, effectively assuming thatx andy are positive reals:

Log is not automatically expanded out:

PowerExpand does the expansion:

PowerExpand returns a result correct for the given assumptions:

Ways of collecting terms.

Here is an expression involving various functionsf:

This collects terms that matchf[_]:

This appliesFactor to each coefficient obtained:

Horner form.

Horner form is a way of arranging a polynomial that allows numerical values to be computed more efficiently by minimizing the number of multiplications.

This gives the Horner form of a polynomial:

Finding the Structure of a Polynomial

Finding the structure of polynomials written in expanded form.

Here is a polynomial in two variables:

This is the polynomial in expanded form:

PolynomialQ reports thatt is a polynomial inx:

This expression, however, is not a polynomial inx:

Variables gives a list of the variables in the polynomialt:

This gives the maximum exponent with whichx appears in the polynomialt. For a polynomial in one variable,Exponent gives the degree of the polynomial:

Coefficient[poly,expr] gives the total coefficient with whichexpr appears inpoly. In this case, the result is a sum of two terms:

This is equivalent toCoefficient[t,x^2]:

This picks out the coefficient of in t:

CoefficientList gives a list of the coefficients of each power of, starting with:

For multivariate polynomials,CoefficientList gives an array of the coefficients for each power of each variable:

CoefficientRules includes only those monomials that have nonzero coefficients:

It is important to notice that the functions in this tutorial will often work even on polynomials that are not explicitly given in expanded form.

Many of the functions also work on expressions that are not strictly polynomials.

Without giving specific integer values toa,b, andc, this expression cannot strictly be considered a polynomial:

Exponent[expr,x] still gives the maximum exponent ofx inexpr, but here has to write the result in symbolic form:

Polynomial Orderings

The leading term of a polynomial can be chosen in many different ways. For multivariate polynomials, sorting by the total degree of the monomials is often useful.

Different representations of polynomials.

Here is a polynomial in three variables:

This is the list of the monomials:

This is the list of the monomials represented as exponent vectors and coefficients:

The first vector corresponds to:

FromCoefficientRules constructs the original polynomial from the list of rules and variables:

If the second argument toMonomialList orCoefficientRules is omitted, the variables are taken in the order in which they are returned by the functionVariables.

The list of the variables is not always sorted:

Now the first vector corresponds to:

By default, the monomials are sorted lexicographically and given in the decreasing order. In the previous example,{5,4,1} (corresponding to) is taken to precede{5,3,2} (corresponding to) by the second element.

An order is described by defining how two vectors of exponents and are sorted. For the lexicographic order,

.

An order can also be described by giving a weight matrix. In that case the exponent vectors are multiplied by the weight matrix and the results are sorted lexicographically, also in the decreasing order. The matrices for different orderings are given as follows.

Weight matrices corresponding to different orderings.

For functions such asGroebnerBasis andPolynomialReduce, it is necessary that the order be well-founded, which ensures that any decreasing sequence of elements is finite (the elements being the vectors of non-negative exponents). In order for that condition to hold, the first nonzero value in each column of the weight matrix must be positive.

The default sorting used for polynomial terms in an expression corresponds to the negative lexicographic ordering with variables sorted in the reversed order. This is commonly known as reverse lexicographic ordering.

This is the internal representation of a polynomial. The arguments ofPlus andTimes are sorted on evaluation:

This is the sorted list of terms:

This is the reverse lexicographic order in variables{x,y,z}:

This is the same order specified by a weight matrix:

The result is identical to the automatically sorted list of terms inpoly:

TraditionalForm tries to arrange the terms in an order close to the lexicographic ordering.

The polynomial displayed inTraditionalForm:

This uses advanced typesetting capabilities to obtain the list of terms in the same order as they appear in theTraditionalForm output:

The result agrees with the list of the monomials given in the default (lexicographic) order:

The optionParameterVariables tellsTraditionalForm which variables should be excluded from the ordering.

By default, the list of independent variables is assumed to be{a,b,x}:

Herex is assumed to be the only variable:

One can obtain additional orderings from the six orderings used inMonomialList simply by reversing the resulting list. This is effectively equivalent to negating the exponent vectors. In a commutative setting, one can also obtain other orderings by reversing the order of the variables.

This diagram illustrates the relations between various orderings. Red lines indicate reversing the list of variables and blue lines indicate negating the power vectors.

Structural Operations on Rational Expressions

For ordinary polynomials,Factor andExpand give the most important forms. For rational expressions, there are many different forms that can be useful.

Different kinds of expansion for rational expressions.

Here is a rational expression:

ExpandNumerator writes the numerator of each term in expanded form:

Expand expands the numerator of each term, and divides all the terms by the appropriate denominators:

ExpandDenominator expands out the denominator of each term:

ExpandAll does all possible expansions in the numerator and denominator of each term:

Controlling expansion.

This avoids expanding the term which does not containz:

Structural operations on rational expressions.

Here is a rational expression:

Together puts all terms over a common denominator:

You can useFactor to factor the numerator and denominator of the resulting expression:

Apart writes the expression as a sum of terms, with each term having as simple a denominator as possible:

Cancel cancels any common factors between numerators and denominators:

Factor first puts all terms over a common denominator, then factors the result:

In mathematical terms,Apart decomposes a rational expression into "partial fractions".

In expressions with several variables, you can useApart[expr,var] to do partial fraction decompositions with respect to different variables.

Here is a rational expression in two variables:

This gives the partial fraction decomposition with respect tox:

Here is the partial fraction decomposition with respect toy:

Algebraic Operations on Polynomials

For many kinds of practical calculations, the only operations you will need to perform on polynomials are essentially structural ones.

If you do more advanced algebra with polynomials, however, you will have to use the algebraic operations discussed in this tutorial.

You should realize that most of the operations discussed in this tutorial work only on ordinary polynomials, with integer exponents and rational‐number coefficients for each term.

Reduction of polynomials.

Given two polynomials and, one can always uniquely write, where the degree of is less than the degree of.PolynomialQuotient gives the quotient, andPolynomialRemainder gives the remainder.

This gives the remainder from dividing by:

Here is the quotient of and, with the remainder dropped:

This gives back the original expression:

Here the result depends on whether the polynomials are considered to be inx ory:

PolynomialMod is essentially the analog for polynomials of the functionMod for integers. When the modulusm is an integer,PolynomialMod[poly,m] simply reduces each coefficient inpoly modulo the integerm. Ifm is a polynomial, thenPolynomialMod[poly,m] effectively tries to get a polynomial with as low a degree as possible by subtracting frompoly appropriate multiplesqm ofm. The multiplierq can itself be a polynomial, but its degree is always less than the degree ofpoly.PolynomialMod yields a final polynomial whose degree and leading coefficient are both as small as possible.

This reduces modulo. The result is simply the remainder from dividing the polynomials:

In this case,PolynomialMod andPolynomialRemainder do not give the same result:

The main difference betweenPolynomialMod andPolynomialRemainder is that while the former works simply by multiplying and subtracting polynomials, the latter uses division in getting its results. In addition,PolynomialMod allows reduction by several moduli at the same time. A typical case is reduction modulo both a polynomial and an integer.

This reduces the polynomial modulo both and:

PolynomialGCD[poly₁,poly₂] finds the highest degree polynomial that divides thepoly_i exactly. It gives the analog for polynomials of the integer functionGCD.

PolynomialGCD gives the greatest common divisor of the two polynomials:

PolynomialExtendedGCD gives the extended greatest common divisor of the two polynomials:

The returned polynomials and can be used to represent the GCD in terms of the original polynomials:

The functionResultant[poly₁,poly₂,x] is used in a number of classical algebraic algorithms. The resultant of two polynomials and, both with leading coefficient one, is given by the product of all the differences between the roots of the polynomials. It turns out that for any pair of polynomials, the resultant is always a polynomial in their coefficients. By looking at when the resultant is zero, you can tell for what values of their parameters two polynomials have a common root. Two polynomials with leading coefficient one have common roots if exactly the first elements in the listSubresultants[poly₁,poly₂,x] are zero.

Here is the resultant with respect toy of two polynomials inx andy. The original polynomials have a common root iny only for values ofx at which the resultant vanishes:

The functionDiscriminant[poly,x] is the product of the squares of the differences of its roots. It can be used to determine whether the polynomial has any repeated roots. The discriminant is equal to the resultant of the polynomial and its derivative, up to a factor independent of the variable.

This polynomial has a repeated root, so its discriminant vanishes:

This polynomial has distinct roots, so its discriminant is nonzero:

Gröbner bases appear in many modern algebraic algorithms and applications. The functionGroebnerBasis[{poly₁,poly₂,…},{x₁,x₂,…}] takes a set of polynomials, and reduces this set to a canonical form from which many properties can conveniently be deduced. An important feature is that the set of polynomials obtained fromGroebnerBasis always has exactly the same collection of common roots as the original set.

The is effectively redundant, and so does not appear in the Gröbner basis:

The polynomial1 has no roots, showing that the original polynomials have no common roots:

The polynomials are effectively unwound here, and can now be seen to have exactly five common roots:

PolynomialReduce[poly,{p₁,p₂,…},{x₁,x₂,…}] yields a list of polynomials with the property that is minimal and is exactlypoly.

This writes in terms of and, leaving a remainder that depends only on:

Functions for factoring polynomials.

Factor,FactorTerms, andFactorSquareFree perform various degrees of factoring on polynomials.Factor does full factoring over the integers.FactorTerms extracts the "content" of the polynomial.FactorSquareFree pulls out any multiple factors that appear.

Here is a polynomial, in expanded form:

FactorTerms pulls out only the factor of 2 that does not depend onx:

FactorSquareFree factors out the 2 and the term, but leaves the rest unfactored:

Factor does full factoring, recovering the original form:

Particularly when you write programs that work with polynomials, you will often find it convenient to pick out pieces of polynomials in a standard form. The functionFactorList gives a list of all the factors of a polynomial, together with their exponents. The first element of the list is always the overall numerical factor for the polynomial.

The form thatFactorList returns is the analog for polynomials of the form produced byFactorInteger for integers.

Here is a list of the factors of the polynomial in the previous set of examples. Each element of the list gives the factor, together with its exponent:

Factoring polynomials with complex coefficients.

Factor and related functions usually handle only polynomials with ordinary integer or rational‐number coefficients. If you set the optionGaussianIntegers->True, however, thenFactor will allow polynomials with coefficients that are complex numbers with rational real and imaginary parts. This often allows more extensive factorization to be performed.

This polynomial is irreducible when only ordinary integers are allowed:

When Gaussian integer coefficients are allowed, the polynomial factors:

Irreducibility testing.

A polynomial is irreducible over a fieldF if it cannot be represented as a product of two nonconstant polynomials with coefficients inF.

This polynomial is irreducible over the rationals:

Over the Gaussian rationals, the polynomial is reducible:

By default, algebraic numbers are treated as independent variables:

Over the rationals extended bySqrt[2], the polynomial is reducible:

Cyclotomic polynomials.

Cyclotomic polynomials arise as "elementary polynomials" in various algebraic algorithms. The cyclotomic polynomials are defined by, where runs over all positive integers less than that are relatively prime to.

This is the cyclotomic polynomial:

appears in the factors of:

Decomposing polynomials.

Factorization is one important way of breaking down polynomials into simpler parts. Another, quite different, way isdecomposition. When you factor a polynomial, you write it as a product of polynomials. Decomposing a polynomial consists of writing it as acomposition of polynomials of the form.

Here is a simple example ofDecompose. The original polynomial can be written as the polynomial, where is the polynomial:

Here are two polynomial functions:

This gives the composition of the two functions:

Decompose recovers the original functions:

Decompose[poly,x] is set up to give a list of polynomials inx, which, if composed, reproduce the original polynomial. The original polynomial can contain variables other thanx, but the sequence of polynomials thatDecompose produces are all intended to be considered as functions ofx.

Unlike factoring, the decomposition of polynomials is not completely unique. For example, the two sets of polynomials and, related by and give the same result on composition, so that. The Wolfram Language follows the convention of absorbing any constant terms into the first polynomial in the list produced byDecompose.

Generating interpolating polynomials.

This yields a quadratic polynomial which goes through the specified three points:

Whenx is0, the polynomial has value 2:

Polynomials Modulo Primes

The Wolfram Language can work with polynomials whose coefficients are in the finite field of integers modulo a prime.

Functions for manipulating polynomials over finite fields.

Here is an ordinary polynomial:

This reduces the coefficients modulo 2:

Here are the factors of the resulting polynomial over the integers:

If you work modulo 2, further factoring becomes possible:

Symmetric Polynomials

Asymmetric polynomial in variables is a polynomial that is invariant under arbitrary permutations of. Polynomials

are calledelementary symmetric polynomials in variables.

The fundamental theorem of symmetric polynomials says that every symmetric polynomial in can be represented as a polynomial in elementary symmetric polynomials in.

When the ordering of variables is fixed, an arbitrary polynomial can be uniquely represented as a sum of a symmetric polynomial, called the symmetric part of, and a remainder that does not contain descending monomials. A monomial is called descending iff.

Functions for symmetric polynomial computations.

Here is the elementary symmetric polynomial of degree three in four variables:

This writes the polynomial in terms of elementary symmetric polynomials. The input polynomial is symmetric, so the remainder is zero:

Here the elementary symmetric polynomials in the symmetric part are replaced with variables. The polynomial is not symmetric, so the remainder is not zero:

SymmetricReduction can be applied to polynomials with symbolic coefficients:

Polynomials over Algebraic Number Fields

Functions likeFactor usually assume that all coefficients in the polynomials they produce must involve only rational numbers. But by setting the optionExtension you can extend the domain of coefficients that will be allowed.

Factoring polynomials over algebraic number fields.

Allowing only rational number coefficients, this polynomial cannot be factored:

With coefficients that can involve, the polynomial can now be factored:

The polynomial can also be factored if one allows coefficients involving:

GaussianIntegers->True is equivalent toExtension->Sqrt[-1]:

If one allows coefficients that involve both and the polynomial can be factored completely:

Expand gives the original polynomial back again:

Factoring polynomials with algebraic number coefficients.

Here is a polynomial with a coefficient involving:

By default,Factor will not factor this polynomial:

But now the field of coefficients is extended by including, and the polynomial is factored:

Other polynomial functions work much likeFactor. By default, they treat algebraic number coefficients just like independent symbolic variables. But with the optionExtension->Automatic they perform operations on these coefficients.

By default,Cancel does not reduce these polynomials:

But now it does:

By default,PolynomialLCM pulls out no common factors:

But now it does:

Irreducibility testing.

A polynomial is irreducible over a fieldF if it cannot be represented as a product of two nonconstant polynomials with coefficients inF.

By default, algebraic numbers are treated as independent variables:

Over the rationals extended bySqrt[2], the polynomial is reducible:

This polynomial is irreducible over the rationals:

Over the rationals extended bySqrt[3], the polynomial is reducible:

This polynomial is irreducible over the field of all complex numbers:

Trigonometric Expressions

Functions for manipulating trigonometric expressions.

This expands out a trigonometric expression:

This factors the expression:

And this reduces the expression to a form that is linear in the trigonometric functions:

TrigExpand works on hyperbolic as well as circular functions:

TrigReduce reproduces the original form again:

The Wolfram System automatically uses functions likeTan whenever it can:

WithTrigFactorList, however, you can see the parts of functions likeTan:

Converting to and from exponentials.

TrigToExp writes trigonometric functions in terms of exponentials:

TrigToExp also works with hyperbolic functions:

ExpToTrig does the reverse, getting rid of explicit complex numbers whenever possible:

ExpToTrig deals with hyperbolic as well as circular functions:

You can also useExpToTrig on purely numerical expressions:

Expressions Involving Complex Variables

The Wolfram Language usually pays no attention to whether variables likex stand for real or complex numbers. Sometimes, however, you may want to make transformations which are appropriate only if particular variables are assumed to be either real or complex.

The functionComplexExpand expands out algebraic and trigonometric expressions, making definite assumptions about the variables that appear.

Expanding complex expressions.

This expands the expression, assuming thatx andy are both real:

In this case,a is assumed to be real, butx is assumed to be complex, and is broken into explicit real and imaginary parts:

With several complex variables, you quickly get quite complicated results:

There are several ways to write a complex variablez in terms of real parameters. As above, for example,z can be written in the "Cartesian form"Re[z]+IIm[z]. But it can equally well be written in the "polar form"Abs[z]Exp[IArg[z]].

The optionTargetFunctions inComplexExpand allows you to specify how complex variables should be written.TargetFunctions can be set to a list of functions from the set{Re,Im,Abs,Arg,Conjugate,Sign}.ComplexExpand will try to give results in terms of whichever of these functions you request. The default is typically to give results in terms ofRe andIm.

This gives an expansion in Cartesian form:

Here is an expansion in polar form:

Here is another form of expansion:

Logical and Piecewise Functions

Nested logical and piecewise functions can be expanded out much like nested arithmetic functions. You can do this usingLogicalExpand andPiecewiseExpand.

Expanding out logical and piecewise functions.

LogicalExpand puts logical expressions into a standarddisjunctive normal form (DNF), consisting of an OR of ANDs.

By default, the Wolfram Language leaves this expression unchanged:

LogicalExpand expands this into an OR of ANDs:

LogicalExpand works on all logical functions, always converting them into a standard OR of ANDs form. Sometimes the results are inevitably quite large.

Xor can be expressed as an OR of ANDs:

Any collection of nested conditionals can always in effect be flattened into apiecewise normal form consisting of a singlePiecewise object. You can do this in the Wolfram Language usingPiecewiseExpand.

By default, the Wolfram Language leaves this expression unchanged:

PiecewiseExpand flattens it into a singlePiecewise object:

Functions likeMax andAbs, as well asClip andUnitStep, implicitly involve conditionals, and combinations of them can again be reduced to a singlePiecewise object usingPiecewiseExpand.

This gives a result as a singlePiecewise object:

Withx assumed real, this can also be written as aPiecewise object:

Functions likeFloor,Mod, andFractionalPart can also be expressed in terms ofPiecewise objects, though in principle they can involve an infinite number of cases.

Without a bound onx, this would yield an infinite number of cases:

The Wolfram Language by default limits the number of cases that the Wolfram Language will explicitly generate in the expansion of any single piecewise function such asFloor at any stage in a computation. You can change this limit by resetting the value of$MaxPiecewiseCases.

Simplification

Simplifying expressions.

The Wolfram Language does not automatically simplify an algebraic expression like this:

Simplify performs the simplification:

Simplify performs standard algebraic and trigonometric simplifications:

It does not, however, do more sophisticated transformations that involve, for example, special functions:

FullSimplify does perform such transformations:

Controlling simplification.

Here is an expression involving trigonometric functions and square roots:

By default,FullSimplify will try to simplify everything:

This makesFullSimplify avoid simplifying the square roots:

Further control of simplification.

In bothSimplify andFullSimplify there is always an issue of what counts as the "simplest" form of an expression. You can use the optionComplexityFunction->c to provide a function to determine this. The function will be applied to each candidate form of the expression, and the one that gives the smallest numerical value will be considered simplest.

With its default definition of simplicity,Simplify leaves this unchanged:

This now tries to minimize the number of elements in the expression:

Using Assumptions

The Wolfram Language normally makes as few assumptions as possible about the objects you ask it to manipulate. This means that the results it gives are as general as possible. But sometimes these results are considerably more complicated than they would be if more assumptions were made.

Doing operations with assumptions.

Simplify by default does essentially nothing with this expression:

The reason is that its value is quite different for different choices ofx:

With the assumptionx>0,Simplify can immediately reduce the expression to 0:

Without making assumptions aboutx andy, nothing can be done:

Ifx andy are both assumed positive, the log can be expanded:

By applyingSimplify andFullSimplify with appropriate assumptions to equations and inequalities, you can in effect establish a vast range of theorems.

Without making assumptions aboutx, the truth or falsity of this equation cannot be determined:

NowSimplify can prove that the equation is true:

This establishes the standard result that the arithmetic mean is larger than the geometric one:

This proves that lies in the range for all positive arguments:

Simplify andFullSimplify always try to find the simplest forms of expressions. Sometimes, however, you may just want the Wolfram Language to follow its ordinary evaluation process, but with certain assumptions made. You can do this usingRefine. The way it works is thatRefine[expr,assum] performs the same transformations as the Wolfram Language would perform automatically if the variables inexpr were replaced by numerical expressions satisfying the assumptionsassum.

There is no simpler form thatSimplify can find:

Refine just evaluatesLog[x] as it would for any explicit negative number x:

An important class of assumptions is those which assert that some object is an element of a particular domain. You can set up such assumptions usingx∈dom, where the∈ character can be entered asEscelEsc or∖[Element].

Asserting that objects are elements of domains.

This confirms that is an element of the domain of real numbers:

These numbers are all elements of the domain of algebraic numbers:

The Wolfram Language knows that is not an algebraic number:

Current mathematics has not established whether is an algebraic number or not:

This represents the assertion that the symbolx is an element of the domain of real numbers:

Domains supported by the Wolfram Language.

If is assumed to be an integer, is zero:

This establishes the theorem if is assumed to be a real number:

If you say that a variable satisfies an inequality, the Wolfram Language will automatically assume that it is real:

By usingSimplify,FullSimplify, andFunctionExpand with assumptions, you can access many of the Wolfram Language's vast collection of mathematical facts.

This uses the periodicity of the tangent function:

The assumptionk/2∈Integers implies thatk must be even:

The Wolfram Language knows that for positive:

FullSimplify accesses knowledge about special functions:

The Wolfram Language knows about discrete mathematics and number theory as well as continuous mathematics.

This uses Wilson's theorem to simplify the result:

This uses the multiplicative property of the Euler phi function:

In something likeSimplify[expr,assum] orRefine[expr,assum], you explicitly give the assumptions you want to use. But sometimes you may want to specify one set of assumptions to use in a whole collection of operations. You can do this by usingAssuming.

Specifying assumptions with larger scopes.

This tellsSimplify to use the default assumptionx>0:

This combines the two assumptions given:

Functions likeSimplify andRefine take the optionAssumptions, which specifies what default assumptions they should use. By default, the setting for this option isAssumptions:>$Assumptions. The wayAssuming then works is to assign a local value to$Assumptions, much as inBlock.

In addition toSimplify andRefine, a number of other functions takeAssumptions options, and thus can have assumptions specified for them byAssuming. Examples areFunctionExpand,Integrate,Limit,Series, andLaplaceTransform.

The assumption is automatically used inIntegrate: