Matrices with Integer Entries ( integer_matrix )

Definition

An instance of data type integer_matrix is a matrix of variables of type integer, the so called ring type. The arithmetic type integer is required to behave like integers in the mathematical sense.

The types integer_matrix and integer_vector together realize many functions of basic linear algebra. All functions on integer matrices compute the exact result, i.e., there is no rounding error. Most functions of linear algebra are checkable, i.e., the programs can be asked for a proof that their output is correct. For example, if the linear system solver declares a linear system Ax = b unsolvable it also returns a vector c such that c^TA = 0 and c^Tb! = 0. All internal correctness checks can be switched on by the flag LA_SELFTEST. Preconditions are checked by default and can be switched off by the compile flag LEDA_CHECKING_OFF.

#include < LEDA/integer _matrix.h >

Creation

integer_matrix	M(int n, int m)	creates an instance M of type integer_matrix of dimension n x m.
integer_matrix	M(int n = 0)	creates an instance M of type integer_matrix of dimension n x n.
integer_matrix	M(array< integer_vector > A)
		creates an instance M of type integer_matrix. Let A be an array of m column - vectors of common dimension n. M is initialized to an n x m matrix with the columns as specified by A.
integer_matrix	integer_matrix::identity(int n)
		returns an identity matrix of dimension n.

Operations

int	M.dim1()	returns n, the number of rows of M.
int	M.dim2()	returns m, the number of columns of M.
integer_vector&	M.row(int i)	returns the i-th row of M (an m - vector). Precondition: 0 < = i < = n - 1.
integer_vector	M.col(int i)	returns the i-th column of M (an n - vector). Precondition: 0 < = i < = m - 1.
integer&	M(int i, int j)	returns Mi, j. Precondition: 0 < = i < = n - 1 and 0 < = j < = m - 1.

Arithmetic Operators

integer_matrix	M + M1	Addition. Precondition: M.dim1() == M1.dim1() and M.dim2() == M1.dim2().
integer_matrix	M - M1	Subtraction. Precondition: M.dim1() == M1.dim1() and M.dim2() == M1.dim2().
integer_matrix	M * M1	Multiplication. Precondition: M.dim2() == M1.dim1().
integer_vector	M * integer_vector vec	Multiplication with vector. Precondition: M.dim2() == vec.dim().
integer_matrix	M * integer x	Multiplication of every entry with integer x.
integer_matrix	integer x * M	Multiplication of every entry with integer x.

Non-Member Functions

integer_matrix	transpose(integer_matrix M)
		returns MT (m x n - matrix).
integer_matrix	inverse(integer_matrix M, integer& D)
		returns the inverse matrix of M. More precisely, 1/D times the matrix returned is the inverse of M. Precondition: determinant(M) ! = 0.

bool	inverse(integer_matrix M, integer_matrix& inverse, integer& D, integer_vector& c)
		determines whether M has an inverse. It also computes either the inverse as (1/D)*inverse or a vector c such that cT*M = 0.
integer	determinant(integer_matrix M, integer_matrix& L, integer_matrix& U, array<int>& q, integer_vector& c)
		returns the determinant D of M and sufficient information to verify that the value of the determinant is correct. If the determinant is zero then c is a vector such that cT*M = 0. If the determinant is non-zero then L and U are lower and upper diagonal matrices respectively and q encodes a permutation matrix Q with Q(i, j) = 1 iff i = q(j) such that L*M*Q = U, L(0, 0) = 1, L(i, i) = U(i - 1, i - 1) for all i, 1 < = i < n, and D = s*U(n - 1, n - 1) where s is the determinant of Q. Precondition: M is quadratic.
bool	verify_determinant(integer_matrix M, integer D, integer_matrix& L, integer_matrix& U, array<int> q, integer_vector& c)
		verifies the conditions stated above.
integer	determinant(integer_matrix M)
		returns the determinant of M. Precondition: M is quadratic.
int	sign_of_determinant(integer_matrix M)
		returns the sign of the determinant of M. Precondition: M is quadratic.
bool	linear_solver(integer_matrix M, integer_vector b, integer_vector& x, integer& D, integer_matrix& spanning_vectors, integer_vector& c)
		determines the complete solution space of the linear system M*x = b. If the system is unsolvable then cT*M = 0 and cT*b! = 0. If the system is solvable then (1/D)x is a solution, and the columns of spanning_vectors are a maximal set of linearly independent solutions to the corresponding homogeneous system. Precondition: M.dim1() == b.dim().
bool	linear_solver(integer_matrix M, integer_vector b, integer_vector& x, integer& D, integer_vector& c)
		determines whether the linear system M*x = b is solvable. If yes, then (1/D)x is a solution, if not then cT*M = 0 and cT*b! = 0. Precondition: M.dim1() == b.dim().
bool	linear_solver(integer_matrix M, integer_vector b, integer_vector& x, integer& D)
		as above, but without the witness c Precondition: M.dim1() == b.dim().
bool	is_solvable(integer_matrix M, integer_vector b)
		determines whether the system M*x = b is solvable Precondition: M.dim1() == b.dim().
bool	homogeneous_linear_solver(integer_matrix M, integer_vector& x)
		determines whether the homogeneous linear system M*x = 0 has a non - trivial solution. If yes, then x is such a solution.
int	homogeneous_linear_solver(integer_matrix M, integer_matrix& spanning_vecs)
		determines the solution space of the homogeneous linear system M*x = 0. It returns the dimension of the solution space. Moreover the columns of spanning_vecs span the solution space.
void	independent_columns(integer_matrix M, array<int>& columns)
		returns the indices of a maximal subset of independent columns of M. The index range of columns starts at 0.
int	rank(integer_matrix M)	returns the rank of matrix M
ostream&	ostream& O << M	writes matrix M row by row to the output stream O.
istream&	istream& I >> integer_matrix& M
		reads matrix M row by row from the input stream I.

Implementation

The datatype integer_matrix is implemented by two-dimensional arrays of variables of type integer. Operations determinant, inverse, linear_solver, and rank take time O(n³), column takes time O(n), row, dim1, dim2, take constant time, and all other operations take time O(nm). The space requirement is O(nm).

All functions on integer matrices compute the exact result, i.e., there is no rounding error. The implemenation follows a proposal of J. Edmonds (J. Edmonds, Systems of distinct representatives and linear algebra, Journal of Research of the Bureau of National Standards, (B), 71, 241 - 245). Most functions of linear algebra are checkable , i.e., the programs can be asked for a proof that their output is correct. For example, if the linear system solver declares a linear system Ax = b unsolvable it also returns a vector c such that c^TA = 0 and c^Tb! = 0.