Matrix Operations

/*-------------------------------------------------------------------------*/
/* Matrix Multiplication                                                   */
/*-------------------------------------------------------------------------*/

/* matrix_times_matrix(Matrix1, Matrix2, Matrix3) is true if Matrix3 is    */
/*   the result of multiplying Matrix1 by Matrix2.  The matrices are lists */
/*   of rows, each row being a list of numbers.                            */
/*   e.g. matrix_times_matrix([[1,2],[3,4],[5,6]],                         */
/*                            [[1,2,3,4],[5,6,7,8]],                       */
/*                            [[11,14,17,20],[23,30,37,44],[35,46,57,68]]).*/
matrix_times_matrix([], _, []).
matrix_times_matrix([Xs|Xss], Yss, [Zs|Zss]):-
  vector_times_matrix(Xs, Yss, Zs),
  matrix_times_matrix(Xss, Yss, Zss).

/* vector_times_matrix(Vector1, Matrix, Vector2) is true if Vector2 is the */
/*   result of multiplying Vector1 by Matrix.  Vector1 and Vector2 are     */
/*   lists of numbers.  Matrix is a list of rows, each row being a list of */
/*   numbers.                                                              */
/*   e.g. vector_times_matrix([1,2], [[1,2,3],[5,6,7]], [11,14,17]).       */
vector_times_matrix(Xs, Yss, Zs):-vector_times_matrix_1(Yss, Xs, Zs).

vector_times_matrix_1([], _, []).
vector_times_matrix_1(Yss, Xs, [Z|Zs]):-
  heads_and_tails(Yss, Hs, Tss),
  inner_product(Xs, Hs, 0, Z),
  vector_times_matrix_1(Tss, Xs, Zs).

/* inner_product(Xs, Ys, Z0, Z) is true if Z is the sum of Z0 and the      */
/*   inner product of the vectors represented by the lists of numbers Xs   */
/*   and Ys.                                                               */
inner_product([], [], Z, Z).
inner_product([X|Xs], [Y|Ys], Z0, Z):-
  Z1 is X * Y + Z0, 
  inner_product(Xs, Ys, Z1, Z).

/*-------------------------------------------------------------------------*/
/* The Determinant of a Matrix                                             */
/*-------------------------------------------------------------------------*/

/* determinant(Matrix, Scalar) is true if Scalar is the value of the       */
/*   determinant of the Matrix.  The Matrix is represented by a list of    */
/*   rows, each row being a list of numbers.                               */
/*   e.g. determinant([[1,2,3],[4,5,6],[7,8,10]], -3).                     */
determinant([[A]], A):-!.  
determinant(Ass, X):-
  heads_and_tails(Ass, Hs, Tss),
  determinant_1(Hs, Tss, 1, 1, 0, X).  

/*   e.g. determinant_1([1,4,7], [[2,3],[5,6],[8,10]], 1, 1, 0, -3).       */
determinant_1([], _, _, _, X, X).
determinant_1([H|Hs], Tss, N, Sign, X0, X):-
  delete_nth_element(N, Tss, Uss),
  determinant(Uss, X1),
  X2 is X0 + Sign * H * X1,
  N1 is N + 1,
  Sign1 is -Sign,
  determinant_1(Hs, Tss, N1, Sign1, X2, X).

/*-------------------------------------------------------------------------*/
/* The Transpose of a Matrix                                               */
/*-------------------------------------------------------------------------*/

/* transpose(Matrix1, Matrix2) is true if Matrix2 is the transpose of      */
/*   Matrix1.  Each Matrix is represented by a list of rows, each row      */
/*   being a list of numbers.                                              */
/*   e.g. transpose([[1,2,3],[4,5,6]], [[1,4],[2,5],[3,6]]).               */
transpose([], []).
transpose([Xs|Xss], [Ys|Yss]):-
  heads_and_tails([Xs|Xss], Ys, Xss1),
  transpose(Xss1, Yss).

/*-------------------------------------------------------------------------*/
/* General Predicates                                                      */
/*-------------------------------------------------------------------------*/

/* is_matrix(Xs) is true if Xs is a list of lists such that each list      */
/*   contains the same number of elements.                                 */
/* This procedure should be used to verify the structure of matrices prior */
/*   to invoking one of the above procedures.                              */
is_matrix([Xs|Xss]):-is_matrix_1(Xss, Xs).

is_matrix_1([], _).
is_matrix_1([Xs|Xss], Ys):-
  same_length(Xs, Ys),
  is_matrix_1(Xss, Ys).
  
same_length([], []).
same_length([_|Xs], [_|Ys]):-
  same_length(Xs, Ys).

/* heads_and_tails(ListOfLists, Heads, Tails) is true if Heads is the list */
/*   of the heads of the members of the ListOfLists, and Tails is the list */
/*   of the (non-empty) tails of the members of the ListOfLists.           */
/*   e.g. heads_and_tails([[1,2,3],[4,5,6]], [1,4], [[2,3],[5,6]]).        */
/*   e.g. heads_and_tails([[1,2,3],[4]],     [1,4], [[2,3]]).              */
heads_and_tails([], [], []).
heads_and_tails([[X]|Xss], [X|Ys], Zss):-
  heads_and_tails(Xss, Ys, Zss).
heads_and_tails([[X,X1|Xs]|Xss], [X|Ys], [[X1|Xs]|Zss]):-
  heads_and_tails(Xss, Ys, Zss).

/* delete_nth_element(N, List1, List2) is true if List2 is the result of   */  
/*   deleting the N-th (base 1) element from List1.                        */
/*   e.g. delete_nth_element(2, [4,5,6], [4,6]).                           */
delete_nth_element(1, [_|As], As):-!.
delete_nth_element(N, [A|As], [A|Bs]):-
  N > 1,
  N1 is N - 1,
  delete_nth_element(N1, As, Bs).

LPA Index     Home Page