Module normalforms 

Integer matrix normal forms: Hermite, Smith, unimodular transforms, integer kernels. Integer matrix normal forms: Hermite normal form, Smith normal form, unimodular transforms and integer kernels.

Everything here is exact over BigInt. Inputs are Matrix values whose entries must be integer literals (a fraction, a symbol or an unevaluated constant expression gives SymplexError::InvalidArgument); results are returned as integer matrices in the same Context. The algorithms live on ZMatrix — use it directly when the data is already integer to skip the expression layer.

Conventions

• hermite_normal_form is row-style: H = U·A with U unimodular (det U = ±1). H is in row echelon form with positive pivots, every entry above a pivot reduced into [0, pivot), zero rows at the bottom. This form is unique, so it is idempotent and invariant under left-multiplication by any unimodular matrix.
• column_hermite_normal_form is column-style: H = A·V, the convention used by SymPy’s hermite_normal_form (Cohen, A Course in Computational Algebraic Number Theory, Algorithm 2.4.5): each nonzero column’s pivot is its lowest nonzero entry, pivots move strictly downwards from left to right, pivots are positive, entries to the right of a pivot in its row lie in [0, pivot), zero columns come first. For a square nonsingular matrix this is upper triangular.
• smith_normal_form gives S = U·A·V = diag(d₁, …, dᵣ, 0, …) with dᵢ > 0 and dᵢ | dᵢ₊₁.

Examples

use symplex::prelude::*;
use symplex::normalforms::{hermite_normal_form_with_transform, smith_normal_form};

let ctx = Context::new();
let a = matrix![ctx, [2, 4, 4], [-6, 6, 12], [10, -4, -16]];
let (h, u) = hermite_normal_form_with_transform(&a).unwrap();
assert_eq!(h, matrix![ctx, [2, 4, 4], [0, 6, 0], [0, 0, 12]]);
assert_eq!((&u * &a).eval(), h);
assert_eq!(smith_normal_form(&a).unwrap(), matrix![ctx, [2, 0, 0], [0, 6, 0], [0, 0, 12]]);

Functions

column_hermite_normal_form

Column-style Hermite normal form H = A·V (column operations), the convention of SymPy’s hermite_normal_form and of Cohen’s Algorithm 2.4.5.

hermite_normal_form

Row-style Hermite normal form H of an integer matrix A.

hermite_normal_form_with_transform

Row-style Hermite normal form together with its transform: (H, U) with H = U·A and det U = ±1. See hermite_normal_form for the normalisation of H.

integer_nullspace

A ℤ-basis of the integer kernel {x ∈ ℤⁿ : A·x = 0} of an m×n integer matrix, as n×1 column vectors.

is_unimodular

Is A a square integer matrix with det A = ±1 (invertible over ℤ)?

lattice_determinant

Determinant (index) of the lattice spanned by the columns of A.

lll

LLL-reduced basis of the lattice spanned by the rows of the integer matrix A, with Lovász parameter δ = num/den (the standard choice is (3, 4)). SymPy: Matrix.lll(delta).

lll_with_transform

LLL reduction with its unimodular transform: (R, T) with R = T·A and det T = ±1. SymPy: Matrix.lll_transform(delta).

smith_normal_form

Smith normal form S = diag(d₁, …, dᵣ, 0, …, 0) of an integer matrix, with dᵢ > 0 and dᵢ | dᵢ₊₁.

smith_normal_form_with_transforms

Smith normal form with transforms: (S, U, V) such that S = U·A·V, det U = ±1, det V = ±1. See smith_normal_form for the form of S. U and V are not unique; the returned pair is the one produced by the elimination.