The Quipper System

Algorithms.CL.SmithReduction

Description

This module provides functions for reducing (non-square) matrices towards Smith Normal Form, and hence for computing the structure of finitely-presented Abelian groups.

The SNF transformation is similar to Gaussian elimination, but over integer matrices, (more generally, matrices over any principal ideal domain)

For background on how this is used to compute the structure of Abelian groups, see the MathOverflow question http://mathoverflow.net/questions/12009/, in particular Greg Kuperberg’s answer http://mathoverflow.net/questions/12009#12053.

We do not implement full SNF reduction here, but rather just as much as is needed to compute the structure of finitely presented Abelian groups from matrix presentations.

Synopsis

# Matrix type and basic access functions.

data CLMatrix a Source #

A data type to hold an m×n matrix (Mij), with entries from an arbitrary type a.

The fields are: integers m and n; a flag t to indicate that a matrix should be considered formally transposed; and an m×n array M containing the entries. When t is False, m is the number of rows, and n the number of columns; when t is True, this is reversed.

(The point of the flag is to allow efficient transposition, and hence to allow operations on rows to be implemented in terms of the corresponding operations on columns without loss of efficiency.)

Constructors

 CLMatrix Int Int Bool (Array (Int, Int) a)

Instances

 Show a => Show (CLMatrix a) # MethodsshowsPrec :: Int -> CLMatrix a -> ShowS #show :: CLMatrix a -> String #showList :: [CLMatrix a] -> ShowS #

The transpose of a matrix

rows :: CLMatrix a -> Int Source #

The number of rows of a matrix

cols :: CLMatrix a -> Int Source #

The number of columns of a matrix

row_list :: CLMatrix a -> [Int] Source #

The row indices of a matrix.

col_list :: CLMatrix a -> [Int] Source #

The column indices of a matrix.

idx :: CLMatrix a -> Int -> Int -> (Int, Int) Source #

An index tuple for a matrix, at a given row and column

(!!!) :: CLMatrix a -> (Int, Int) -> a infix 9 Source #

The matrix entry at a given row and column

(///) :: CLMatrix a -> [(Int, Int, a)] -> CLMatrix a infixl 9 Source #

Update a matrix by a list of (i,j,m_i_j) pairs (all indexes assumed in range of original matrix).

matrix_from_list :: [[a]] -> CLMatrix a Source #

Construct an CLMatrix from a list such as [[1,0],[4,-5]].

Assumes that all inner lists are the same length, and that the overall list is of length ≥1.

delete_row :: Int -> CLMatrix a -> CLMatrix a Source #

Delete a row of a matrix

delete_col :: Int -> CLMatrix a -> CLMatrix a Source #

Delete the first column of a matrix

# Smith reduction

elim_entry_with_pivot :: Integral int => CLMatrix int -> Int -> Int -> Int -> CLMatrix int Source #

elim_entry_with_pivot M i j j': apply elementary column operations to M (equivalently, post-multiply by an invertible matrix) to obtain M' such that M'i,j is gcd(Mi,j, Mi,j') and M'i,j' is 0.

clean_first_row :: Integral int => CLMatrix int -> CLMatrix int Source #

Given a matrix, repeatedly use elim_entry_with_pivot to put the top row into clean form (d,0,…,0).

clean_first_col :: Integral int => CLMatrix int -> CLMatrix int Source #

Dual to clean_first_row.

clean_first_row_col :: Integral int => CLMatrix int -> CLMatrix int Source #

Given a matrix, repeatedly apply clean_first_row and its analogue on columns until the first row and column are both in clean form.

# Structure of Abelian Groups

structure_constants_from_matrix :: (Show int, Integral int) => CLMatrix int -> [int] Source #

Given a matrix, taken as presenting an Abelian group (with generators corresponding to columns of the matrix, and relations specified by the rows), compute the structure constants of the group, not necessarily sorted.

That is, return a list of natural numbers [n0,…,ns] such that the group given by the input presentation is isomorphic to the product of the cyclic groups ℤ/(ni).

group_order_from_matrix :: (Show int, Integral int) => CLMatrix int -> int Source #

Given a matrix, taken as presenting an Abelian group, compute the order of the group.

Returns 0 if the group is of infinite order.