Author Topic: -={ Challenge }=- Matrix Determinant  (Read 14262 times)

0 Members and 1 Guest are viewing this topic.

Lee Mac

  • Seagull
  • Posts: 12910
  • London, England
-={ Challenge }=- Matrix Determinant
« on: November 12, 2009, 08:40:39 AM »
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, Mij 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
« Last Edit: November 12, 2013, 11:58:38 AM by Lee Mac »

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
Re: -={ Challenge }=- Matrix Determinant
« Reply #1 on: November 12, 2009, 10:49:17 AM »
We're not helping you with your home work.  :evil:

Just kidding, Sorry to say this math exceeds my knowledge and perhaps my understanding.
I need more pictures at the elementary level.
I've reached the age where the happy hour is a nap. ()
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

TimSpangler

  • Water Moccasin
  • Posts: 2010
  • CAD Naked!!
Re: -={ Challenge }=- Matrix Determinant
« Reply #2 on: November 12, 2009, 11:22:34 AM »
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.... :lmao:
ACA 2015 - Windows 7 Pro
All Comments and Content by TimSpangler, Copyright 2016

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: -={ Challenge }=- Matrix Determinant
« Reply #3 on: November 12, 2009, 01:19:52 PM »
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)))
  )
)
« Last Edit: November 12, 2009, 02:12:04 PM by gile »
Speaking English as a French Frog

Strucmad

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #4 on: November 12, 2009, 04:39:29 PM »
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 :-D
or maybe some eigenvalue characteristic polynomials....(I love doing them by hand).

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8690
  • AKA Daniel
Re: -={ Challenge }=- Matrix Determinant
« Reply #5 on: November 13, 2009, 04:44:41 AM »
AcGeMatrix3d::det();  :evil:

Lee Mac

  • Seagull
  • Posts: 12910
  • London, England
Re: -={ Challenge }=- Matrix Determinant
« Reply #6 on: November 13, 2009, 07:27:52 AM »
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 :-D
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  :-)

Quote
AcGeMatrix3d::det();

Haha cheeky  :-P  But nxn?  :wink:

Quote
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...   :evil:

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...   :wink:

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: -={ Challenge }=- Matrix Determinant
« Reply #7 on: November 16, 2009, 08:15:53 AM »
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

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: -={ Challenge }=- Matrix Determinant
« Reply #8 on: November 16, 2009, 08:21:44 AM »
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

  • Water Moccasin
  • Posts: 1628
  • Ukraine
Re: -={ Challenge }=- Matrix Determinant
« Reply #9 on: November 16, 2009, 01:02:03 PM »
and that's why i love Evgeniy :)

Lee Mac

  • Seagull
  • Posts: 12910
  • London, England
Re: -={ Challenge }=- Matrix Determinant
« Reply #10 on: November 16, 2009, 01:34:56 PM »
Wow! Concise solution - nice one Evgeniy  :lol:

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: -={ Challenge }=- Matrix Determinant
« Reply #11 on: November 16, 2009, 01:43:28 PM »
Wow! Concise solution - nice one Evgeniy  :lol:

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

  • Seagull
  • Posts: 12910
  • London, England
Re: -={ Challenge }=- Matrix Determinant
« Reply #12 on: November 16, 2009, 01:47:08 PM »
Haha - now thats showing off  :-P  :evil:

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: -={ Challenge }=- Matrix Determinant
« Reply #13 on: November 16, 2009, 01:53:58 PM »
Haha - now thats showing off  :-P  :evil:

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

qjchen

  • Bull Frog
  • Posts: 285
  • Best wishes to all
Re: -={ Challenge }=- Matrix Determinant
« Reply #14 on: January 25, 2011, 08:01:10 PM »
Wow! Concise solution - nice one Evgeniy  :lol:

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~
http://qjchen.mjtd.com
My blog http://chenqj.blogspot.com (Chinese, can be translate into English)

chlh_jd

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #15 on: January 26, 2011, 03:57:15 AM »
all Great !  :-o

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.
« Last Edit: January 26, 2011, 04:09:18 AM by chlh_jd »

Brick_top

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #16 on: January 26, 2011, 04:40:53 AM »
The sad part is that I don't even know what this is for  :oops:

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
« Last Edit: January 26, 2011, 05:30:30 AM by Brick_top »

SOFITO_SOFT

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #17 on: January 26, 2011, 08:29:03 AM »
Quote
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 !!!  :lol:

chlh_jd

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #18 on: February 05, 2011, 08:18:09 AM »
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  :angel:

SOFITO_SOFT

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #19 on: February 06, 2011, 07:44:40 AM »
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.))   :-o
Greetings. :-)

SOFITO_SOFT

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #20 on: February 06, 2011, 07:54:10 AM »
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.  :oops:
Greetings  :-)

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: -={ Challenge }=- Matrix Determinant
« Reply #21 on: February 06, 2011, 08:40:09 AM »
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.  :oops:
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)
  )
)
« Last Edit: February 06, 2011, 01:01:21 PM by gile »
Speaking English as a French Frog

SOFITO_SOFT

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #22 on: February 06, 2011, 03:14:40 PM »
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

  • Gator
  • Posts: 2507
  • Marseille, France
Re: -={ Challenge }=- Matrix Determinant
« Reply #23 on: February 06, 2011, 03:32:34 PM »
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
Speaking English as a French Frog

chlh_jd

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #24 on: February 09, 2011, 11:02:52 AM »
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 ?
« Last Edit: February 09, 2011, 11:12:43 AM by chlh_jd »

jbuzbee

  • Swamp Rat
  • Posts: 851
Re: -={ Challenge }=- Matrix Determinant
« Reply #25 on: February 09, 2011, 02:02:36 PM »
Please stop - you're all scaring me!  :|

 :lol:
James Buzbee
Windows 8

SOFITO_SOFT

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #26 on: February 10, 2011, 03:49:56 PM »
glubssss ....I do not get to much .... I use "Calc3D ".....
greetings

chlh_jd

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #27 on: February 15, 2011, 12:27:41 AM »
Excellent Gile !
Thank you for your Gauss Way determent fun .

chlh_jd

  • Guest
Re: -={ Challenge }=- Matrix Determinant
« Reply #28 on: February 15, 2011, 12:31:45 AM »
Is it can change a lit ? Because it will get a null 'mat' in some case , E.G. the matrix in 'Reply #25 on' .
Quote
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))
« Last Edit: February 15, 2011, 12:34:48 AM by chlh_jd »

ribarm

  • Gator
  • Posts: 3245
  • Marko Ribar, architect
Re: -={ Challenge }=- Matrix Determinant
« Reply #29 on: December 18, 2019, 06:30:34 PM »
I've added my new version here :
http://www.theswamp.org/index.php?topic=45666.msg597622#msg597622

Regards, M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube