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/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) ![]() |
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 ![]() 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 ![]() 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(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 0.