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^{T}A = 0 and c^{T}b! = 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 M_{i, 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 M^{T} (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) 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 c^{T}*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
c^{T}*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
c^{T}*M = 0 and
c^{T}*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(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
c^{T}*M = 0 and
c^{T}*b 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(n^{3}), 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^{T}A = 0 and c^{T}b 0.