HP-41 Complex Determinants w/ SandMatrix and 41Z

[Valentin Albillo]

.
Hi, Ángel:

As I told you in my previous post on this subject (which was in another thread), for low dimensionality (say up to 5x5 or 6x6) I prefer the simple, general expansion by minors procedure over complicated, specific formulae for each dimension, which entail traces (cheap) and powers of matrices (expensive).

The expansion is very simple to code and works for any dimensions from 2x2 upwards though it's only reasonably efficient for low orders because the computation time grows like n!. This is my non-optimized, recursive implementation as a 4-line subprogram in HP-71B code valid for both real and complex matrices of any size:

       8 SUB MDET(A(,),D) @ N=UBND(A,1) @ IF N=2 THEN D=A(1,1)*A(2,2)-A(1,2)*A(2,1) @ END
       9 D=0 @ IF TYPE(A)<6 THEN REAL E,B(N-1,N-1) ELSE COMPLEX E,B(N-1,N-1)
      10 FOR K=1 TO N @ FOR I=2 TO N @ C=1 @ FOR J=1 TO N @ IF J#K THEN B(I-1,C)=A(I,J) @ C=C+1
      11 NEXT J @ NEXT I @ CALL MDET(B,E) @ D=D-(-1)^K*A(1,K)*E @ NEXT K

To use it, you simply call it from the keyboard or your own program, passing as parameters (both by reference) the matrix itself (real or complex) and a variable where the determinant will be returned (same type real or complex as the matrix), i.e.:

      CALL MDET(M,D)

Upon return from the subprogram, D holds the value of the determinant. The subprogram finds out the type (real or complex) of the matrix and its dimensions so there's no need to pass this information as additional parameters.

The code could be greatly optimized. For instance, it could attempt to find the row or column which has the most zero values and do the minor expansion by that row or column, which would save significant time, and it could also implement the exact formula for 3x3 determinants as well for extra speed, but this is intended just for proof-of-concept, not production.

One way to check the MDET subprogram is by running this sample driver program:

      1 DESTROY ALL @ OPTION BASE 1
      2 DATA 58,71,67,36,35,19,60,50,71,71,56,45,20,52,64,40,84,50,51,43,69,31,28
      3 DATA 41,54,31,18,33,45,23,46,38,50,43,50,41,10,28,17,33,41,46,66,72,71,38
      4 DATA 40,27,69,(1,2),(2,3),(3,1),(-1,2),(2,-1),(-1,-1),(0,3),(-2,0),(2,2)

      5 REAL A(7,7),D @ READ A @ DISP DET(A) @ DISP @ GOSUB 7
      6 COMPLEX A(3,3),D @ READ A @ DISP @ GOSUB 7 @ END
      7 MAT DISP A; @ DISP @ CALL MDET(A,D) @ DISP "D =";D @ RETURN

which defines both a 7x7 real matrix and a 3x3 complex one and upon running displays them and calls MDET to compute and subsequently display their determinants, like this:

>RUN

      .97095056196

      58 71 67 36 35 19 60
      50 71 71 56 45 20 52
      64 40 84 50 51 43 69
      31 28 41 54 31 18 33
      45 23 46 38 50 43 50
      41 10 28 17 33 41 46
      66 72 71 38 40 27 69

      D = 1

      (1,2)  (2,3)  (3,1)
      (-1,2) (2,-1) (-1,-1)
      (0,3)  (-2,0) (2,2)

      D = (44,-6)

The very first number displayed, .97095056196, is the result returned by the Math ROM function DET when applied to the 7x7 real matrix (DET doesn't work for complex matrices). As you can see from the output produced by MDET, the actual, correct value for the 7x7 determinant is exactly 1, not .97095056196, so this is another important advantage of MDET: it produces exact integer values for integer matrices (as long as no intermediate products or sums exceed 12 digits), which DET might not.

The 7x7 particular matrix used as a test is my 7x7 integer-element "Albillo Matrix #1", as discussed in my article "Mean Matrices". Its determinant is exactly 1, but the DET function in the Matrix ROM evaluates it as .97095056196 despite its small size, simple 2-digit integer elements and 15-digit internal accuracy. See the article for more details on this and other hugely more difficult Albillo Matrices, some of which can put to shame the WP-34S famous 34-digit accuracy. In particular perhaps you would consider:

      - implementing expansion by minors for complex matrices' determinants in 41C code using your awesome microcoded complex and matrix functions, to see how it fares in terms of speed versus your current 4x4 implementation.

      - check your matrix functions or program using my 7x7 matrix as a test case, to see if they return the correct determinant (1). Even though the matrix is real it can be used with your algorithms expecting a complex matrix, right ?

For dimensions over 6x6 or 7x7, I'd simply perform the classical LU decomposition for speed but the accuracy for integer matrices would certainly not be as good.

Regards.
V.
.