# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Compute the Smith decomposition of a matrix of univariate polynomials

Contributed by:
Daniel Lichtblau

ResourceFunction["PolynomialSmithDecomposition"][ computes the Smith decomposition of the matrix | |

ResourceFunction["PolynomialSmithDecomposition"][ computes the Smith decomposition for a matrix of polynomials in the variable |

The result is given in the form {*u*,*s**,**v*}, where *u* and *v* are unimodular matrices, *s* is a diagonal matrix and *u*.*mat**.**v*⩵*s*. Moreover, each diagonal element of *s* divides all subsequent diagonal elements.

A unimodular matrix over a ring of univariate polynomials is a matrix with nonzero determinant lying in the coefficient field (that is, constant).

The Smith decomposition is computed using iterations of the Hermite decomposition, as implemented in the resource function PolynomialHermiteDecomposition.

Multivariate polynomials are regarded as univariate in the specified variable, with all others treated as symbolic coefficients.

ResourceFunction["PolynomialSmithDecomposition"] takes Method and Modulus as options. These are the same as for PolynomialHermiteDecomposition.

For specifics of the Method option, see documentation for PolynomialHermiteDecomposition. The only uses in ResourceFunction["PolynomialSmithDecomposition"] are to pass it to the Hermite computations.

ResourceFunction["PolynomialSmithDecomposition"] is intended for matrices of polynomials in a single variable, with all coefficients being exact numbers.

Compute the Smith decomposition of a 2×3 matrix of low degree polynomials:

In[1]:= |

Out[1]= |

Check the matrix equation:

In[2]:= |

Out[2]= |

Check that *u* and *v* are unimodular; that is, they are constants:

In[3]:= |

Out[3]= |

Check that the diagonal entries of *s* divide into subsequent entries:

In[4]:= |

Out[4]= |

Generate and compute the Hermite decomposition for an 8×12 matrix of random degree-5 polynomials with coefficients between -10 and 10:

In[5]:= |

Out[5]= |

As is often the case in symbolic computation, speed improves considerably when one works over a prime field of modest size:

In[6]:= |

Out[6]= |

Check that the Smith form is a diagonal matrix:

In[7]:= |

Out[7]= |

Check that the decomposition satisfies the necessary matrix identity:

In[8]:= |

Out[8]= |

Check that the left factor is unimodular:

In[9]:= |

Out[9]= |

The determinant of the right factor cannot easily be computed due to expression swell. A probabilistic test that it is unimodular (that is, a constant) is to check that it gives the same value with multiple substitutions of the polynomial variable:

In[10]:= |

Out[10]= |

Use the Smith decomposition to compute the minimal polynomial of a matrix:

In[11]:= |

Out[11]= |

The result from PolynomialSmithDecomposition is a scalar multiple of the result of the resource function MatrixMinimalPolynomial:

In[12]:= |

Out[12]= |

For a square matrix *mat*, the nontrivial diagonal elements in the Smith normal form for *mat*-*x* ℑ are the invariant factors of the characteristic polynomial of *mat* (here ℑ is the identity matrix of same dimension as *mat*). We can use this to compute the rational canonical form.

We start with code to create a companion matrix from a polynomial:

In[13]:= |

Work with an upper triangular matrix having a nontrivial minimal polynomial and hence nontrivial rational canonical form:

In[14]:= |

Out[17]= |

Find the diagonal for the Smith normal form of *mat*-*x*:

In[18]:= |

Out[19]= |

Compute the submatrices for the diagonal block:

In[20]:= |

Out[20]= |

Use SparseArray and Band to reconstruct the companion matrix for *mat* as a diagonal block matrix:

In[21]:= |

Out[21]= |

- 1.0.3 – 18 October 2022
- 1.0.2 – 19 January 2022

This work is licensed under a Creative Commons Attribution 4.0 International License