Definition:Permanent

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\mathbf A = \sqbrk a_n$ be a square matrix of order $n$.

That is, let:

$\mathbf A = \begin {pmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n 1} & a_{n 2} & \cdots & a_{n n} \end {pmatrix}$


Let $\lambda: \N_{>0} \to \N_{>0}$ be a permutation on $\N_{>0}$.


Then the permanent of $\mathbf A$ is defined as:

$\ds \sum_{\lambda} \paren {\prod_{k \mathop = 1}^n a_{k \map \lambda k} } = \sum_{\lambda} a_{1 \map \lambda 1} a_{2 \map \lambda 2} \cdots a_{n \map \lambda n}$

where:

the summation $\ds \sum_\lambda$ goes over all the $n!$ permutations of $\set {1, 2, \ldots, n}$.


Examples

3 x 3 Matrix

The square matrix:

$\begin {pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end {pmatrix}$

has a permanent of $450$.


Matrix whose Entries are Product of Row and Column Indices

The square matrix of the form:

$\begin{pmatrix} 1 \times 1 & 1 \times 2 & \cdots & 1 \times m \\ 2 \times 1 & 2 \times 2 & \cdots & 2 \times m \\ \vdots & \vdots & \ddots & \vdots \\ m \times 1 & m \times 2 & \cdots & m \times m \end{pmatrix}$

has a permanent of $\paren {n!}^3$.


Also see

  • Results about permanents can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Permanent&oldid=734727"