SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
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:

      [a  b]
 [c  d]

    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: 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
    .
    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
    

Date created: 1/21/2009
Last updated: 1/21/2009
Please email comments on this WWW page to alan.heckert@nist.gov.