Dataplot Vol 2 Vol 1

# MATRIX PERMANENT

Name:
MATRIX PERMANENT (LET)
Type:
Let Subcommand
Purpose:
Compute the permanent of a matrix.
Description:
The determinant of an NxN matrix A is defined as

det A = a1A11 - a2A12 + a3A13 - ... - (-1)N+1anA1N

where A1j is the entry in row 1 and column j of A and aj 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.

Syntax:
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).
Examples:
LET P = MATRIX PERMANENT A
Note:
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.
Note:
Matrices are created with the READ MATRIX, CREATE MATRIX and MATRIX DEFINITION commands.
Note:
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.
Note:
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.
Note:
DATAPLOT computes the permanent using the PERMAN subroutine given in Nijenhuis and Wilf (see the Reference section below).
Default:
None
Synonyms:
None
Related Commands:
 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.
Reference:
Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 23.
Applications:
Combinatorial Analysis
Implementation Date:
2009/1
Program:
```
.  Following example from Nijenhuis and Wilf
DIMENSION 100 COLUMNS
LET ICNT = 0
.
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
.
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
.
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
.
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
.
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
.
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
.
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
.
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
.
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
```

Date created: 1/21/2009
Last updated: 1/21/2009