Finite-Field Matrix API¶

Functions for matrices whose entries are elements of F_p (integers mod a prime p).

Over a field every nonzero element is a unit, so:

The SNF is always diag(1, ..., 1, 0, ..., 0) where the number of 1s equals the rank.
The HNF is the unique reduced row echelon form (RREF).

Functions¶

snforacle.ff_interface.ff_smith_normal_form ¶

ff_smith_normal_form(
    matrix: Any, backend: _FFBackend | None = None
) -> FFSNFResult

Compute the Smith normal form of a matrix over F_p.

Over a finite field every nonzero element is a unit, so the SNF is always diag(1, ..., 1, 0, ..., 0) where the number of 1s equals the rank.

Parameters:

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

Returns:

Type	Description
`FFSNFResult`	A Pydantic model with fields: `smith_normal_form` The m×n SNF matrix over F_p with 1s at (0,0),...,(r-1,r-1). `rank` The rank r of the matrix over F_p.

snforacle.ff_interface.ff_smith_normal_form_with_transforms ¶

ff_smith_normal_form_with_transforms(
    matrix: Any, backend: _FFBackend | None = None
) -> FFSNFWithTransformsResult

Compute the SNF together with invertible left and right transforms over F_p.

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`ff_smith_normal_form`).	required
`backend`	`_FFBackend \| None`	Name of the backend to use. Defaults to `"pure_python"`.	`None`

Returns:

Type	Description
`FFSNFWithTransformsResult`	A Pydantic model with fields: `smith_normal_form` The m×n SNF matrix over F_p. `rank` The rank r of the matrix over F_p. `left_transform` Invertible m×m matrix U over F_p. `right_transform` Invertible n×n matrix V over F_p. Satisfies: `left_transform @ matrix @ right_transform = smith_normal_form`.

snforacle.ff_interface.ff_hermite_normal_form ¶

ff_hermite_normal_form(
    matrix: Any, backend: _FFBackend | None = None
) -> FFHNFResult

Compute the row Hermite Normal Form of a matrix over F_p.

Over a finite field the HNF is the unique reduced row echelon form (RREF): upper-staircase with leading 1 in each nonzero row, and all other entries in each pivot column equal to 0.

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`ff_smith_normal_form`).	required
`backend`	`_FFBackend \| None`	Name of the backend to use. Defaults to `"flint"` if available, then `"pure_python"`.	`None`

Returns:

Type	Description
`FFHNFResult`	A Pydantic model with field: `hermite_normal_form` The unique RREF of the matrix over F_p.

snforacle.ff_interface.ff_hermite_normal_form_with_transform ¶

ff_hermite_normal_form_with_transform(
    matrix: Any, backend: _FFBackend | None = None
) -> FFHNFWithTransformResult

Compute the row HNF together with the left invertible transform over F_p.

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`ff_smith_normal_form`).	required
`backend`	`_FFBackend \| None`	Name of the backend to use. Defaults to `"pure_python"`.	`None`

Returns:

Type	Description
`FFHNFWithTransformResult`	A Pydantic model with fields: `hermite_normal_form` The unique RREF of the matrix over F_p. `left_transform` Invertible m×m matrix U over F_p. Satisfies: `left_transform @ matrix = hermite_normal_form`.

snforacle.ff_interface.ff_rank ¶

ff_rank(
    matrix: Any, backend: _FFBackend | None = None
) -> FFRankResult

Compute the rank of a matrix over F_p.

Parameters:

Name	Type	Description	Default
`matrix`	`Any`	The input matrix (same accepted types as :func:`ff_smith_normal_form`).	required
`backend`	`_FFBackend \| None`	Name of the backend to use. Defaults to `"flint"` if available, then `"pure_python"`.	`None`

Returns:

Type	Description
`FFRankResult`	A Pydantic model with field: `rank` The rank of the matrix over F_p.

Input models¶

snforacle.ff_schema.DenseFFMatrix ¶

Bases: BaseModel

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

Each entry is an integer in [0, p-1].

snforacle.ff_schema.SparseFFMatrix ¶

Bases: BaseModel

A matrix over F_p stored as (row, col, value) triples.

Entries not listed are implicitly zero. Listed entries must be nonzero (value in [1, p-1]). Duplicate (row, col) pairs are not allowed.

Output models¶

snforacle.ff_schema.FFSNFResult ¶

Bases: BaseModel

The Smith normal form of a matrix over F_p.

Over a field, every nonzero element is a unit, so invariant factors are either 1 (nonzero) or 0. The SNF is diag(1, ..., 1, 0, ..., 0) where the number of 1s equals the rank.

smith_normal_form has 1s at positions (0,0), ..., (r-1,r-1) and 0s elsewhere. rank gives r directly.

snforacle.ff_schema.FFSNFWithTransformsResult ¶

Bases: BaseModel

The SNF together with invertible left and right transforms over F_p.

Satisfies: left_transform @ M @ right_transform = smith_normal_form. All matrices have entries in [0, p-1].

snforacle.ff_schema.FFHNFResult ¶

Bases: BaseModel

Row Hermite Normal Form of a matrix over F_p.

Over a field the HNF is the unique reduced row echelon form (RREF): upper-staircase structure with leading 1 in each nonzero row, and all other entries in each pivot column equal to 0.

snforacle.ff_schema.FFHNFWithTransformResult ¶

Bases: BaseModel

Row HNF together with the left invertible transform over F_p.

Satisfies: left_transform @ M = hermite_normal_form.

snforacle.ff_schema.FFRankResult ¶

Bases: BaseModel

The rank of a matrix over F_p.