Function Repository Resource:

PopovDecomposition

Source Notebook

Compute the Popov decomposition of a matrix of univariate polynomials

Contributed by: Daniel Lichtblau

ResourceFunction["PopovDecomposition"][mat]

computes the Popov decomposition of the matrix mat consisting of univariate polynomials.

ResourceFunction["PopovDecomposition"][mat,x]

gives the Popov decomposition of the matrix mat regarded as univariate polynomials in the variable x.

Details and Options

The result is given in the form {u,pop} where u is a unimodular matrix, pop is the Popov normal form for mat and u.mat=pop.
The Popov normal form can be characterized as follows. Take the maximal degrees in each column, and permute columns so these are ordered from largest to smallest. Remove any rows of zeros. Now take the matrix of coefficients of maximal degree in each row. This matrix has only nonzero constants on the main diagonal, and zeros everywhere else. Stated differently, after permuting columns to correspond to decreasing maximal degree, the maximal degrees in each row appear on the main diagonal, and these degrees are non-increasing.
The Popov normal form is sometimes referred to as the lattice-reduced form, as it satisfies a minimal degree property analogous to the (approximately) minimal-length behavior of rows of a reduced-integer lattice.

Examples

Basic Examples (4) 

Compute the Popov decomposition for a 3×3 matrix of quartic polynomials:

In[1]:=
{u, pop} = ResourceFunction[
  "PopovDecomposition"][{{-8 + 5 x - 3 x^2 - 8 x^3 - 4 x^4, 2 + 4 x + 2 x^2 - 2 x^3 + 7 x^4, -1 - 10 x + 9 x^2 - 6 x^3 - 3 x^4}, {-2 + 5 x - 2 x^2 + 4 x^3 + 6 x^4, 4 + 5 x^2 - 8 x^3 - 5 x^4, 4 + 5 x - 3 x^2 - 6 x^3 - 6 x^4}, {-7 - 9 x + 8 x^2 + 9 x^3 + 2 x^4, 10 + x + 5 x^2 + 8 x^3 - 8 x^4, 4 + 5 x - 2 x^2 + x^3 - 9 x^4}}]
Out[1]=

Check that the determinant is a constant:

In[2]:=
Det[u]
Out[2]=

Check that the necessary matrix identity is satisfied:

In[3]:=
Expand[u . mat - pop]
Out[3]=

Check that the maximal degrees in each row move successively to the right:

In[4]:=
Map[Exponent[#, x] &, pop, {2}]
Out[4]=

Scope (2) 

Create a tool to generate a 3×3 matrix of quartic polynomials:

In[5]:=
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}]

If the input matrix does not have full row rank, there will be zero rows at the bottom of the Popov form (as many as the row rank deficiency):

In[6]:=
SeedRandom[1111];
mat = randomMatrix[3, 2, 4, 10, x];
{u, pop} = ResourceFunction["PopovDecomposition"][mat]
Out[3]=

Options (3) 

Generate a 3×3 matrix of quartic polynomials:

In[7]:=
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[3, 3, 4, 10, x];

Compute the Popov decomposition over the integers modulo a prime:

In[8]:=
{u, pop} = ResourceFunction["PopovDecomposition"][mat, Modulus -> 103]
Out[8]=

Check the necessary matrix identity:

In[9]:=
Expand[u . mat - pop, Modulus -> 103]
Out[9]=

Version History

  • 2.0.0 – 05 June 2020
  • 1.0.0 – 12 November 2019

Related Resources

License Information