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~

[chlh_jd]

all Great !  

before this , I have been use Gile's deter function , it's so fast ,Thanks Gile !
Evgeniy's fastest , Thank you !
But now I test the matrix (det-g '((1 2 3) (2 4 5) (3 5 6))) , It take wrong result  0 , not the corret -1.

[Brick_top]

The sad part is that I don't even know what this is for 

edit - even sadder is that I didn't  read the explanation in the first post

edit 2 - now that I read it I don't understand it... Unfortunately I could go on and on

sorry for the off topic

[SOFITO_SOFT]

Code: [Select]

If it is necessary concise:
(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))

BravoooOOOO !!! 

[chlh_jd]

Hi Sofito_soft
Hi ElpanovEvgeniy
Is it my PC problem ? I test the matrix '((1 2 3) (2 4 5) (3 5 6)) , however , your functions 'det-g or 'd din't give the correct result 

[SOFITO_SOFT]

Hello people of the swamp:
chlh_jd:
proceedings are divisions, so the numbers to drive must be real, not integers.
Please try with '((1.0 2. 3.) (2. 4. 5.) (3. 5. 6.))   
Greetings.

[SOFITO_SOFT]

Hello people of the swamp:
chlh_jd:
not all determinants also has a solution!
For example, if 2 lines are dependent, can not be resolved.
((1 2 3) (3 6 9 ).....) has no solution because (1 2 3) x 3 = (3 6 9). They are dependent!
There are more cases that has no solution. 
Greetings 

[gile]

Hello people of the swamp:
chlh_jd:
not all determinants also has a solution!
For example, if 2 lines are dependent, can not be resolved.
((1 2 3) (3 6 9 ).....) has no solution because (1 2 3) x 3 = (3 6 9). They are dependent!
There are more cases that has no solution. 
Greetings 

It seems to me that in these cases the routine have to return 0.0.

Anyway, here's another solution using Gauss pivot (the matrix determinant is equal to the product of all the pivots used in a Gauss-Jordan elimination)
This method should be much more faster with large dimension matrices.

Code: [Select]

(defun gc:determ (mat / col piv row res det)
  (setq res 1.)
  (while (< 2 (length mat))
    (setq col (mapcar '(lambda (x) (abs (car x))) mat))
    (repeat (vl-position (apply 'max col) col)
      (setq mat (append (cdr mat) (list (car mat))))
    )
    (if (equal (setq piv (float (caar mat))) 0.0 1e-13)
      (setq mat nil
    res 0.0
      )
      (setq row (mapcar '(lambda (x) (/ x piv)) (car mat))
    mat (mapcar
  '(lambda (r / e)
     (setq e (car r))
     (cdr (mapcar '(lambda (x n) (- x (* n e))) r row))
   )
  (cdr mat)
)
    res (* piv res)
      )
    )
  )
  (setq det (- (* (caar mat) (cadadr mat)) (* (caadr mat) (cadar mat))))
  (if (equal 0. det 1e-14)
    0.
    (* res det)
  )
)

[SOFITO_SOFT]

Indeed Gille:
not all determinants also has a solution! <<<< with the LSP program....
For example, if 2 lines are dependent, can not be resolved <<<< with the LSP program....
As you say, should return 0
Regards.

[gile]

Indeed Gille:
not all determinants also has a solution! <<<< with the LSP program....
For example, if 2 lines are dependent, can not be resolved <<<< with the LSP program....
As you say, should return 0
Regards.

Did you try all the upper routines with: '((1. 2. 3.) (3. 6. 9.) (7. 5. 3.)) for example ?
All resolve the problem returning 0.0

[chlh_jd]

Hi  SOFITO_SOFT
I've test in real , it take a wrong result yet .
Hi All ,
How to invers this matrix :

Code: [Select]

'((7.0 0.0 -3.0 2.0 0.0 -4.0 -4.0 2.0) (0.0 13.0 2.0 -1.0 -4.0 0.0 2.0 -12.0)
(-3.0 2.0 7.0 -4.0 -4.0 2.0 0 0) (2.0 -1.0 -4.0 13.0 2.0 -12.0 0 0) (0.0 -4.0
-4.0 2.0 7.0 0.0 -3.0 2.0) (-4.0 0.0 2.0 -12.0 0.0 13.0 2.0 -1.0) (-4.0 2.0 0 0
-3.0 2.0 7.0 -4.0) (2.0 -12.0 0 0 2.0 -1.0 -4.0 13.0))
It's a matrix of a cantilever beam  for Finite element analysis , It can be inversed by 'MatLab' .
However , all above codes returns nil or 0.0 ?
Therefore, is there some way to use scientific notation to represent  intermediate values or  results ?

[jbuzbee]

Please stop - you're all scaring me! 

 

[SOFITO_SOFT]

glubssss ....I do not get to much .... I use "Calc3D ".....
greetings

[chlh_jd]

Excellent Gile !
Thank you for your Gauss Way determent fun .

[chlh_jd]

Is it can change a lit ? Because it will get a null 'mat' in some case , E.G. the matrix in 'Reply #25 on' .

Code: [Select]

(setq det (- (* (caar mat) (cadadr mat)) (* (caadr mat) (cadar mat))))


Code: [Select]

(if mat (setq det (- (* (caar mat) (cadadr mat)) (* (caadr mat) (cadar mat)))) (setq det 0.0))


[ribarm]

I've added my new version here :
http://www.theswamp.org/index.php?topic=45666.msg597622#msg597622

Regards, M.R.