Hermite and Smith Normal Forms¶

desr uses the diophantine package, which in turn uses the methods found in [Havas1998], to calculate the Hermite normal form of matrices.

matrix_normal_forms should be used for all normal form calculations - we never call the diophantine package directly from other parts of desr.

This is also where the Smith normal form functions live, which use Hermite normal forms at their core.

Hermite Normal Forms¶

desr.matrix_normal_forms.is_hnf_row(matrix_)[source]

Decide whether a matrix is in Hermite normal form, when acting on rows. This is according to the Havas Majewski Matthews definition.

Parameters:	matrix (sympy.Matrix) – The matrix in question.
Returns:	bool

>>> is_hnf_row(sympy.eye(4))
True
>>> is_hnf_row(sympy.ones(2))
False
>>> is_hnf_row(sympy.Matrix([[1, 2, 0], [0, 1, 0]]))
False
>>> is_hnf_row(sympy.Matrix([[1, 0, 0], [0, 2, 1]]))
True
>>> is_hnf_row(sympy.Matrix([[1, 0, 0], [0, -2, 1]]))
False

desr.matrix_normal_forms.is_hnf_col(matrix_)[source]

Decide whether a matrix is in row Hermite normal form, when acting on rows.

Parameters:	matrix (sympy.Matrix) – The matrix in question.
Returns:	bool

desr.matrix_normal_forms.hnf_row(matrix_)

Default function for calculating row Hermite normal forms.

Parameters:	matrix (sympy.Matrix) – Input matrix.
Returns:	hermite_normal_form (sympy.Matrix): The column Hermite normal form of matrix_. normal_multiplier (sympy.Matrix): The normal Hermite multiplier.
Return type:	tuple
Return type:	(sympy.Matrix, sympy.Matrix)

desr.matrix_normal_forms.hnf_col(matrix_)

Default function for calculating column Hermite normal forms.

Parameters:	matrix (sympy.Matrix) – Input matrix.
Returns:	Tuple containing: hermite_normal_form (sympy.Matrix): The column Hermite normal form of matrix_. normal_multiplier (sympy.Matrix): The normal Hermite multiplier.
Return type:	tuple
Return type:	(sympy.Matrix, sympy.Matrix)

desr.matrix_normal_forms.normal_hnf_row(matrix_)[source]

Return the row HNF and the unique normal Hermite multiplier.

Parameters:	matrix (sympy.Matrix) – Input matrix.
Returns:	Tuple containing: hermite_normal_form (sympy.Matrix): The row Hermite normal form of matrix_. normal_multiplier (sympy.Matrix): The normal Hermite multiplier.
Return type:	tuple

desr.matrix_normal_forms.normal_hnf_col(matrix_)[source]

Return the column HNF and the unique normal Hermite multiplier.

Parameters:	matrix (sympy.Matrix) – Input matrix.
Returns:	Tuple containing: hermite_normal_form (sympy.Matrix): The column Hermite normal form of matrix_. normal_multiplier (sympy.Matrix): The normal Hermite multiplier.
Return type:	tuple

>>> A = sympy.Matrix([[8, 2, 15, 9, 11],
...                   [6, 0, 6, 2, 3]])
>>> h, v = normal_hnf_col(A)
>>> h
Matrix([
[1, 0, 0, 0, 0],
[0, 1, 0, 0, 0]])
>>> v
Matrix([
[  0,  0,   1,  0,   0],
[  0,  0,   0,  1,   0],
[  2,  1,   3,  1,   5],
[  9,  2,  21,  3,  21],
[-10, -3, -22, -4, -24]])
>>> (A * v) == h
True

Smith Normal Form¶

desr.matrix_normal_forms.is_smf(matrix_)[source]

Given a rectangular \(n \times m\) integer matrix, determine whether it is in Smith normal form or not.

Parameters:	matrix (sympy.Matrix) – The rectangular matrix to be decomposed
Returns:	True if in Smith normal form, False otherwise.
Return type:	bool

>>> matrix_ = sympy.diag(1, 1, 2)
>>> is_smf(matrix_)
True
>>> matrix_ = sympy.diag(-1, 1, 2)
>>> is_smf(matrix_)
False
>>> matrix_ = sympy.diag(2, 1, 1)
>>> is_smf(matrix_)
False
>>> matrix_ = sympy.diag(1, 2, 0)
>>> is_smf(matrix_)
True
>>> matrix_ = sympy.diag(2, 6, 0)
>>> is_smf(matrix_)
True
>>> matrix_ = sympy.diag(2, 5, 0)
>>> is_smf(matrix_)
False
>>> matrix_ = sympy.diag(0, 1, 1)
>>> is_smf(matrix_)
False
>>> matrix_ = sympy.diag(0)
>>> is_smf(sympy.diag(0)), is_smf(sympy.diag(1)), is_smf(sympy.Matrix()),
(True, True, True)

Check a real example:

>>> matrix_ = sympy.Matrix([[2, 4, 4],
...                         [-6, 6, 12],
...                         [10, -4, -16]])
>>> is_smf(matrix_)
False

>>> matrix_ = sympy.diag(2, 6, 12)
>>> is_smf(matrix_)
True

Check it works for non-square matrices:

>>> matrix_ = sympy.Matrix(4, 5, range(20))
>>> is_smf(matrix_)
False

>>> matrix_ = sympy.Matrix([[1, 0], [1, 2]])
>>> is_smf(matrix_)
False

desr.matrix_normal_forms.smf(matrix_)[source]

Given a rectangular \(n \times m\) integer matrix, calculate the Smith Normal Form \(S\) and multipliers \(U\), \(V\) such that \(U \textrm{matrix_} V = S\).

Parameters:	matrix (sympy.Matrix) – The rectangular matrix to be decomposed.
Returns:	S (sympy.Matrix) – The Smith normal form of matrix_. U (sympy.Matrix) – \(U\) (the matrix representing the row operations of the decomposition). V (sympy.Matrix) – \(V\) (the matrix representing the column operations of the decomposition).
Return type:	(sympy.Matrix, sympy.Matrix, sympy.Matrix)

>>> matrix_ = sympy.Matrix([[2, 4, 4],
...                         [-6, 6, 12],
...                         [10, -4, -16]])
>>> smf(matrix_)[0]
Matrix([
[2, 0,  0],
[0, 6,  0],
[0, 0, 12]])

>>> matrix_ = sympy.diag(2, 1, 0)
>>> smf(matrix_)[0]
Matrix([
[1, 0, 0],
[0, 2, 0],
[0, 0, 0]])

>>> matrix_ = sympy.diag(5, 2, 0)
>>> smf(matrix_)[0]
Matrix([
[1,  0, 0],
[0, 10, 0],
[0,  0, 0]])