next up previous contents index
Next: Rational Vectors ( rat_vector Up: Number Types and Linear Previous: Vectors with Integer Entries   Contents   Index


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 cTA = 0 and cTb! = 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/numbers/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(const 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 + const integer_matrix& M1
    Addition.
Precondition
M.dim1() == M1.dim1() and M.dim2() == M1.dim2().

integer_matrix M - const integer_matrix& M1
    Subtraction.
Precondition
M.dim1() == M1.dim1() and M.dim2() == M1.dim2().

integer_matrix M * const integer_matrix& M1
    Multiplication.
Precondition
M.dim2() == M1.dim1().

integer_vector M * const integer_vector& vec
    Multiplication with vector.
Precondition
M.dim2() == vec.dim().

integer_matrix const integer_matrix& M * const integer& x
    Multiplication of every entry with integer x.

integer_matrix const integer& x * const integer_matrix& M
    Multiplication of every entry with integer x.

Non-Member Functions

integer_matrix transpose(const integer_matrix& M)
    returns MT (m x n - matrix).

integer_matrix inverse(const 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) $ \not=$ 0.

bool inverse(const 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(const 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(const integer_matrix& M, integer D, integer_matrix& L, integer_matrix& U, array<int> q, integer_vector& c)
    verifies the conditions stated above.

integer determinant(const integer_matrix& M)
    returns the determinant of M.
Precondition M is quadratic.

int sign_of_determinant(const integer_matrix& M)
    returns the sign of the determinant of M.
Precondition M is quadratic.

bool linear_solver(const integer_matrix& M, const 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 $ \not=$ 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(const integer_matrix& M, const 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 $ \not=$ 0.
Precondition M.dim1() == b.dim().

bool linear_solver(const integer_matrix& M, const integer_vector& b, integer_vector& x, integer& D)
    as above, but without the witness c
Precondition M.dim1() == b.dim().

bool is_solvable(const integer_matrix& M, const integer_vector& b)
    determines whether the system M*x = b is solvable
Precondition M.dim1() == b.dim().

bool homogeneous_linear_solver(const 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(const 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(const 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(const integer_matrix& M)
    returns the rank of matrix M

ostream& ostream& O « const integer_matrix& 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(n3), 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 cTA = 0 and cTb $ \not=$ 0.


next up previous contents index
Next: Rational Vectors ( rat_vector Up: Number Types and Linear Previous: Vectors with Integer Entries   Contents   Index
root 2008-01-09