Permanent

Permanent[m]

gives the permanent of the square matrix m.

Details and Options

  • Permanent works with both numeric and symbolic matrices.
  • The permanent of an matrix m is given by , where the are the permutations of elements.
  • Permanent[m,Modulus->n] computes the permanent modulo n.
  • Permanent supports a Method option. Possible settings include "MemoizedExpansion", "MixedCoefficient", "Glynn" and "Ryser". The default setting of Automatic switches among these methods depending on the matrix given.

Examples

open allclose all

Basic Examples  (2)

Find the permanent of a symbolic matrix:

The permanent of an exact matrix:

Scope  (2)

Find the permanent of a symbolic matrix:

Use exact arithmetic to compute the permanent:

Use machine arithmetic:

Use 40-digit precision arithmetic:

Options  (2)

Method  (1)

Use the default method for numerical evaluation:

Obtain the result from all available methods:

Compare the timings of the four methods:

Modulus  (1)

Compute a permanent using arithmetic modulo 47:

This is faster than computing Mod[Permanent[m],47]:

Applications  (6)

The permanent of a square matrix of all ones is the factorial of the dimension:

The permanent of a square matrix of all ones minus the identity matrix counts the number of derangements of the corresponding dimension:

Given n sets, each containing a subset of (1 n), the number of ways to choose a distinct element from each subset is equal to the permanent of the 01 matrix where the (i,j) position contains a 1 exactly when subset i contains j:

There are two ways to create sets with distinct elements from each subset:

Confirm the result by explicitly constructing these sets:

Use the permanent to compute the number of ways n queens can be placed on an n×n chessboard such that no two queens attack each other:

The permanental polynomial of a graph is defined as the permanent of id x-m, where m is the corresponding adjacency matrix and id is the identity matrix of appropriate size:

The permanental polynomial of a path graph with n vertices is equivalent to the Fibonacci polynomial :

The permanental polynomial of a cycle graph can also be expressed in terms of the Fibonacci polynomial:

Define a function for computing a Fourier matrix with unit normalization:

For even dimensions, the permanent is zero:

For odd dimensions, the permanent is always an integer:

For an odd prime p>3, the permanent of the p×p matrix is congruent to p!, modulo p3:

Properties & Relations  (10)

The permanent is given by :

The permanent is a polynomial of its entries. Degree 2 for a matrix:

Degree 3 for a matrix etc.:

The determinant Det has the same terms as the permanent, except for sign changes:

The permanent can be computed recursively via cofactor expansion along any row:

Or any column:

The permanent is the outer product of the matrix rows, with terms having the repeated column index removed:

A matrix and its transpose have the same permanent:

The permanent is invariant under an arbitrary permutation of rows and columns:

The permanent of a matrix multiplied by a diagonal matrix is equal to the product of the permanent of the original matrix and the diagonal elements of the diagonal matrix:

The permanent of a triangular matrix is the product of its diagonal elements:

The permanent of a block diagonal matrix is the product of the permanents of the diagonal blocks:

Possible Issues  (1)

Computing the permanent becomes slow even at modest dimension:

Wolfram Research (2015), Permanent, Wolfram Language function, https://reference.wolfram.com/language/ref/Permanent.html (updated 2022).

Text

Wolfram Research (2015), Permanent, Wolfram Language function, https://reference.wolfram.com/language/ref/Permanent.html (updated 2022).

CMS

Wolfram Language. 2015. "Permanent." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2022. https://reference.wolfram.com/language/ref/Permanent.html.

APA

Wolfram Language. (2015). Permanent. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/Permanent.html

BibTeX

@misc{reference.wolfram_2024_permanent, author="Wolfram Research", title="{Permanent}", year="2022", howpublished="\url{https://reference.wolfram.com/language/ref/Permanent.html}", note=[Accessed: 10-October-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_permanent, organization={Wolfram Research}, title={Permanent}, year={2022}, url={https://reference.wolfram.com/language/ref/Permanent.html}, note=[Accessed: 10-October-2024 ]}