(48g/49/50) Matrix Permanent
04-28-2023, 06:02 PM (This post was last modified: 01-07-2024 08:03 PM by John Keith.)
Post: #1
 John Keith Senior Member Posts: 1,028 Joined: Dec 2013
(48g/49/50) Matrix Permanent
NOTE: This program is obsolete. It has been replaced by the program in post #5 which is much more efficient.

This program computes the permanent of a square matrix. The matrix may be real or complex, and on the 49 and 50, may also be exact integer or symbolic (type 29). This program is slow because computing permanents is slow. It is not practical for matrices larger than 8 x 8, and a 7 x 7 matrix may take several minutes on the physical calculator.

The program uses recursive Laplace expansion as described in this section of the Wikipedia link above. For matrix (or sub-matrix) size 2 x 2, the explicit formula is used, requiring only two multiplications and one addition. This method requires about half as many multiplications as the "brute force" method based on the definition of the permanent.

The program should be stored in a variable named 'PRMNT'. If another name is used, the name reference in the program must be changed.

Code:
 \<< DUP SIZE HEAD 2 OVER   IF SAME                                     @ Size = {2 2}?   THEN DROP OBJ\-> DROP ROT ROT * ROT ROT * + @ 2 x 2 permanent   ELSE \-> n     \<< 1 COL- OBJ\-> EVAL \->LIST SWAP 1 n   @ Remove column 1 and save       FOR k DUP k ROW- DROP PRMNT SWAP        @ Recurse over row permutations       NEXT DROP n \->LIST * \GSLIST           @ Multiply by column 1 and sum     \>>   END \>>

A shorter version for the 49 and 50:

Code:
 \<< DUP SIZE HEAD 2. OVER   IF SAME   THEN DROP OBJ\-> DROP UNROT * UNROT * +   ELSE \-> n     \<< 1. COL- AXL SWAP 1. n       FOR k DUP k ROW- DROP PRMNT SWAP       NEXT DROP n \->LIST * \GSLIST     \>>   END EVAL                                    @ EVAL for symbolic matrices \>>

Some examples:

This 7 x 7 1/0 matrix from A000794 returns 24 in about 4 minutes on my 50g.

Code:
 [[1 0 0 1 1 0 0]  [0 1 1 0 1 0 0]  [1 0 1 0 0 1 0]  [0 1 0 1 0 1 0]  [0 0 1 1 0 0 1]  [1 1 0 0 0 0 1]  [0 0 0 0 1 1 1]]

A symbolic permanent:

Code:
 [[ 'A' 'B' 'C' ]  [ 'D' 'E' 'F' ]  [ 'G' 'H' 'I' ]] PRMNT returns '(I*E+H*F)*A+((I*D+G*F)*B+(H*D+G*E)*C)'
 « Next Oldest | Next Newest »

 Messages In This Thread (48g/49/50) Matrix Permanent - John Keith - 04-28-2023 06:02 PM RE: (48g/49/50) Matrix Permanent - Valentin Albillo - 04-28-2023, 10:44 PM RE: (48g/49/50) Matrix Permanent - John Keith - 04-29-2023, 05:30 PM RE: (48g/49/50) Matrix Permanent - John Keith - 05-03-2023, 07:39 PM RE: (48g/49/50) Matrix Permanent - John Keith - 01-07-2024, 08:27 PM RE: (48g/49/50) Matrix Permanent - John Keith - 01-24-2024, 03:40 PM

User(s) browsing this thread: 1 Guest(s)