Type Alias ZMatrix 

pub type ZMatrix = ExactMatrix<BigInt>;

Dense matrix over ℤ with BigInt entries.

Integer-specific operations: Bareiss det, hermite_normal_form, smith_normal_form, integer_nullspace, is_unimodular, lattice_determinant.

Aliased Type

pub struct ZMatrix { /* private fields */ }

Implementations

impl ZMatrix

pub fn to_qmatrix(&self) -> QMatrix

Convert to a QMatrix (every entry becomes n/1).

pub fn to_matrix(&self, ctx: &Context) -> Matrix

Convert to a symbolic Matrix of integer literals in ctx.

pub fn det(&self) -> Result<BigInt, SymplexError>

Determinant by Bareiss fraction-free elimination (O(n³) integer operations, no fractions at any stage).

Errors

SymplexError::InvalidArgument if the matrix is not square.

Examples

use symplex::matrix::ZMatrix;
use symplex::num_bigint::BigInt;

let m = ZMatrix::from_i64(&[&[2, 1, 0], &[1, 3, 1], &[0, 1, 4]]).unwrap();
assert_eq!(m.det().unwrap(), BigInt::from(18));
assert!(ZMatrix::from_i64(&[&[1, 2, 3]]).unwrap().det().is_err());

pub fn rank(&self) -> usize

Rank over ℚ (equivalently over ℤ as a lattice).

Examples

use symplex::matrix::ZMatrix;

assert_eq!(ZMatrix::from_i64(&[&[1, 2], &[2, 4]]).unwrap().rank(), 1);

pub fn content(&self) -> BigInt

Greatest common divisor of all entries (0 for the zero matrix).

pub fn hermite_normal_form(&self) -> ZMatrix

Row-style Hermite normal form H = U·A (U unimodular).

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. See normalforms for the conventions in detail.

Examples

use symplex::matrix::ZMatrix;

let a = ZMatrix::from_i64(&[&[1, 2], &[2, 4]]).unwrap();
assert_eq!(a.hermite_normal_form(), ZMatrix::from_i64(&[&[1, 2], &[0, 0]]).unwrap());

pub fn hermite_normal_form_with_transform(&self) -> (ZMatrix, ZMatrix)

Row-style Hermite normal form with its transform: (H, U), H = U·A, det U = ±1.

pub fn column_hermite_normal_form(&self) -> ZMatrix

Column-style Hermite normal form H = A·V (Cohen’s Algorithm 2.4.5, SymPy’s convention): zero columns first, each pivot the lowest nonzero entry of its column, pivots positive and strictly descending from left to right, entries to the right of a pivot in [0, pivot).

Examples

use symplex::matrix::ZMatrix;

let a = ZMatrix::from_i64(&[&[12, 6, 4], &[3, 9, 6], &[2, 16, 14]]).unwrap();
assert_eq!(
    a.column_hermite_normal_form(),
    ZMatrix::from_i64(&[&[10, 0, 2], &[0, 15, 3], &[0, 0, 2]]).unwrap()
);

pub fn smith_normal_form(&self) -> ZMatrix

Smith normal form diag(d₁, …, dᵣ, 0, …) with dᵢ > 0, dᵢ | dᵢ₊₁.

Examples

use symplex::matrix::ZMatrix;

let a = ZMatrix::from_i64(&[&[2, 0], &[0, 3]]).unwrap();
assert_eq!(a.smith_normal_form(), ZMatrix::from_i64(&[&[1, 0], &[0, 6]]).unwrap());

pub fn smith_normal_form_with_transforms(&self) -> (ZMatrix, ZMatrix, ZMatrix)

Smith normal form with transforms (S, U, V), S = U·A·V, det U = det V = ±1.

pub fn integer_nullspace(&self) -> Vec<ZMatrix>

A ℤ-basis of the integer kernel {x ∈ ℤⁿ : A·x = 0}, as n × 1 column vectors (n − rank of them; empty for full column rank).

Examples

use symplex::matrix::ZMatrix;

let a = ZMatrix::from_i64(&[&[2, 4, 6]]).unwrap();
let basis = a.integer_nullspace();
assert_eq!(basis.len(), 2);
for k in &basis {
    assert!((&a * k).is_zero());
}

pub fn is_unimodular(&self) -> bool

Is this a square matrix with det = ±1 (invertible over ℤ)? Non-square matrices give false.

pub fn lattice_determinant(&self) -> Result<BigInt, SymplexError>

Index [ℤᵐ : A·ℤⁿ] of the lattice spanned by the columns (|det A| for a square nonsingular matrix).

Errors

SymplexError::InvalidArgument if A does not have full row rank (the index would be infinite).

impl ZMatrix

pub fn inv_mod(&self, m: &BigInt) -> Result<ZMatrix, SymplexError>

Inverse modulo m: the integer matrix B with entries in [0, m) and A·B ≡ I (mod m), computed as adj(A) · det(A)⁻¹ mod m. SymPy: Matrix.inv_mod(m).

Errors

SymplexError::InvalidArgument if the matrix is not square, m < 2, or gcd(det A, m) ≠ 1 (which includes every singular matrix).

Examples

use symplex::matrix::ZMatrix;
use symplex::num_bigint::BigInt;

let a = ZMatrix::from_i64(&[&[1, 2], &[3, 4]]).unwrap();
let b = a.inv_mod(&BigInt::from(5)).unwrap();
assert_eq!(b, ZMatrix::from_i64(&[&[3, 1], &[4, 2]]).unwrap());
// det = −2 shares the factor 2 with the modulus 4.
assert!(a.inv_mod(&BigInt::from(4)).is_err());

pub fn lll_default(&self) -> Result<ZMatrix, SymplexError>

LLL-reduced basis of the lattice spanned by the rows, with the standard Lovász parameter δ = 3/4. See lll.

Errors

Same as lll.

pub fn lll(&self, delta: (i64, i64)) -> Result<ZMatrix, SymplexError>

Lenstra–Lenstra–Lovász reduction of the lattice basis formed by the rows, with Lovász parameter δ = num/den. SymPy: Matrix.lll(delta).

The Gram–Schmidt data is kept as exact rationals, so the result is exactly LLL-reduced: with μ_ij = ⟨b_i, b*_j⟩ / ⟨b*_j, b*_j⟩, every |μ_ij| ≤ 1/2 (size condition) and ‖b*_k‖² ≥ (δ − μ²_{k,k−1}) ‖b*_{k−1}‖² (Lovász condition). The reduced rows span the same lattice as the input (they differ by a unimodular transform, see lll_with_transform), and the first row is within a factor 2^{(n−1)/2} of a shortest lattice vector. The reduction order and rounding follow SymPy’s DomainMatrix.lll, so the output coincides with SymPy’s for the same input.

Errors

SymplexError::InvalidArgument if δ is not in the open interval (1/4, 1), or the rows are linearly dependent (this includes having more rows than columns).

Examples

use symplex::matrix::ZMatrix;

let b = ZMatrix::from_i64(&[&[1, 1, 1], &[-1, 0, 2], &[3, 5, 6]]).unwrap();
let r = b.lll((3, 4)).unwrap();
assert_eq!(r, ZMatrix::from_i64(&[&[0, 1, 0], &[1, 0, 1], &[-1, 0, 2]]).unwrap());
// Same lattice: identical Hermite normal forms.
assert_eq!(r.hermite_normal_form(), b.hermite_normal_form());
assert!(b.lll((1, 4)).is_err());

pub fn lll_with_transform( &self, delta: (i64, i64), ) -> Result<(ZMatrix, ZMatrix), SymplexError>

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

Errors

Same as lll.

Examples

use symplex::matrix::ZMatrix;

let b = ZMatrix::from_i64(&[&[1, 1, 1], &[-1, 0, 2], &[3, 5, 6]]).unwrap();
let (r, t) = b.lll_with_transform((3, 4)).unwrap();
assert_eq!(&t * &b, r);
assert!(t.is_unimodular());

Trait Implementations

impl TryFrom<&Matrix> for ZMatrix

fn try_from(m: &Matrix) -> Result<Self, SymplexError>

Every entry must be an integer literal (after a constant-folding eval if the raw entries are not).

type Error = SymplexError

The type returned in the event of a conversion error.