(48g/49/50) Matrix Permanent

[John Keith]

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)'