Polynomial Matrix API¶

Functions for matrices whose entries are polynomials over a finite field F_p[x].

Polynomials are represented as coefficient lists [c_0, c_1, ..., c_d] (constant term first), with coefficients in [0, p-1]. The zero polynomial is []. No trailing zeros are permitted.

All invariant factors and HNF pivots are returned as monic polynomials.

Functions¶

snforacle.poly_interface.poly_smith_normal_form ¶

poly_smith_normal_form(
    matrix: Any, backend: _PolyBackendName | None = None
) -> PolySNFResult

Compute the Smith normal form of a polynomial matrix over F_p[x].

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix as a `DensePolyMatrix`, `SparsePolyMatrix`, or a plain `dict` conforming to one of those schemas.	required
`backend`	`_PolyBackendName \| None`	Name of the backend to use. Defaults to `"sage"` if available, then `"magma"`, then `"pure_python"`.	`None`

Returns:

Type	Description
`PolySNFResult`	A Pydantic model with fields: `smith_normal_form` The m×n SNF matrix. The diagonal entries d_1 \| d_2 \| ... \| d_r are monic polynomials in ascending-degree order; all other entries are zero. `invariant_factors` The sequence `[d_1, ..., d_r]` of nonzero monic diagonal entries.

snforacle.poly_interface.poly_smith_normal_form_with_transforms ¶

poly_smith_normal_form_with_transforms(
    matrix: Any, backend: _PolyBackendName | None = None
) -> PolySNFWithTransformsResult

Compute the SNF together with invertible left and right transforms.

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`poly_smith_normal_form`).	required
`backend`	`_PolyBackendName \| None`	Name of the backend to use.	`None`

Returns:

Type	Description
`PolySNFWithTransformsResult`	A Pydantic model with fields: `smith_normal_form` The m×n SNF matrix. `invariant_factors` The nonzero monic diagonal entries. `left_transform` Invertible m×m matrix U over F_p[x]. `right_transform` Invertible n×n matrix V over F_p[x]. Satisfies: `left_transform @ matrix @ right_transform = smith_normal_form`.

snforacle.poly_interface.poly_hermite_normal_form ¶

poly_hermite_normal_form(
    matrix: Any, backend: _PolyBackendName | None = None
) -> PolyHNFResult

Compute the row Hermite Normal Form of a polynomial matrix over F_p[x].

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`poly_smith_normal_form`).	required
`backend`	`_PolyBackendName \| None`	Name of the backend to use.	`None`

Returns:

Type	Description
`PolyHNFResult`	A Pydantic model with field: `hermite_normal_form` Upper-triangular matrix with monic pivots; entries above each pivot have strictly smaller degree than the pivot.

snforacle.poly_interface.poly_hermite_normal_form_with_transform ¶

poly_hermite_normal_form_with_transform(
    matrix: Any, backend: _PolyBackendName | None = None
) -> PolyHNFWithTransformResult

Compute the row HNF together with the left invertible transform.

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`poly_smith_normal_form`).	required
`backend`	`_PolyBackendName \| None`	Name of the backend to use.	`None`

Returns:

Type	Description
`PolyHNFWithTransformResult`	A Pydantic model with fields: `hermite_normal_form` Upper-triangular matrix with monic pivots. `left_transform` Invertible m×m matrix U over F_p[x]. Satisfies: `left_transform @ matrix = hermite_normal_form`.

snforacle.poly_interface.poly_elementary_divisors ¶

poly_elementary_divisors(
    matrix: Any, backend: _PolyBackendName | None = None
) -> PolyElementaryDivisorsResult

Compute the non-zero invariant factors (elementary divisors) over F_p[x].

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`poly_smith_normal_form`).	required
`backend`	`_PolyBackendName \| None`	Name of the backend to use.	`None`

Returns:

Type	Description
`PolyElementaryDivisorsResult`	A Pydantic model with field: `elementary_divisors` Monic polynomials in ascending-degree order; same as the invariant_factors from :func:`poly_smith_normal_form`.

Input models¶

snforacle.poly_schema.DensePolyMatrix ¶

Bases: BaseModel

A matrix over F_p[x] stored as a full list of rows.

Each entry is a coefficient list [c_0, ..., c_d] with all coefficients in [0, p-1]. Trailing zeros are not allowed (use [] for the zero polynomial).

snforacle.poly_schema.SparsePolyMatrix ¶

Bases: BaseModel

A matrix over F_p[x] stored as (row, col, coeffs) triples.

Entries not listed are implicitly the zero polynomial.

Output models¶

snforacle.poly_schema.PolySNFResult ¶

Bases: BaseModel

The Smith normal form of a polynomial matrix over F_p[x].

Invariant factors are monic polynomials d_1 | d_2 | ... | d_r satisfying the divisibility chain, sorted by degree (ascending) then lexicographically. The SNF matrix has these on its diagonal; all other entries are zero.

snforacle.poly_schema.PolySNFWithTransformsResult ¶

Bases: BaseModel

SNF of a polynomial matrix together with invertible transforms.

Satisfies: left_transform @ M @ right_transform = smith_normal_form. The transforms are invertible matrices over F_p[x] (not necessarily unimodular in the polynomial sense, but with nonzero constant determinant).

snforacle.poly_schema.PolyHNFResult ¶

Bases: BaseModel

Row Hermite Normal Form of a polynomial matrix over F_p[x].

The HNF is the unique upper-triangular matrix H = U @ M where U is invertible over F_p[x], the pivots are monic, and entries above each pivot have strictly smaller degree than the pivot.

snforacle.poly_schema.PolyHNFWithTransformResult ¶

Bases: BaseModel

Row HNF together with the left invertible transform.

Satisfies: left_transform @ M = hermite_normal_form.

snforacle.poly_schema.PolyElementaryDivisorsResult ¶

Bases: BaseModel

Non-zero invariant factors (elementary divisors) of a polynomial matrix.

These are the same monic polynomials as the diagonal of the SNF, returned in ascending-degree order.