PolynomialHermiteDecomposition
PolynomialHermiteDecomposition[P]
computes the Hermite decomposition of the matrix P of univariate polynomials.
PolynomialHermiteDecomposition[P,x]
computes the Hermite decomposition for a matrix of polynomials in the variable x.
Details and Options
- PolynomialHermiteDecomposition is the polynomial analog of HermiteDecomposition. It gives a canonical decomposition of a polynomial matrix as a unimodular and an upper triangular matrix.
- PolynomialHermiteDecomposition is typically used in applications similar to where one uses RowReduce with the big difference being that one is only looking for polynomial solutions and not rational function solutions.
- The Hermite decomposition is computed by doing polynomial row operations: multiply by a polynomial, permute rows and add rows. This corresponds to multiplying by a matrix
from the left, and the result is an upper triangular Hermite form 
. - The matrix
is unimodular, i.e. ![TemplateBox[{{U, (, x, )}}, Det]](Files/PolynomialHermiteDecomposition.en/4.png "TemplateBox[{{U, (, x, )}}, Det]")
is constant, so the inverse ![U^~(x)=TemplateBox[{{U, (, x, )}}, Inverse]](Files/PolynomialHermiteDecomposition.en/5.png "U^~(x)=TemplateBox[{{U, (, x, )}}, Inverse]")
is also a polynomial matrix. and the polynomial matrix 
has the decomposition 
: - The matrix
is an upper triangular polynomial matrix that is also a canonical form of 
up to multiplying each row with constants. The first nonzero entry in each row is a polynomial such that all entries above it are of strictly lower degree and all entries below it are zero. - PolynomialHermiteDecomposition takes the following options:
-
Method Automatic method to use Modulus 0 modulus to assume for integers
Examples
open all close allBasic Examples (2)
Compute the Hermite decomposition of a 2x2 matrix:
m = {{-3 - 7x, 37 - 25x}, {-6 - 14x, 26 - 25x}};{u, h} = PolynomialHermiteDecomposition[m]Expand[u.m - h]Det[u]Compute the Hermite decomposition of a 2x3 matrix of low-degree polynomials:
m = {{x ^ 3 - 11, x ^ 2 - 2x + 5, x ^ 3 - 2x ^ 2 + 3x - 7}, {x ^ 2 + 4x + 9, x ^ 2 - 19, x ^ 3 + 5x - 6}};
{u, h} = PolynomialHermiteDecomposition[m]Expand[u.m - h]Det[u]Scope (4)
The matrix can have rational coefficients:
m = {{x ^ 3 - 11 / 5, x ^ 2 / 7 - 2x + 3 / 5, 2 / 3x ^ 3 - 2x ^ 2 + 3 / 4x - 7 / 2}, {x ^ 2 + 4 / 5x + 4 / 9, x ^ 2 - 19 / 6, x ^ 3 + 5 / 3x - 6 / 7}};
{u, h} = PolynomialHermiteDecomposition[m]Check that the determinant of u is constant and check the required matrix equation:
{Det[u], Expand[u.m] == h}The matrix can have complex coefficients:
m = {{x ^ 3 - I, x ^ 2 - (2 - 3I)x + 5, (2 + I)x ^ 3 - (2 + 3I)x ^ 2 + 3x - 7 + I}, {x ^ 2 + (4 + 3I)x + 9, x ^ 2 - 19, x ^ 3 + (5 + 2I)x - 6}};
{u, h} = PolynomialHermiteDecomposition[m]Check that the determinant of u is constant and verify the required matrix equation:
{Det[u], Expand[u.m] == h}The matrix can have approximate coefficients:
m = N@{{x ^ 3 - 11 / 5, x ^ 2 / 7 - 2x + 3 / 5, 2 / 3x ^ 3 - 2x ^ 2 + 3 / 4x - 7 / 2}, {x ^ 2 + 4 / 5x + 4 / 9, x ^ 2 - 19 / 6, x ^ 3 + 5 / 3x - 6 / 7}};
{u, h} = PolynomialHermiteDecomposition[m]Check that the determinant of u is constant and check the required matrix equation to reasonable precision:
{Chop@Det[u], Chop[Expand[u.m] - h]}The matrix can have symbolic coefficients:
m = {{x ^ 3 - 11 / 5a, x ^ 2 / 7 - 2b x + 3 / 5, 2 / 3x ^ 3 - 2x ^ 2 + 3 / 4c x - 7 / 2}, {x ^ 2 + 4 / 5d x + 4 / 9, x ^ 2 - 19 / 6e, x ^ 3 + 5 / 3f x - 6 / 7}};
{u, h} = PolynomialHermiteDecomposition[m, x]Expand[u.m - h]Check that u is unimodular; in this case, it is a constant with respect to the polynomial variable x:
Det[u]Options (3)
Modulus (1)
PolynomialHermiteDecomposition can work modulo a prime:
m = {{x ^ 3 - 11, x ^ 2 - 2x + 5, x ^ 3 - 2x ^ 2 + 3x - 7}, {x ^ 2 + 4x + 9, x ^ 2 - 19, x ^ 3 + 5x - 6}};
{u, h} = PolynomialHermiteDecomposition[m, Modulus -> 19]Check that the determinant of u is constant and check the required matrix equation:
{Det[u, Modulus -> 19], Expand[u.m - h, Modulus -> 19]}Method (2)
m = {{x ^ 3 - 11, x ^ 2 - 2x + 5, x ^ 3 - 2x ^ 2 + 3x - 7}, {x ^ 2 + 4x + 9, x ^ 2 - 19, x ^ 3 + 5x - 6}};
{u, h} = PolynomialHermiteDecomposition[m]In addition to the default MethodAutomatic, one can specify Method"Direct" to use dedicated univariate polynomial algebra code:
{ud, hd} = PolynomialHermiteDecomposition[m, Method -> "Direct"]{Det[ud], Expand[ud.m - hd]}Instead set Method "GroebnerBasis" (this uses a computation of a module Gröbner basis):
{ug, hg} = PolynomialHermiteDecomposition[m, Method -> "GroebnerBasis"]{Det[ug], Expand[ug.m - hg]}This gives the same result as:
{ud - ug, hd - hg}Use different methods with a prime modulus:
m = {{x ^ 3 - 11, x ^ 2 - 2x + 5, x ^ 3 - 2x ^ 2 + 3x - 7}, {x ^ 2 + 4x + 9, x ^ 2 - 19, x ^ 3 + 5x - 6}};{ud, hd} = PolynomialHermiteDecomposition[m, Modulus -> 19, Method -> "Direct"]PolynomialHermiteDecomposition[m, Modulus -> 19, Method -> "GroebnerBasis"]Applications (2)
Polynomial Equations (1)
Create an underdetermined system using a 6×8 matrix of random quartic polynomials:
randomPoly[deg_, max_, x_] := RandomInteger[{-max, max}, deg + 1].x ^ Range[0, deg]
randomMatrix[m_, n_, deg_, max_, x_] := Table[randomPoly[deg, max, x], {m}, {n}]
SeedRandom[1111];
mat = randomMatrix[6, 8, 4, 10, x];
rhs = Flatten[randomMatrix[6, 1, 4, 10, x]];A function to find polynomial solutions to linear systems with polynomial coefficients:
solvePolynomialSystem[mat_, rhs_, x_] := Module[
{tmat = Join[{rhs}, Transpose[mat]], augmat, uu, hh, soln, len = Length[rhs]},
augmat = Join[tmat, IdentityMatrix[Length[tmat]], 2];
{uu, hh} = PolynomialHermiteDecomposition[augmat, x];
soln = SelectFirst[hh, (#[[len + 1]] =!= 0 && FreeQ[#[[len + 1]], x])&, "Missing"];
If[soln === "Missing", {}, -Drop[soln, len + 1] / soln[[len + 1]]]
]Timing[soln = solvePolynomialSystem[mat, rhs, x];]Expand[mat.soln - rhs]One can get a solution faster using LinearSolve:
Timing[soln2 = LinearSolve[mat, rhs];]But several components are rational functions rather than polynomials:
Map[PolynomialQ[#, x]&, soln2]Greatest Common Left Divisor (GCLD) (1)
One can use PolynomialHermiteDecomposition to compute left-extended GCDs of two polynomial matrices.
Construct a pair of matrices with a known nontrivial left common divisor:
m1a = {{-36 - 84x - 55x^2 - 87x^3, 3 + 90x - 67x^2 - 81x^3}, {95 - 89x - 6x^2 - 91x^3, -46 + 90x + 72x^2 - 4x^3}};
m2a = {{-95 - 29x - 56x^2 + 11x^3, -95 - 81x + 81x^2 - 89x^3}, {-9 - 48x + 68x^2 - 70x^3, -92 - 49x + 87x^2 + 64x^3}};
m3 = {{-41 + 6x + 76x^2 + 15x^3, -40 + 62x + 70x^2 + 12x^3}, {-10 - 80x + 39x^2 + 64x^3, 15 - 96x + x^2 - 45x^3}};
m1 = Expand[m3.m1a];
m2 = Expand[m3.m2a];Join these transposed and compute the Hermite decomposition:
bigmat = Join[Transpose@m1, Transpose@m2];
{u, h} = PolynomialHermiteDecomposition[bigmat, x];The GCD matrix is obtained from h:
gcd = Expand[Transpose@h[[1 ;; 2]]];Create a solver over the univariate polynomial ring:
solvePolynomialSystem[mat_, rhs_ ? VectorQ, x_] := Module[
{tmat = Join[{rhs}, Transpose[mat]], augmat, uu, hh, soln, len = Length[rhs]},
augmat = Join[tmat, IdentityMatrix[Length[tmat]], 2];
{uu, hh} = PolynomialHermiteDecomposition[augmat, x];
soln = SelectFirst[hh, (#[[len + 1]] =!= 0 && FreeQ[#[[len + 1]], x])&, "Missing"];
If[soln === "Missing", {}, -Drop[soln, len + 1] / soln[[len + 1]]]
]Use it to recover the GCD cofactors:
u11 = solvePolynomialSystem[gcd, m1[[All, 1]], x];
u12 = solvePolynomialSystem[gcd, m1[[All, 2]], x];
U1 = Transpose[{u11, u12}]u21 = solvePolynomialSystem[gcd, m2[[All, 1]], x];
u22 = solvePolynomialSystem[gcd, m2[[All, 2]], x];
U2 = Transpose[{u21, u22}]{Expand[gcd.U1 - m1], Expand[gcd.U2 - m2]}While a matrix GCD is not unique, any one is related to another by a unimodular transformation.
Construct the unimodular matrix transforming gcd to the common multiplier m3:
u1 = solvePolynomialSystem[gcd, m3[[All, 1]], x];
u2 = solvePolynomialSystem[gcd, m3[[All, 2]], x];
U = Transpose[{u1, u2}]Check that 
is unimodular and transforms gcd to m3:
{Det[U], Expand[gcd.U - m3]}Properties & Relations (3)
Compute the Hermite normal form of a matrix:
mat = {{-2324 + 12678 x + 387 x^2 - 5509 x^3 - 13092 x^4 - 13879 x^5 - 2397 x^6, 1785 - 6735 x + 14415 x^2 - 5463 x^3 + 12174 x^4 - 6734 x^5 - 1473 x^6}, {1717 - 10124 x + 2995 x^2 + 20176 x^3 + 1644 x^4 - 6577 x^5 - 1263 x^6, -720 + 4626 x - 14019 x^2 + 5060 x^3 + 6033 x^4 - 10691 x^5 - 5004 x^6}, {4255 + 1981 x - 11424 x^2 - 868 x^3 - 4781 x^4 - 4088 x^5 - 675 x^6, 815 + 8034 x + 4794 x^2 - 10062 x^3 + 4028 x^4 - 6285 x^5 + 3854 x^6}, {7575 - 993 x - 23985 x^2 - 5146 x^3 + 13877 x^4 - 25 x^5 - 567 x^6, -430 + 16507 x + 7882 x^2 - 18130 x^3 + 1243 x^4 - 2138 x^5 - 8576 x^6}};
h1 = PolynomialHermiteReduce[mat]The Hermite normal form can also be obtained from the second matrix returned by PolynomialHermiteDecomposition:
{u2, h2} = PolynomialHermiteDecomposition[mat];
h2The Hermite form of a matrix is unique only up to constant multiples of the rows:
Together[h2[[1]] / h1[[1]]]Only consider second element of second rows to avoid a division by zero:
Together[h2[[2, 2]] / h1[[2, 2]]]Create a pair of polynomials with a known common divisor (which is the GCD with high probability):
p1 = -9 + 10x + 10x^2 - 9x^3 - 10x^4;
p2 = 6 + 7x - 6x^2 - 5x^3 + 9x^4;
p3 = 5 + 6x + 9x^2 - 8x^3 + 2x^4;
p = Expand[p1 * p2];
q = Expand[p1 * p3];Compute the extended GCD of this pair:
{g, mults} = PolynomialExtendedGCD[p, q, x]Compute the Hermite decomposition:
{u, h} = PolynomialHermiteDecomposition[{{p}, {q}}]The first row of h will recover the GCD up to a unit factor:
Together[h[[1, 1]] / g]The first row of u will recover the extended GCD multipliers up to a unit factor:
Together[u[[1]] / mults]PolynomialHermiteDecomposition works over the Euclidean ring of univariate polynomials:
m = {{1 + x, 2, 3, 4}, {9, 7 - x + 3x ^ 2, 3, 2}, {4, 5, 1 + 2x - 5x ^ 2, 2}};
MatrixForm /@ ({u, r} = PolynomialHermiteDecomposition[m])The entries above any pivot are always lower in degree than that pivot:
Thread[Exponent[r[[1 ;; 2, 3]], x] < Exponent[r[[3, 3]], x]]The determinant of u must be a nonzero number, as these are exactly the invertible polynomials:
Det[u]In contrast, HermiteDecomposition works over the Euclidean ring of the integers:
m2 = m /. x -> 0;
MatrixForm /@ ({u2, r2} = HermiteDecomposition[m2])Now the entries above any pivot are always smaller in absolute value than that pivot:
Thread[Abs@r2[[1 ;; 2, 3]] < r2[[3, 3]]]The determinant of u2 must be 1 or 
, as these are the only invertible integers:
Det[u2]Note that integers and polynomials are different as rings, and in particular one does not recover anything resembling the integer Hermite decomposition by making the polynomial variable zero:
PolynomialHermiteDecomposition[m /. x -> 0]Text
Wolfram Research (2025), PolynomialHermiteDecomposition, Wolfram Language function, https://reference.wolfram.com/language/ref/PolynomialHermiteDecomposition.html.
CMS
Wolfram Language. 2025. "PolynomialHermiteDecomposition." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/PolynomialHermiteDecomposition.html.
APA
Wolfram Language. (2025). PolynomialHermiteDecomposition. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PolynomialHermiteDecomposition.html