Topic: -={ Challenge }=- Matrix Determinant

[Lee Mac]

The Challenge:

To create a program that will calculate the determinant of any nxn matrix with entries in the Real space.

The program should take one argument - the matrix - which should be formulated as a list, for example:

2x2 Matrix:

Code: [Select]

'( (1 2)
   (3 4) )

3x3 Matrix:

Code: [Select]

'( (1 2 3)
   (3 4 5)
   (5 6 7) )

As a little background on Matrices and Determinants....

A Matrix (not the film) is purely an array of entries which can represent vectors (usually), coefficients of systems of equations, and other such quantities. They are used in a huge range of applications... from solving systems of simultaneous/differential equations... to applying transformations to vectors.

The determinant is also a useful calculation... geometrically, it can be thought of as the area of a parallelogram, the sides of which are the vectors of the matrix. And this can be extended to 3-dimensions with a 3x3 matrix, and thought of as the parallelepiped formed by the 3 vectors contained in the matrix.

The determinant is also a necessary element when calculating the Inverse of a matrix - a necessary component in matrix arithmetic.

Methods for Calculation...

I believe the most common method for calculating the determinant is by Laplace's Formula:



For a matrix of size n. Where, when calculating the determinant along row i, M_ij is the determinant of the matrix formed by removing row i and column j from the orignal matrix.

This is the route that I have followed.

But there are many other methods that can be used... many of which are outlined here.


My Offering:

Code: [Select]

;; Matrix Determinant  -  Lee Mac
;; Args: m - nxn matrix
 
(defun detm ( m / i j )
    (setq i -1 j 0)
    (cond
        (   (null (cdr  m)) (caar m))
        (   (null (cddr m)) (- (* (caar m) (cadadr m)) (* (cadar m) (caadr m))))
        (   (apply '+
                (mapcar
                   '(lambda ( c ) (setq j (1+ j))
                        (* c (setq i (- i))
                            (detm
                                (mapcar
                                   '(lambda ( x / k )
                                        (setq k 0)
                                        (vl-remove-if '(lambda ( y ) (= j (setq k (1+ k)))) x)
                                    )
                                    (cdr m)
                                )
                            )
                        )
                    )
                    (car m)
                )
            )
        )
    )
)

Enjoy!

Lee

[CAB]

We're not helping you with your home work. 

Just kidding, Sorry to say this math exceeds my knowledge and perhaps my understanding.
I need more pictures at the elementary level.

[TimSpangler]

Just kidding, Sorry to say this math exceeds my knowledge and perhaps my understanding.
I need more pictures at the elementary level.

Yeah..What he said....

[gile]

Hi,

Here's my way (from here)

Code: [Select]

;; COFACT (gile)
;; Returns the cofactor associated to ij item of a matrix
;;
;; Arguments
;; i = row index (first row = 1)
;; j = column index (first column = 1)
;; m = a matrix

(defun cofact (i j m)
  (* (determ
       (remove-i (1- i) (mapcar '(lambda (x) (remove-i (1- j) x)) m))
     )
     (expt -1 (+ i j))
  )
)

;; DETERM (gile)
;; Returns the déterminant of a matrix
;;
;; Argument: a matrix

(defun determ (m)
  (if (= 2 (length m))
    (- (* (caar m) (cadadr m)) (* (caadr m) (cadar m)))
    ((lambda (r n)
       (apply '+
              (mapcar '(lambda (x) (* x (cofact 1 (setq n (1+ n)) m))) r)
       )
     )
      (car m)
      0
    )
  )
)

;; REMOVE-I (gile)
;; Returns the list but item at specified index (first item = 0)
;;
;; Arguments: the index of item to be remove and the list

(defun remove-i (i l)
  (if (or (zerop i) (null l))
    (cdr l)
    (cons (car l) (remove-i (1- i) (cdr l)))
  )
)

[Strucmad]

I wish my code skills were more advanced, I would love to play...

why not throw in some 2nd order non-homogeneous DE's with constant coefficients while your at it
or maybe some eigenvalue characteristic polynomials....(I love doing them by hand).

[It's Alive!]

AcGeMatrix3d::det(); 

[Lee Mac]

I wish my code skills were more advanced, I would love to play...

why not throw in some 2nd order non-homogeneous DE's with constant coefficients while your at it
or maybe some eigenvalue characteristic polynomials....(I love doing them by hand).

Haha... right up my street.. I loved the DE course I took in my first year 

AcGeMatrix3d::det();

Haha cheeky    But nxn? 

We're not helping you with your home work. 

Just kidding, Sorry to say this math exceeds my knowledge and perhaps my understanding.
I need more pictures at the elementary level.

Funny you should say that actually Alan - I do have an assignment for my C-programming module that asks to calculate the determinant of a 3x3 matrix... which is where I got the inspiration for this challenge...   

I wondered how many of you would be interested - I saw a similar thread on here about Matrix Mathematics, but it wasn't taken very far... I knew that Gile would rise to the challenge - I've seen his mathematical genius before...   

[ElpanovEvgeniy]

I hope, I not strongly was late with the answer?

Code: [Select]

(defun det-g (l)
 ;; By ElpanovEvgeniy
 (cond
  ((null l) 1)
  ((zerop (caar l)) 0)
  ((* (caar l)
      (det-g (mapcar '(lambda (a)
                       (mapcar '(lambda (b c) (- b (* c (/ (car a) (float (caar l))))))
                               (cdr a)
                               (cdar l)
                       ) ;_  mapcar
                      ) ;_  lambda
                     (cdr l)
             ) ;_  mapcar
      ) ;_  det
   ) ;_  *
  )
 ) ;_  cond
)

[ElpanovEvgeniy]

version 2:

Code: [Select]

(defun det-g (l)
 ;; By ElpanovEvgeniy
 (cond ((null l) 1)
       ((zerop (caar l)) 0)
       ((* (caar l)
           (det-g (mapcar '(lambda (a / d)
                            (setq d (/ (car a) (float (caar l))))
                            (mapcar '(lambda (b c) (- b (* c d))) (cdr a) (cdar l))
                           ) ;_  lambda
                          (cdr l)
                  ) ;_  mapcar
           ) ;_  det
        ) ;_  *
       )
 ) ;_  cond
) ;_  defun

[VovKa]

and that's why i love Evgeniy

[Lee Mac]

Wow! Concise solution - nice one Evgeniy 

[ElpanovEvgeniy]

Wow! Concise solution - nice one Evgeniy 

If it is necessary concise:

Code: [Select]

(defun d(l)(if l(*(caar l)(d(mapcar'(lambda(a)(mapcar'(lambda(b c)(- b(* c(/(car a)1.(caar l)))))(cdr a)(cdar l)))(cdr l))))1))

[Lee Mac]

Haha - now thats showing off   

[ElpanovEvgeniy]

Haha - now thats showing off   

I am not assured, that I can really write more shortly.

[qjchen]

Wow! Concise solution - nice one Evgeniy 

If it is necessary concise:

Code: [Select]

(defun d(l)(if l(*(caar l)(d(mapcar'(lambda(a)(mapcar'(lambda(b c)(- b(* c(/(car a)1.(caar l)))))(cdr a)(cdar l)))(cdr l))))1))

Wow, all of you are so excellent.
Last night I thought that we should challenge  determinant, a matrix and recursive problem. But after I searched, I was shocked by your codes, especially Evgeniy's.
My solution is tooooooo longer.

Thank you all~