Essays/Determinant
< Essays
Jump to navigation
Jump to search
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.