PopovDecomposition
computes the Popov decomposition of the matrix m consisting of univariate polynomials.
PopovDecomposition[m,x]
yields the Popov decomposition of m consisting of univariate polynomials in the variable x.
Details and Options
- The Popov form of a polynomial matrix is analogous to a reduced lattice for an integer matrix.
- PopovDecomposition[m] returns a pair of matrices {u,p} where u is unimodular, p is the Popov form, and u m=p.
- A square matrix u of polynomials over a coefficient field is said to be unimodular if its determinant Det[u] is a constant in the field. Such matrices have polynomial matrix inverses.
- The matrix m need not be square and need not have full rank. The resulting unimodular u will be square and have the same number of rows as m. The Popov form p will have the same dimensions as m.
- The position of the last entry in a given row having the highest degree (in that row) is known as the pivot position for that row (rows of zero have no pivot position).
- A matrix p is said to be in Popov form if each row having a pivot has it in a unique column, the pivot degrees are increasing, with ties broken by leftmost position coming first, and all other elements in a pivot column are of degree strictly less than the degree of the pivot.
- The Popov form is canonical, that is, unique, up to multiplying rows by constants. Typically these are normalized either by having pivots be monic or, if the base field is the rationals, having all polynomial coefficients be integers.
- The following options can be given:
-
Modulus 0 modulus to assume for integers
Examples
open all close allBasic Examples (2)
Compute the Popov decomposition of a polynomial matrix:
PopovDecomposition[{{5 + 4x, 10 + 6x}, {10 + 9x, 23 + 14x}}]Compute the Popov decomposition of a 2×3 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, p} = PopovDecomposition[m]Expand[u.m - p]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, p} = PopovDecomposition[m]Check that the determinant of u is constant and check the required matrix equation:
{Det[u], Expand[u.m - p]}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, p} = PopovDecomposition[m]Check that the determinant of u is constant and verify the required matrix equation:
{Det[u], Expand[u . m ] == p}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, p} = PopovDecomposition[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] - p]}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, p} = PopovDecomposition[m, x]Check that the determinant of u is constant and verify the required matrix equation:
{Det[u], Expand[u . m - p]}Options (1)
Modulus (1)
PopovDecomposition 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, p} = PopovDecomposition[m, Modulus -> 19]Check that the determinant of u is constant and check the required matrix equation:
{Det[u, Modulus -> 19], Expand[u.m - p, Modulus -> 19]}Applications (3)
One can use PopovDecomposition to compute left-extended GCDs of two polynomial matrices. These will have low degrees as compared to equivalent (up to unimodular transform) GCDs. 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 Popov decomposition:
mat = Join[Transpose@m1, Transpose@m2];
{u, p} = PopovDecomposition[mat, x];The GCD matrix is obtained from h:
gcd = Expand[Transpose@p[[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 U is unimodular and transforms gcd to m3:
{Det[U], Expand[gcd.U - m3]}One can compute what is called a shifted Popov form. This is where columns get weights attached to determine minimality of degree. By suitable weighting earlier columns larger, one can use PopovDecomposition to emulate PolynomialHermiteDecomposition. Emulate this weighting simply by multiplying each column by a power of the variable. A 4×8 matrix and a shift vector:
mat = {{-8 + 5x - 3x^2 - 8x^3 - 4x^4, 2 + 4x + 2x^2 - 2x^3 + 7x^4, -1 - 10x + 9x^2 - 6x^3 - 3x^4, -2 + 5x - 2x^2 + 4x^3 + 6x^4, 4 + 5x^2 - 8x^3 - 5x^4, 4 + 5x - 3x^2 - 6x^3 - 6x^4, -7 - 9x + 8x^2 + 9x^3 + 2x^4, 10 + x + 5x^2 + 8x^3 - 8x^4}, {4 + 5x - 2x^2 + x^3 - 9x^4, -10 - 4x - 3x^2 + 3x^3 + 10x^4, -2x^2 + 4x^3 + x^4, 7 + 10x - 5x^2 - 3x^3 - 10x^4, -6 - 8x - 6x^2 + 7x^3 - 3x^4, -9 - 4x - 5x^2 - 6x^3 - 8x^4, -6 + 10x + 4x^2 + 7x^3 - 9x^4, -1 - 6x - 9x^2 + 9x^3 - 6x^4}, {-2 + 7x - 9x^2 + 8x^3 + 10x^4, -2 + 8x - 9x^2 + 10x^3 + x^4, -8 + 6x - 8x^2 + 4x^3 - 3x^4, -7 + x - x^2 + 4x^3 - 4x^4, 2 - 8x - 4x^2 + 4x^3 + 8x^4, -10 - 7x + 8x^2 - 6x^3 + 4x^4, 9 + x + 4x^2 - 4x^3 + 9x^4, -6 - 9x - 7x^2 + 2x^3 - 2x^4}, {2 + 2x + 3x^2 - 7x^3 + x^4, 8 - x + 8x^2 + 4x^4, -7 + 3x - 4x^2 - 7x^3 - x^4, 5 + 2x^2 - 9x^3, -5 - 7x + 5x^2 - x^3 + x^4, 6 - 9x^2 - 4x^3 - 5x^4, 1 - 3x + x^2 + 6x^3 + 3x^4, -5 - 10x + 5x^2 + 5x^3 + 6x^4}};
shiftvec = x ^ (2 ^ Range[7, 0, -1] - 1)Weight the matrix and find the Popov form:
newmat = mat.DiagonalMatrix[shiftvec];
{u, p} = PopovDecomposition[newmat];Now check that its rows, reordered, give the Hermite form:
{u2, h} = PolynomialHermiteDecomposition[mat];
newp = Together[p.DiagonalMatrix[1 / shiftvec]];
Sort[newp] - Sort[h]Here is a method to find a low-degree solution to underdetermined linear polynomial systems. Use PopovDecomposition on a particular solution along with null vectors to create a new solution of minimal degree. Create an underdetermined system using a 4×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[4, 8, 4, 10, x];
rhs = Flatten[randomMatrix[4, 1, 4, 10, x]];A function to find low-degree polynomial solutions to linear systems with polynomial coefficients:
solvePolynomialSystem[mat_, rhs_ ? VectorQ, x_] := Catch[Module[
{tmat = Join[{rhs}, Transpose[mat]], len = Length[rhs], augmat, uu, hh, soln, nulls, expon, pop, newsol},
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",
Throw[{}, "sPS"],
soln = -Drop[soln, len + 1] / soln[[len + 1]]
];
nulls = Cases[hh, {a : 0.., ___} /; Length[{a}] >= Length[mat] + 1];
If[Length[nulls] >= 1,
nulls = nulls[[All, Length[mat] + 2 ;; ]];
{u, pop} = PopovDecomposition[nulls];
augmat = Join[{soln}, nulls(*pop*)];
expon = 2 * Max[Exponent[augmat, x]];
augmat = Join[Transpose[{Join[{x ^ expon}, ConstantArray[0, Length[pop]]]}], augmat, 2];
{uu, pop} = PopovDecomposition[augmat];
newsol = SelectFirst[pop, Exponent[#[[1]], x] == expon&];
If[newsol === "Missing", Throw[soln, "sPS"]];
soln = Rest[newsol] / (First[newsol] /. x -> 1);
];
soln
], "sPS"]soln = solvePolynomialSystem[mat, rhs, x]Expand[mat.soln - rhs]Properties & Relations (1)
Create a pair of polynomials with a known common divisor (which is the GCD with high probability):
pol1 = -9 + 10x + 10x^2 - 9x^3 - 10x^4;
pol2 = 6 + 7x - 6x^2 - 5x^3 + 9x^4;
pol3 = 5 + 6x + 9x^2 - 8x^3 + 2x^4;
p1 = Expand[pol1 * pol2];
p2 = Expand[pol1 * pol3];Compute the extended GCD of this pair:
{g, mults} = PolynomialExtendedGCD[p1, p2, x]Compute the Popov decomposition:
{u, p} = PopovDecomposition[{{p1}, {p2}}]The first row of p will recover the GCD up to a unit factor:
Together[p[[1, 1]] / g]The first row of u will recover the extended GCD multipliers up to a unit factor:
Together[u[[1]] / mults]Text
Wolfram Research (2026), PopovDecomposition, Wolfram Language function, https://reference.wolfram.com/language/ref/PopovDecomposition.html.
CMS
Wolfram Language. 2026. "PopovDecomposition." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/PopovDecomposition.html.
APA
Wolfram Language. (2026). PopovDecomposition. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PopovDecomposition.html