The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

Complex Matrix Determinant on the 15C
Message #1 Posted by Andrew H. on 22 May 2010, 11:19 p.m.

Comrades,

Does anyone know of a program for the 15C that calculates the determinant of a 3 × 3 matrix with complex elements?

Andrew

      
Re: Complex Matrix Determinant on the 15C
Message #2 Posted by Karl Schneider on 23 May 2010, 1:36 a.m.,
in response to message #1 by Andrew H.

Quote:
Comrades,

Does anyone know of a program for the 15C that calculates the determinant of a 3 × 3 matrix with complex elements?

Andrew


That's a good question. I'm sure you're aware that the HP-15C can calculate the inverse of a 3 x 3 complex-valued matrix in place using built-in utilities that transform such a matrix into a real-valued 6 x 6 matrix, along with the LU decomposition. It can also calculate the determinant of real-valued matrices up to 8 x 8, using the LU decomposition. However, the determinant of a complex-valued matrix is something different.

I've thought about it before. Although I have no such program, I believe that it might be feasible within the resource limitations of the HP-15C:

  1. Store the complex matrix as a 3 x 6 real matrix in the standard "Complex" form, with alternating real and imaginary values.

  2. Compute the complex-valued determinant of a 2 x 2 complex submatrix in rows 2 and 3, recalling each element using indices on the stack with the "RCL g" function (or conventionally), then assembling and multiplying the complex-valued elements when ready.

  3. Multiply this determinant by its corresponding complex-valued element in row 1, and store to two registers.

  4. Do the same for the other two submatrices (except the last sub-result need not be stored).

  5. Combine the three sub-results.

You'll need 18 registers for the complex matrix, 5 registers for Complex mode, at least 4 registers to store two or more complex-valued sub-results, plus space for the program. The "Simpler" method may require 22-23 registers in total, as "RCL A (user mode)" is a two-byte instruction.

Example (if I've got it right) for steps 2 and 3:

METHODICAL:                   SIMPLER:
instruct.  req'd stk depth    instruct.  req'd stk depth
2                1            2              1
ENTER            2            STO 0          1
3                2            3              1
RCL g A          1            STO 1          1
2                2            RCL A (u)      1
ENTER            3            RCL A (u)      2
4                3            f I            1
RCL g A          2            3              2
f I              1            STO 0          2
3                2            R_down         1 
ENTER            3            RCL A (u)      2
5                3            RCL A (u)      3
RCL g A          2            f I            2
3                3            *              1
ENTER            4            2              2
6                4            STO 0          2
RCL g A          3            CLx            2 
f I              2            5              2
*                1            STO 1          2
STO 2            1            R_down         1
Re<>Im           1            RCL A (u)      2 
STO 3            0            RCL A (u)      3 
2                1            f I            2
ENTER            2            3              3
5                2            STO 1          3
RCL g A          1            R_down         2 
2                2            RCL A (u)      3
ENTER            3            RCL A (u)      4
6                3            f I            3 
RCL g A          2            *              2
f I              1            -              1
3                2            f MATRIX 1     1
ENTER            3            RCL A (u)      2
3                3            RCL A (u)      3
RCL g A          2            f I            2
3                3            *              1
ENTER            4            STO 2          1
4                4            Re<>Im         1
RCL g A          3            STO 3          0
f I              2
*                1
RCL 2            2
RCL 3            3
f I              2 
x<>y             2
-                1
1                2
ENTER            3
RCL g A          2
1                3 
ENTER            4
2                4 
RCL g A          3
f I              2
*                1
STO 4            1
Re<>Im           1
STO 5            0

The HP-42S has full built-in functionality for complex matrices...

-- KS

Edited: 24 May 2010, 2:46 a.m. after one or more responses were posted

            
Re: Complex Matrix Determinant on the 15C
Message #3 Posted by Andrew H. on 23 May 2010, 2:51 a.m.,
in response to message #2 by Karl Schneider

Karl,

Ausgezeichnet! Thank you.

I thought that it might be possible to do this using the 15C's in-built matrix functions (other than matrix addition, subtraction, and multiplication) in just a few steps, but it seems that this isn't feasible.

Andrew

Edited: 23 May 2010, 2:55 a.m.

                  
Re: Complex Matrix Determinant on the 15C
Message #4 Posted by Karl Schneider on 23 May 2010, 5:47 p.m.,
in response to message #3 by Andrew H.

Andrew --

This enticed me to investigate in more detail a few things I've wondered about.

As I had suspected, if a complex-valued matrix is singular (determinant of 0 + i0), the HP-15C will also compute a value of virtually zero for the real-valued transformation matrix ('Py,x' followed by MATRIX 2). As an example, for the following singular matrix

 [ 1+i3  2+i4 ]
 [ 2+i6  4+i8 ]

the HP-15C calculates -2.053600001E-18 as the determinant (more about this later), while the HP-42S computes exactly 0 + i0.

Thus, if you are simply wondering if a complex-valued matrix is invertible, the HP-15C can tell you that.

For the nonsingular matrix

 [ 1+i5  2+i4 ]
 [ 2+i6  4+i8 ]

the HP-42S calculates -16 + i8 (exactly) as the determinant, while the HP-15C calculates 319.9999999 as the determinant of the transformation matrix. Note that 320 is the squared magnitude of the complex-valued determinant. I doubt that this is coincidental.

It seems that the HP-15C can give you the magnitude of a complex-valued determinant. I'm open to suggestions how that piece of information, along with the computed inverse matrix, could be employed using linear algebra to obtain the actual determinant.


Now, why does the HP-15C seem unable to compute exact integer values for the determinants of integer-valued matrices?

ANSWER: The HP-15C does not calculate determinants directly. Instead, it first computes a 'unitized' LU decomposition of the matrix that can be stored in the same space. The determinant of that is simply the product of the main-diagonal elements of the U matrix (those of the L matrix are all unity), with a sign change for an odd number of necessary row transpositions.

The LU decomposition is part of the process for matrix inversion (allows in-place inversion), and speeds up solution of linear equations.

So, why is LU decomposition performed unnecessarily for determinants, when direct computation is faster and more accurate? Couldn't LU be computed when inversion or linear solutions are subsequently requested?

ANSWER: This was probably a consequence of limited ROM space for the functionality to be implemented. Additional machine code -- similar to what I devised above, but more extensive -- would have been needed for direct computation of determinants. Instead, the existing LU-decomposition code was utilized. Having LU already computed also provides a 'head start' on subsequent inversion or linear-solution calculations.

However, the unintuitive LU decomposition as part of the HP-15C's determinant calculation is indeed a potential "gotcha" to the user. The user may be chagrined to see his calculation of a determinant -- merely a scalar-valued output -- overwrite a needed matrix with an LU matrix. Or, if insufficient free memory exists to store the LU decomposition to the RESULT matrix, the operation will fail with a cryptic message "Error 10". No additional space is needed if the identifier of the RESULT matrix is designated as that of the original matrix, which can be approximately recovered by twice inverting the LU matrix.

-- KS

Edited: 28 May 2010, 1:49 a.m. after one or more responses were posted

                        
Re: Complex Matrix Determinant on the 15C
Message #5 Posted by Andrew H. on 25 May 2010, 7:32 p.m.,
in response to message #4 by Karl Schneider

Karl,

A bit of research has uncovered a formula that might be useful:

det(A) = [tr^3(A) – 3tr(A)tr(A^2) + 2tr(A^3)]/6

which is derived from Newton's identities (http://en.wikipedia.org/wiki/Determinant).

The real part of the trace of a 6 × 6 partitioned matrix is just a(1,1) + a(1,2) + a(1,3) and the imaginary part is just a(4,1) + a(4,2) + a(4,3).

I agree with your observation that the product of the diagonal elements of the LU decomposition is the square of the absolute value of the determinant. This suggests that it might be possible to calculate the determinant from the diagonal elements of the LU decomposition using Newton's identities. However, this is probably not viable on the 15C as there might be row permutations during the calculation of the LU decomposition.

Andrew

                              
Re: Complex Matrix Determinant on the 15C
Message #6 Posted by Karl Schneider on 26 May 2010, 1:24 a.m.,
in response to message #5 by Andrew H.

Quote:
A bit of research has uncovered a formula that might be useful:

det(A) = [tr^3(A) – 3tr(A)tr(A^2) + 2tr(A^3)]/6


Andrew --

A novel approach, but there's not enough space on the HP-15C for it, using built-in functionality. A 3 x 3 complex-valued matrix A has 9 complex-valued elements to represent as 18 real-valued elements -- each requiring a free register, of which no more than 64 are available. To calculate A^2, the first A is doubled to 36 elements by MATRIX 2, while the second A still has 18. The product A^2 must be stored separately, requiring 18 more. That's 72 registers, and we still need to store a program to extract the traces, perform the multiplications, and combine the results.

-- KS

Edited: 26 May 2010, 1:27 a.m.

                                    
Re: Complex Matrix Determinant on the 15C
Message #7 Posted by Andrew H. on 26 May 2010, 11:35 p.m.,
in response to message #6 by Karl Schneider

Karl,

The harsh impact of reality!

Andrew

      
Re: Complex Matrix Determinant on the 15C
Message #8 Posted by Palmer O. Hanson, Jr. on 23 May 2010, 9:30 p.m.,
in response to message #1 by Andrew H.

I have never had a 15C so I don't know its capabilities relative to the 33s and 35s so I don't know if this will help or not. I did write Third Order Complex Liinear Equation Solvers for those two machines which use Cramer's Rule so there are determinant solutions buried in both. You can find them as Articles 722 and 887.

            
Re: Complex Matrix Determinant on the 15C
Message #9 Posted by Andrew H. on 25 May 2010, 7:35 p.m.,
in response to message #8 by Palmer O. Hanson, Jr.

Palmer,

Thanks for sharing this.

Andrew


[ Return to Index | Top of Index ]

Go back to the main exhibit hall