;; 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)))))))))))))