Home Online Manual
Back: luinverse
Forward: max
FastBack: Functions and system variables
FastForward: Control structures
Up: Functions
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

5.1.81 lusolve

lusolve ( matrix_expression, matrix_expression, matrix_expression, matrix_expression )
Computes all solutions of a linear equation system A*x = b, if solvable
The (m x n matrix A must be given by its LU-decomposition, that is, by three matrices P, L, and U, in this order, which satisfy
- P * A = L * U,
- P is an (m x m) permutation matrix, i.e., its rows/columns form the standard basis of K^m,
- L is an (m x m) matrix in lower triangular form with all diagonal entries equal to 1, and
- U is an (m x n) matrix in upper row echelon form.
The fourth argument, b, is expected to be an (m x 1) matrix.

list Q=lusolve(P,L,U,b); fills the list Q with either one entry = 0 (signaling that A*x=b has no solution), or with the three entries 1, x, H, where x is any (n x 1) solution of the given linear system, and H is a matrix the columns of which span the solution space of the homogeneous linear system. (I.e., ncols(H) is the dimension of the solution space.)
If there is exactly one solution, then H is the 1x1 matrix with entry zero.

The method will give a warning if the matrices violate the above conditions regarding row and column numbers, or if the number of rows of the vector b does not equal m.
The method expects matrices with entries coming from the ground field of the given polynomial ring, only.

  ring r=0,(x),dp;
  matrix A[4][4]=1,1,1,0,1,2,3,1,1,3,5,2,1,4,7,3;
  matrix b[4][1]=2,5,8,11;
  list L=ludecomp(A);
  list Q=lusolve(L[1],L[2],L[3],b);
  if (Q[1] == 1)
    "one solution:";
    "check whether result is correct (iff next is zero vector):";
    if ((nrows(Q[3])==1) and (ncols(Q[3])==1) and (Q[3][1,1]==0))
    { "printed solution is the only solution to given linear system" }
      "homogeneous solution space is spanned by columns of:";
==> one solution:
==> -1,
==> 3, 
==> 0, 
==> 0  
==> check whether result is correct (iff next is zero vector):
==> 0,
==> 0,
==> 0,
==> 0 
==> homogeneous solution space is spanned by columns of:
==> -1,-1,
==> 1, 2, 
==> 0, -1,
==> -1,0  
See ludecomp.