```(* ----------------------------------------------------------------------------
* \$Id: LINALGI.md,v 1.3 1995/11/05 09:21:55 kredel Exp \$
* ----------------------------------------------------------------------------
* This file is part of MAS.
* ----------------------------------------------------------------------------
* Copyright (c) 1989 - 1992 Universitaet Passau
* ----------------------------------------------------------------------------
* \$Log: LINALGI.md,v \$
* Revision 1.3  1995/11/05 09:21:55  kredel
*
* Revision 1.2  1992/02/12  17:33:08  pesch
* Moved CONST definition to the right place
*
* Revision 1.1  1992/01/22  15:12:31  kredel
* Initial revision
*
* ----------------------------------------------------------------------------
*)

DEFINITION MODULE LINALGI;

(* MAS Linear Algebra Integer Definition Module. *)

(*-------------------------------------------------------------------------

Programmierpraktikum SS 1990: JUEGEN MUELLER, Heinz Kredel

Contents: Standartoperations for matrix and vector manipulations,
Gaussian elimination, LU-Decomposition, Solve,
Inversion, Nullspace, Determinant.

Stand : 27.09.90, Juergen Mueller
from then date of the file, Heinz Kredel

Remarks: A vector is represented as a list of elements.
The elements may be integers or rational numbers.
A matix is represented as a list of vectors.
In most circumstances these vectors are interpreted row
vectors, but they can also be interpreted as column vectors.

--------------------------------------------------------------------------*)

FROM MASSTOR IMPORT LIST;

CONST rcsid = "\$Id: LINALGI.md,v 1.3 1995/11/05 09:21:55 kredel Exp \$";

PROCEDURE IUM(m, n : LIST): LIST;
(*Integer unit matrix. m, n integer. An (m x n) integer unit
matrix is returned. *)

PROCEDURE IVWRITE(A : LIST);
(*Integer vector write. A is an integer vector. A is written
to the output stream. *)

PROCEDURE IMWRITE(A : LIST);
(*Integer matrix write. A is an integer matrix. A is written
to the output stream. *)

PROCEDURE IVVDIF(A, B : LIST): LIST;
(*Integer vector difference. A and B are integer vectors.
The integer vector C = A - B is returned. *)

PROCEDURE IKM(A, B : LIST): LIST;
(*Integer vector component product. IKM returns the difference of
the product of the integer vector A with FIRST(B) and the product of
the integer vector B with FIRST(A). C = A * FIRST(B) - B * FIRST(A).
C is an integer vector. *)

PROCEDURE IVVSUM(A, B : LIST): LIST;
(*Integer vector vector sum. A and B are integer vectors.
An integer vector C = A + B is returned. *)

PROCEDURE IVSVSUM(A, B : LIST): LIST;
(*Integer vector scalar and vector sum. A and B are integer vectors.
An integer vector C = A + FIRST(B) is returned. *)

PROCEDURE IVSSUM(A : LIST): LIST;
(*Integer vector scalar sum. A is an integer vector. An integer
C = a1 + a2 + ... + an is returned. *)

PROCEDURE IVSVPROD(A, B : LIST): LIST;
(*Integer vector scalar and vector product. A and B are integer vectors.
An integer vector C = (a1*FIRST(B), ..., an*FIRST(B) ) is returned. *)

PROCEDURE IVVPROD(A, B : LIST): LIST;
(*Integer vector vectors product. A and B are integer vectors.
An integer vector C = (a1*b1, ..., an*bn) is returned. *)

PROCEDURE IVSPROD(A, B : LIST): LIST;
(*Integer vector scalar product. A and B are integer vectors.
An integer C = a1*b1 + ... + an*bn is returned. *)

PROCEDURE IVMAX(M : LIST): LIST;
(*Integer vector maximum norm. M is an integer vector.
An integer a = maximum absolute value M(i) is returned. *)

PROCEDURE IVLC(a, A, b, B : LIST): LIST;
(*Integer vector linear combination. A and B are integer vectors.
a and b are integers. An integer vector C = a*A + b*B is returned. *)

PROCEDURE IVSQ(a, A: LIST): LIST;
(*Integer vector scalar quotient. A is an integer vector.
a is an integer. An integer vector C = A/a is returned.
a must divide each element of A exactly.  *)

PROCEDURE IVFRNV(A: LIST): LIST;
(*Integer vector from rational number vector. A is a rational
number vector. A is muliplied by a common multiple of its
denominators, then the denominators are removed. An integer
vector C = lcm(denom(A)) * A is returned.  *)

PROCEDURE IVFRNV1(A, B : LIST; VAR C, D: LIST);
(*Integer vector from rational number vector. A and B are
rational number vectors. A and B are muliplied by a common
multiple of their denominators, then the denominators are
removed. C and D are integer vectors, such that
C = lcm(denom(A),denom(B))*A and D = lcm(denom(A),denom(B))*B. *)

PROCEDURE IMPROD(A, B : LIST): LIST;
(*Integer matrix product. A and B are integer matrices.
An integer matrix C = A * B is returned, if the number of
coloums of A is equal to the number of rows of B,
otherwise the empty matrix is returned. *)

PROCEDURE IMSUM(A, B : LIST): LIST;
(*Integer matrix sum. A and B are integer matrices.
An integer matrix C = A + B is returned. *)

PROCEDURE IMDIF(A, B : LIST): LIST;
(*Integer matrix difference. A and B are integer matrices.
An integer matrix C = A - B is returned. *)

PROCEDURE ISMPROD(A, B : LIST): LIST;
(*Integer scalar and matrix product. A is an integer matrix.
B is an integer. An integer matrix C = A * B is returned. *)

PROCEDURE IMMAX(M : LIST): LIST;
(*Integer matrix maximum norm. M is an integer matrix.
An integer a = maximum absolute value M(i,j) is returned. *)

PROCEDURE IMFRNM(A : LIST): LIST;
(*Integer matrix from rational number matrix. A is a rational
number row matix. The rows of A are muliplied by a common
multiple of its denominators, then the denominators are
removed. An integer matix C is returned, such that for
all rows C(i) = lcm(denom(A(i))) * A(i). *)

PROCEDURE IMFRNM1(A, B : LIST; VAR C, D: LIST);
(*Integer matrix from rational number matrix. A is a rational
number row matix. B is a rational number column matix.
The rows of A and the rows of B are muliplied by
a common multiple of their denominators, then the
denominators are removed. C and D are integer matices,
such that C(i) = lcm(denom(A(i)),B(i)) * A(i) and
D(i) = lcm(denom(A(i)),B(i)) * B(i). *)

PROCEDURE IMGELUD(M : LIST; VAR L, U: LIST);
(*Integer matrix Gaussian elimination LU-decomposition.
M is an integer matrix represented rowwise. L is a lower
triangular integer matrix represented columnwise.
U is an upper triangular integer matrix represented rowwise.
M = L * U for appropriate modifications of L and U. The pivot
operations and exact division factors are also recorded in L. *)

PROCEDURE IMLT(L, b : LIST): LIST;
(*Integer lower triangular matrix transformation.
L is a lower triangular integer matrix represented
columnwise as generated by IMGELUD. b is an integer vector.
An integer vector u = L * b is returned, such that
if M * x = b and M = L * U, then U * x = u. *)

PROCEDURE IMUT(U, b : LIST): LIST;
(*Integer upper triangular matrix transformation.
U is an upper triangular integer matrix represented rowwise
as generated by IMGELUD. b is an integer vector
b = L * b' as generated by IMLT. A rational number (!) vector x,
such that U * x = b is returned. If no such x exists, then an
empty vector is returned. If more than one such x exists, then

PROCEDURE IMGE(M : LIST): LIST;
(*Integer matrix Gaussian elimination. M is a (n x m) integer
matrix. A (n x m) integer matrix resulting from Gaussian
elimination is returned. IMGELUD is called. *)

PROCEDURE IMSDS(L, U, b : LIST): LIST;
(*Integer matrix solve decomposed system. L is a lower
triangular integer matrix represented columnwise, U is an upper
triangular integer matrix represented rowwise. L and U as
generated by IMGELUD. If M = L * U, then a rational number (!)
vector x, such that M * x = b is returned. If no such x exists,
then an empty vector is returned. If more than one such x exists,

PROCEDURE RNMINVI(A : LIST): LIST;
(*Rational number matrix inversion, integer algorithm. A is a
rational number matrix represented rowwise. If it exists,
the inverse matrix of A is returned, otherwise an empty matrix
is returned. The integer Gaussian elimination IMGELUD is used. *)

PROCEDURE IMUNS(U : LIST): LIST;
(*Integer matrix upper triangular matrix solution null space.
U is an upper triangular integer matrix represented rowwise
as generated by IMGELUD. A matrix X of linear independent rational
number vectors x is returned, such that for each x in X, U * x = 0 holds.
If only x = 0 satisfies the condition U * x = 0, then the
matrix X is empty. *)

PROCEDURE IMDETL(M : LIST): LIST;
(*Integer matrix determinant, using Laplace expansion.
M is an integer matrix. The determinant of M is returned. *)

PROCEDURE IMDET(M : LIST): LIST;
(*Integer matrix determinant, using Gaussian elimination.
M is an integer matrix. The determinant of M is returned. *)

END LINALGI.

(* -EOF- *)
```