;; Compute the determinant of a square matrix given by a list of lists ;; e.g. ((a b)(c d)) is a 2 by 2. This first program assumes the top ;; left element is non-zero, and that in subsequent Gaussian ;; elimination, the top left (diagonal element) remains nonzero. Note ;; that if it is zero, either the determinant itself is zero or row ;; operations can make this top left element non-zero. To see one way ;; to modify the algorithm see Knuth vol 2 p 479. Numerically, this ;; is not a competitively fast numeric program because it reduces the ;; determinant of an nxn matrix to constructing an associated ;; (n-1)x(n-1) matrix and computing its determinant. A normal ;; elimination procedure would not construct new matrices, but compute ;; in place. (defun det(m);; ordinary numerical version (cond ((null m) 0) ; 0 size matrix? ((null (cdr m)) (caar m)) ;single element (t (let ((pivot (caar m));; x11 (row1 (cdar m)));; (x12, x13 ...) (* pivot (det (mapcar #'(lambda(row col1);; for each row (let ((mult ( / col1 pivot))) (mapcar #'(lambda (h k) (- h (* mult k)));; (- x22 (* (/ x21 x11) x12)) row;; (x22 x23 ...) row1))) (mapcar #'cdr (cdr m));; ((x22 x23 ..)(x32 x33 ..)..) (mapcar #'car (cdr m));; (x21, x31, ))))))) (defun det-s(m) ;; symbolic version (framevars (det-s1 m))) (defun det-s1(m) (cond ((null m) 0) ((null (cdr m)) (caar m)) ;; the clause below is unnecessary, but results in simpler code ((null (cddr m)) (-s (*s (caar m)(cadadr m));; 2X2 case (*s (cadar m)(caadr m)))) (t (let ((pivot (newname `(/ -1 ,(caar m))));; x11 (row1 (cdar m)));; (x12, x13 ...) (newname (*s (caar m) (det-s1 (mapcar #'(lambda(row col1);; for each row (let ((mult (newname(*s col1 pivot)))) (mapcar #'(lambda (h k) ;; (- x22 (* (/ x21 x11) x12)) (newname (+s h (*s mult k)))) row;; (x22 x23 ...) row1))) (mapcar #'cdr (cdr m));; ((x22 x23 ..)(x32 x33 ..)..) (mapcar #'car (cdr m));; (x21, x31, )))))))) ;; this is an alternative determinant program for numerical ;; matrices. Expansion by minors. (defun detm(m) (cond ((null m) 0) ((null (cdr m)) (caar m)) ;; go through minors of first row ;; need to put signs in there (t (newname (let ((sum 0)) (dotimes (i (length (car m)) sum) (setf sum (+ sum (* (elt (car m) i) (expt -1 i) (detm (mapcar ;remove the ith element from each line #'(lambda(line) (remove t line :start i :end (+ i 1) :test #'(lambda(r s)r))) (cdr m)))))))))))) ;;symbolic, by minors (defun detm-s(m)(framevars (detm-s2 m))) (defun detm-s2(m) (cond ((null m) 0) ((null (cdr m)) (caar m)) ;; go through minors of first row (t (newname (let ((sum 0)) (dotimes (i (length (car m)) sum) (setf sum (+s sum (*s (elt (car m) i) (expt -1 i) (newname (detm-s2 (mapcar ;remove the ith element from each line #'(lambda(line) (remove t line :start i :end (+ i 1) :test #'(lambda(r s)r))) (cdr m)))))))))))))