Essays/Determinant

We compute the ordinary determinant of a square matrix.

Primitive

The ordinary determinant is the monad -/ .* .

det=: -/ .*

Laplace Expansion

Laplace expansion on column 0. This takes time of order !n .

det1  =: ({."1 -/ .* 1 $:\. }."1) ` ({.@,) @. (1=#)

det1a =: 3 : 0
 if. 1=#y do. {.,y else. ({."1 y) -/ .* 1 det1a\. }."1 y end.
)

Gaussian Elimination

Let i,j be the row and column indices of the largest entry. Do Gaussian elimination on row i (and column j), then do Laplace expansion on row i (or column j). This take time of order n^3 .

det2=: 1&$: : (4 : 0)
 if. 0=#y do. x
 elseif. ($y) -: 'i j'=. ($y) #: (i.>./) |,y do. 0
 elseif. 1 do. (x*(_1^i+j)* y{~<i,j) det2 (y{~<(<i);<<j) - (y{~<(<i);j) */ (y{~<i;<<j) % y{~<i,j end.
)

LU Decomposition

The verb LU is from the LU Decomposition page. LU A computes a permutation p , a lower triangular matrix L with 1s on the diagonal, and an upper triangular matrix U such that A -: p {"1 L mp U . The determinant is therefore the sign of the permutation times the product of the diagonal entries of U .

mp=: +/ .*

LU=: 3 : 0
 'm n'=. $ A=. y
 if. 1=m do.
  p ; (=1) ; p{"1 A [ p=. C. (n-1);~.0,(0~:,A)i.1
 else.
  m2=. >.m%2
  'p1 L1 U1'=. LU m2{.A
  D=. (/:p1) {"1 m2}.A
  F=. m2 {."1 D
  E=. m2 {."1 U1
  FE1=. F mp %. E
  G=. m2}."1 D - FE1 mp U1
  'p2 L2 U2'=. LU G
  p3=. (i.m2),m2+p2
  H=. (/:p3) {"1 U1
  (p1{p3) ; (L1,FE1,.L2) ; H,(-n){."1 U2
 end.
)

det3=: (C.!.2@(0&{::) * */@((<0 1)&|:)@(2&{::)) @ LU

Examples

   H=: % @: >: @: (+/~) @: i.  NB. Hilbert matrix

   (det,det1,det2,det3) H 7
4.8358e_25 4.83971e_25 4.8358e_25 4.8358e_25

   (det,det1,det2,det3) H 7x
1r2067909047925770649600000 1r2067909047925770649600000 1r2067909047925770649600000 1r2067909047925770649600000

---

See also

• Cholesky Decomposition
• LU Decomposition
• QR Decomposition
• Matrix Inverse
• Triangular Matrix Inverse
• Determinant
• Minors
• Hilbert Matrix
• Block Matrix Inverse
• Kronecker Product

---

Contributed by Roger Hui.