MATRIX PERMANENT

MATRIX PERMANENT (LET)

Let Subcommand

Compute the permanent of a matrix.

The determinant of an NxN matrix A is defined as
det A = a₁A₁₁ - a₂A₁₂ + a₃A₁₃ - ... - (-1)^N+1a_nA_1N

where A_1j is the entry in row 1 and column j of A and a_j is the determinant of the matrix obtained by omitting the first row and column j of A. This is a recursive definition. The determinant of a 2x2 matrix:

is ab - cd.

The permanent of a matrix is similar to the determinant. However, the sign is postive for all terms in the sum (instead of alternating as it does for the determinant).

The permanent of a matrix has applications in combinatorial analysis.

LET <par> = MATRIX PERMANENT <mat>
                        <SUBSET/EXCEPT/FOR qualification>
where <mat> is a matrix for which the permanent is to be computed;
            <par> is a parameter where the resulting permanent is saved;
and where the <SUBSET/EXCEPT/FOR qualification> is optional (and rarely used in this context).

LET P = MATRIX PERMANENT A

Matrices for which a permanent is to be computed must have the same number of rows and columns. An error message is printed if they do not.

Matrices are created with the READ MATRIX, CREATE MATRIX and MATRIX DEFINITION commands.

The columns of a matrix are accessible as variables by appending an index to the matrix name. For example, the 4x4 matrix C has columns C1, C2, C3, and C4. These columns can be operated on like any other DATAPLOT variable.

The maximum size matrix that DATAPLOT can handle is set when DATAPLOT is built on a particular site. Enter HELP DIMENSION and HELP MATRIX DIMENSION for details.

DATAPLOT computes the permanent using the PERMAN subroutine given in Nijenhuis and Wilf (see the Reference section below).

None

None

MATRIX DETERMINANT	= Compute the determinant of a matrix.
MATRIX ADJOINT	= Compute the adjoint matrix of a matrix.
MATRIX COFACTOR	= Compute a matrix cofactor.
CREATE MATRIX	= Create a matrix from a list of variables.
MATRIX DEFINITION	= Create a matrix from the rows and columns of previously defined variables.
MATRIX MINOR	= Compute a matrix minor.
READ MATRIX	= Read a matrix from the terminal or a file.

Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 23.

Combinatorial Analysis

2009/1

 
.  Following example from Nijenhuis and Wilf
DIMENSION 100 COLUMNS
LET ICNT = 0
.
READ MATRIX M
0  1
1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 2
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1
1  0  1
1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 3
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1  1
1  0  1  1
1  1  0  1
1  1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 4
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1  1  1
1  0  1  1  1
1  1  0  1  1
1  1  1  0  1
1  1  1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 5
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1  1  1  1
1  0  1  1  1  1
1  1  0  1  1  1
1  1  1  0  1  1
1  1  1  1  0  1
1  1  1  1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 6
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1  1  1  1  1
1  0  1  1  1  1  1
1  1  0  1  1  1  1
1  1  1  0  1  1  1
1  1  1  1  0  1  1
1  1  1  1  1  0  1
1  1  1  1  1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 7
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1  1  1  1  1  1
1  0  1  1  1  1  1  1
1  1  0  1  1  1  1  1
1  1  1  0  1  1  1  1
1  1  1  1  0  1  1  1
1  1  1  1  1  0  1  1
1  1  1  1  1  1  0  1
1  1  1  1  1  1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 8
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1  1  1  1  1  1  1
1  0  1  1  1  1  1  1  1
1  1  0  1  1  1  1  1  1
1  1  1  0  1  1  1  1  1
1  1  1  1  0  1  1  1  1
1  1  1  1  1  0  1  1  1
1  1  1  1  1  1  0  1  1
1  1  1  1  1  1  1  0  1
1  1  1  1  1  1  1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 9
LET PERM(ICNT) = A
DELETE M
.
READ MATRIX M
0  1  1  1  1  1  1  1  1  1
1  0  1  1  1  1  1  1  1  1
1  1  0  1  1  1  1  1  1  1
1  1  1  0  1  1  1  1  1  1
1  1  1  1  0  1  1  1  1  1
1  1  1  1  1  0  1  1  1  1
1  1  1  1  1  1  0  1  1  1
1  1  1  1  1  1  1  0  1  1
1  1  1  1  1  1  1  1  0  1
1  1  1  1  1  1  1  1  1  0
END OF DATA
LET A = MATRIX PERMANENT M
LET ICNT = ICNT + 1
LET NVAL(ICNT) = 10
LET PERM(ICNT) = A
DELETE M
.
PRINT NVAL PERM

The following output is generated.

 VARIABLES--NVAL           PERM    

          2              1
          3              2
          4              9
          5             44
          6            265
          7           1854
          8          14833
          9         133496
         10        1334961