## `linalg::permanent` -- permanent of a matrix

#### Introduction

`linalg::permanent``(A)` computes the permanent of the square matrix A.

#### Call(s)

`linalg::permanent(A)`

#### Parameters

`A` | - | a square matrix of a domain of category `Cat::Matrix`

#### Returns

an element of the component ring of `A`.

#### Related Functions

`linalg::det`

#### Details

- The component ring of the matrix `A` must be a commutative ring, i.e., a domain of category `Cat::CommutativeRing`.

#### Example 1

We compute the permanent of the following matrix:

    >> delete a11, a12, a21, a22:
       A := matrix([[a11, a12], [a21, a22]])

                                  +-          -+
                                  |  a11, a12  |
                                  |            |
                                  |  a21, a22  |
                                  +-          -+

which gives us the general formula for the permanent of an arbitrary 2x2 matrix:

    >> linalg::permanent(A)

                                 a11 a22 + a12 a21

#### Example 2

The permanent of a matrix can be computed over arbitrary commutative rings. Let us create a random matrix defined over the ring Z6, the integers modulo 6:

    >> B := linalg::randomMatrix(5, 5, Dom::IntegerMod(6))

                 +-                                             -+
                 |  3 mod 6, 2 mod 6, 3 mod 6, 5 mod 6, 4 mod 6  |
                 |                                               |
                 |  2 mod 6, 5 mod 6, 2 mod 6, 1 mod 6, 1 mod 6  |
                 |                                               |
                 |  1 mod 6, 3 mod 6, 3 mod 6, 2 mod 6, 2 mod 6  |
                 |                                               |
                 |  1 mod 6, 0 mod 6, 3 mod 6, 3 mod 6, 5 mod 6  |
                 |                                               |
                 |  0 mod 6, 0 mod 6, 0 mod 6, 1 mod 6, 3 mod 6  |
                 +-                                             -+

The permanent of this matrix is:

    >> linalg::permanent(B)

                                      4 mod 6

Its determinant is:

    >> linalg::det(B)

                                      0 mod 6

#### Background

- The permanent of an n x n matrix A=(a[i,j]) (1<=i,j<=n) is defined similary as the determinant of A, only the signs of the permutations do not enter the definition:

      perm(A):= Sum( Prod( A[s(j),j],j=1..n ), s in Sn )

  (Sn is the symmetric group of all permutations of {1,...,n}.)
- In contrast to the computation of the determinant, the computation of the permanent takes exponential time in n!

#### Changes

- new function

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000