permanent (mathematics)

The permanent of an {{math|n×n}} matrix {{math|1=A = (a_i,j)}} is defined as

$$\backslash operatorname\{perm\}(A)=\backslash sum\_\{\backslash sigma\backslash in\; S\_n\}\backslash prod\_\{i=1\}^n\; a\_\{i,\backslash sigma(i)\}.$$

The sum here extends over all elements σ of the symmetric group S_n; i.e. over all permutations of the numbers 1, 2, ..., n.

For example,

and

The definition of the permanent of A differs from that of the determinant of A in that the signatures of the permutations are not taken into account.

The permanent of a matrix A is denoted per A, perm A, or Per A, sometimes with parentheses around the argument. Minc uses Per(A) for the permanent of rectangular matrices, and per(A) when A is a square matrix.{{harvtxt|Minc|1978}} Muir and Metzler use the notation $\backslash overset\{+\}$

The word, permanent, originated with Cauchy in 1812 as “fonctions symétriques permanentes” for a related type of function,{{Citation| last=Cauchy | first=A. L.| title=Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment. |url=https://gallica.bnf.fr/ark:/12148/bpt6k90193x/f97 |journal=Journal de l'École Polytechnique |volume=10 |pages=91–169 |year=1815}} and was used by Muir and Metzler{{harvtxt|Muir|Metzler|1960}} in the modern, more specific, sense.{{harvnb|van Lint|Wilson|2001|loc=p. 108}}

If one views the permanent as a map that takes n vectors as arguments, then it is a multilinear map and it is symmetric (meaning that any order of the vectors results in the same permanent). Furthermore, given a square matrix $A\; =\; \backslash left(a\_\{ij\}\backslash right)$ of order n:{{harvnb|Ryser|1963|loc=pp. 25 – 26}}

• perm(A) is invariant under arbitrary permutations of the rows and/or columns of A. This property may be written symbolically as perm(A) = perm(PAQ) for any appropriately sized permutation matrices P and Q,
• multiplying any single row or column of A by a scalar s changes perm(A) to s⋅perm(A),
• perm(A) is invariant under transposition, that is, perm(A) = perm(A^T).
• If $A\; =\; \backslash left(a\_\{ij\}\backslash right)$ and $B=\backslash left(b\_\{ij\}\backslash right)$ are square matrices of order n then,{{harvnb|Percus|1971|loc=p. 2}} $$\backslash operatorname\{perm\}\backslash left(A\; +\; B\backslash right)\; =\; \backslash sum\_\{s,t\}\; \backslash operatorname\{perm\}\; \backslash left(a\_\{ij\}\backslash right)\_\{i\; \backslash in\; s,\; j\; \backslash in\; t\}\; \backslash operatorname\{perm\}\; \backslash left(b\_\{ij\}\backslash right)\_\{i\; \backslash in\; \backslash bar\{s\},\; j\; \backslash in\; \backslash bar\{t\}\},$$ where s and t are subsets of the same size of {1,2,...,n} and $\backslash bar\{s\},\; \backslash bar\{t\}$ are their respective complements in that set.
• If $A$ is a triangular matrix, i.e. $a\_\{ij\}=0$, whenever $i>j$ or, alternatively, whenever

Laplace's expansion by minors for computing the determinant along a row, column or diagonal extends to the permanent by ignoring all signs.{{harvnb|Percus|1971|loc=p. 12}}

For every $i$,

$$\backslash mathbb\{perm\}(B)=\backslash sum\_\{j=1\}^n\; B\_\{i,j\}\; M\_\{i,j\},$$

where $B\_\{i,j\}$ is the entry of the ith row and the jth column of B, and $M\_\{i,j\}$ is the permanent of the submatrix obtained by removing the ith row and the jth column of B.

For example, expanding along the first column,

$$\backslash begin\{align\}$$

\operatorname{perm} \left ( \begin{matrix} 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end{matrix} \right )

= {} & 1 \cdot \operatorname{perm} \left( \begin{matrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{matrix}\right) + 2\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}\right) \\

& {} + \ 3\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}\right) + 4 \cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}\right) \\

= {} & 1(1) + 2(1) + 3(1) + 4(1) = 10,

\end{align}

while expanding along the last row gives,

$$\backslash begin\{align\}$$

\operatorname{perm} \left ( \begin{matrix} 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end{matrix} \right )

= {} & 4 \cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}\right) + 0\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}\right) \\

& {} + \ 0\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}\right) +

1 \cdot \operatorname{perm} \left( \begin{matrix} 1&1&1\\ 2&1&0\\ 3&0&1\end{matrix}\right) \\

= {} & 4(1) + 0 + 0 + 1(6) = 10.

\end{align}

On the other hand, the basic multiplicative property of determinants is not valid for permanents.{{harvnb|Ryser|1963|loc=p. 26}} A simple example shows that this is so.

&\neq \operatorname{perm}\left ( \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \right ) = \operatorname{perm} \left ( \begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix} \right )= 8. \end{align}

Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in combinatorics, in treating boson Green's functions in quantum field theory, and in determining state probabilities of boson sampling systems.{{cite arXiv |last=Aaronson |first=Scott |date=14 Nov 2010 |title=The Computational Complexity of Linear Optics |eprint=1011.3245|class=quant-ph }} However, it has two graph-theoretic interpretations: as the sum of weights of cycle covers of a directed graph, and as the sum of weights of perfect matchings in a bipartite graph.

The permanent arises naturally in the study of the symmetric tensor power of Hilbert spaces.{{cite book|last1=Bhatia|first1=Rajendra|title=Matrix Analysis|date=1997|publisher=Springer-Verlag|location=New York|isbn=978-0-387-94846-1|pages=16–19}} In particular, for a Hilbert space $H$, let $\backslash vee^k\; H$ denote the $k$th symmetric tensor power of $H$, which is the space of symmetric tensors. Note in particular that $\backslash vee^k\; H$ is spanned by the symmetric products of elements in $H$. For $x\_1,x\_2,\backslash dots,x\_k\; \backslash in\; H$, we define the symmetric product of these elements by

x_1 \vee x_2 \vee \cdots \vee x_k =

(k!)^{-1/2} \sum_{\sigma \in S_k}

x_{\sigma(1)} \otimes x_{\sigma(2)} \otimes \cdots \otimes x_{\sigma(k)}

If we consider $\backslash vee^k\; H$ (as a subspace of $\backslash otimes^kH$, the kth tensor power of $H$) and define the inner product on $\backslash vee^kH$ accordingly, we find that for $x\_j,y\_j\; \backslash in\; H$

$$\backslash langle$$

x_1 \vee x_2 \vee \cdots \vee x_k,

y_1 \vee y_2 \vee \cdots \vee y_k

\rangle =

\operatorname{perm}\left[\langle x_i,y_j \rangle\right]_{i,j = 1}^k

Applying the Cauchy–Schwarz inequality, we find that $\backslash operatorname\{perm\}\; \backslash left[\backslash langle\; x\_i,x\_j\; \backslash rangle\backslash right]\_\{i,j\; =\; 1\}^k\; \backslash geq\; 0$, and that

$$\backslash left|\backslash operatorname\{perm\}\; \backslash left[\backslash langle\; x\_i,y\_j\; \backslash rangle\backslash right]\_\{i,j\; =\; 1\}^k\; \backslash right|^2\; \backslash leq$$

\operatorname{perm} \left[\langle x_i,x_j \rangle\right]_{i,j = 1}^k \cdot

\operatorname{perm} \left[\langle y_i,y_j \rangle\right]_{i,j = 1}^k

{{main|Vertex cycle cover}}

Any square matrix $A\; =\; (a\_\{ij\})\_\{i,j=1\}^n$ can be viewed as the adjacency matrix of a weighted directed graph on vertex set $V=\backslash \{1,2,\backslash dots,n\backslash \}$, with $a\_\{ij\}$ representing the weight of the arc from vertex i to vertex j.

A cycle cover of a weighted directed graph is a collection of vertex-disjoint directed cycles in the digraph that covers all vertices in the graph. Thus, each vertex i in the digraph has a unique "successor" $\backslash sigma(i)$ in the cycle cover, and so $\backslash sigma$ represents a permutation on V. Conversely, any permutation $\backslash sigma$ on V corresponds to a cycle cover with arcs from each vertex i to vertex $\backslash sigma(i)$.

If the weight of a cycle-cover is defined to be the product of the weights of the arcs in each cycle, then

$$\backslash operatorname\{weight\}(\backslash sigma)\; =\; \backslash prod\_\{i=1\}^n\; a\_\{i,\backslash sigma(i)\},$$

implying that

$$\backslash operatorname\{perm\}(A)=\backslash sum\_\backslash sigma\; \backslash operatorname\{weight\}(\backslash sigma).$$

Thus the permanent of A is equal to the sum of the weights of all cycle-covers of the digraph.

A square matrix $A\; =\; (a\_\{ij\})$ can also be viewed as the adjacency matrix of a bipartite graph which has vertices $x\_1,\; x\_2,\; \backslash dots,\; x\_n$ on one side and $y\_1,\; y\_2,\; \backslash dots,\; y\_n$ on the other side, with $a\_\{ij\}$ representing the weight of the edge from vertex $x\_i$ to vertex $y\_j$. If the weight of a perfect matching $\backslash sigma$ that matches $x\_i$ to $y\_\{\backslash sigma(i)\}$ is defined to be the product of the weights of the edges in the matching, then

$$\backslash operatorname\{weight\}(\backslash sigma)\; =\; \backslash prod\_\{i=1\}^n\; a\_\{i,\backslash sigma(i)\}.$$

Thus the permanent of A is equal to the sum of the weights of all perfect matchings of the graph.

The answers to many counting questions can be computed as permanents of matrices that only have 0 and 1 as entries.

Let Ω(n,k) be the class of all (0, 1)-matrices of order n with each row and column sum equal to k. Every matrix A in this class has perm(A) > 0.{{harvnb|Ryser|1963|loc=p. 124}} The incidence matrices of projective planes are in the class Ω(n² + n + 1, n + 1) for n an integer > 1. The permanents corresponding to the smallest projective planes have been calculated. For n = 2, 3, and 4 the values are 24, 3852 and 18,534,400 respectively. Let Z be the incidence matrix of the projective plane with n = 2, the Fano plane. Remarkably, perm(Z) = 24 = |det (Z)|, the absolute value of the determinant of Z. This is a consequence of Z being a circulant matrix and the theorem:{{harvnb|Ryser|1963|loc=p. 125}}

:If A is a circulant matrix in the class Ω(n,k) then if k > 3, perm(A) > |det (A)| and if k = 3, perm(A) = |det (A)|. Furthermore, when k = 3, by permuting rows and columns, A can be put into the form of a direct sum of e copies of the matrix Z and consequently, n = 7e and perm(A) = 24^e.

Permanents can also be used to calculate the number of permutations with restricted (prohibited) positions. For the standard n-set {1, 2, ..., n}, let $A\; =\; (a\_\{ij\})$ be the (0, 1)-matrix where a_ij = 1 if i → j is allowed in a permutation and a_ij = 0 otherwise. Then perm(A) is equal to the number of permutations of the n-set that satisfy all the restrictions. Two well known special cases of this are the solution of the derangement problem and the ménage problem: the number of permutations of an n-set with no fixed points (derangements) is given by

where J is the n×n all 1's matrix and I is the identity matrix, and the ménage numbers are given by

$$\backslash begin\{align\}$$

\operatorname{perm}(J - I - I') & = \operatorname{perm}\left (\begin{matrix} 0 & 0 & 1 & \dots & 1 \\ 1 & 0 & 0 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 1 & \dots & 0 \end{matrix} \right) \\

& = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!,

\end{align}

where I' is the (0, 1)-matrix with nonzero entries in positions (i, i + 1) and (n, 1).

Permanent of n×n all 1's matrix is a number of possible arrangements of n mutually non-attacking rooks in the positions of the board of size n×n.{{Cite journal

|last1=Shevelev

|first1=V.S.

|year=1990

|title=On a representation of rook polinomials

|journal=Russian Mathematical Surveys

|volume=45

|issue=4

|pages=183–185

|url=https://www.mathnet.ru/eng/rm4775

|doi=10.1070/RM1990v045n04ABEH002387

}}

The Bregman–Minc inequality, conjectured by H. Minc in 1963{{citation|first=Henryk|last=Minc|title=Upper bounds for permanents of (0,1)-matrices|journal=Bulletin of the American Mathematical Society|volume=69|issue=6|year=1963|pages=789–791|doi=10.1090/s0002-9904-1963-11031-9|doi-access=free}} and proved by L. M. Brégman in 1973,{{harvnb|van Lint|Wilson|2001|loc=p. 101}} gives an upper bound for the permanent of an n × n (0, 1)-matrix. If A has r_i ones in row i for each 1 ≤ i ≤ n, the inequality states that

$$\backslash operatorname\{perm\}\; A\; \backslash leq\; \backslash prod\_\{i=1\}^n\; (r\_i)!^\{1/r\_i\}.$$

In 1926, Van der Waerden conjectured that the minimum permanent among all {{nowrap|n × n}} doubly stochastic matrices is n!/nⁿ, achieved by the matrix for which all entries are equal to 1/n.{{citation

| last = van der Waerden | first = B. L. | author-link = Bartel Leendert van der Waerden

| journal = Jber. Deutsch. Math.-Verein.

| page = 117

| title = Aufgabe 45

| volume = 35

| year = 1926}}. Proofs of this conjecture were published in 1980 by B. Gyires{{citation |last=Gyires |first=B. |title=The common source of several inequalities concerning doubly stochastic matrices |journal=Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis |volume=27 |issue=3–4 |pages=291–304 |year=1980 |doi=10.5486/PMD.1980.27.3-4.15 |mr=604006 |doi-access=free}}. and in 1981 by G. P. Egorychev{{citation

| last = Egoryčev | first = G. P.

| language = ru

| location = Krasnoyarsk

| mr = 602332

| page = 12

| publisher = Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz.

| title = Reshenie problemy van-der-Vardena dlya permanentov

| year = 1980}}. {{citation

| last = Egorychev | first = G. P.

| issue = 6

| journal = Akademiya Nauk SSSR

| language = ru

| mr = 638007

| pages = 65–71, 225

| title = Proof of the van der Waerden conjecture for permanents

| volume = 22

| year = 1981| doi = 10.1007/BF00968054

| bibcode = 1981SibMJ..22..854E

}}. {{citation

| last = Egorychev | first = G. P.

| doi = 10.1016/0001-8708(81)90044-X

| doi-access = free

| issue = 3

| journal = Advances in Mathematics

| mr = 642395

| pages = 299–305

| title = The solution of van der Waerden's problem for permanents

| volume = 42

| year = 1981}}. and D. I. Falikman;{{citation

| last = Falikman | first = D. I.

| issue = 6

| journal = Akademiya Nauk Soyuza SSR

| language = ru

| mr = 625097

| pages = 931–938, 957

| title = Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix

| volume = 29

| year = 1981}}. Egorychev's proof is an application of the Alexandrov–Fenchel inequality.Brualdi (2006) p.487 For this work, Egorychev and Falikman won the Fulkerson Prize in 1982.[https://mathopt.org/?nav=fulkerson Fulkerson Prize], Mathematical Optimization Society, retrieved 2012-08-19.

{{main|Computing the permanent|Sharp-P-completeness of 01-permanent}}

The naïve approach, using the definition, of computing permanents is computationally infeasible even for relatively small matrices. One of the fastest known algorithms is due to H. J. Ryser.{{harvtxt|Ryser|1963|loc=p. 27}} Ryser's method is based on an inclusion–exclusion formula that can be given{{harvtxt|van Lint|Wilson|2001}} [https://books.google.com/books?id=5l5ps2JkyT0C&pg=PA108&dq=permanent+ryser&lr=#PPA99,M1 p. 99] as follows: Let $A\_k$ be obtained from A by deleting k columns, let $P(A\_k)$ be the product of the row-sums of $A\_k$, and let $\backslash Sigma\_k$ be the sum of the values of $P(A\_k)$ over all possible $A\_k$. Then

$$\backslash operatorname\{perm\}(A)=\backslash sum\_\{k=0\}^\{n-1\}\; (-1)^\{k\}\; \backslash Sigma\_k.$$

It may be rewritten in terms of the matrix entries as follows:

$$\backslash operatorname\{perm\}\; (A)\; =\; (-1)^n\; \backslash sum\_\{S\backslash subseteq\backslash \{1,\backslash dots,n\backslash \}\}\; (-1)^$$

The permanent is believed to be more difficult to compute than the determinant. While the determinant can be computed in polynomial time by Gaussian elimination, Gaussian elimination cannot be used to compute the permanent. Moreover, computing the permanent of a (0,1)-matrix is #P-complete. Thus, if the permanent can be computed in polynomial time by any method, then FP = #P, which is an even stronger statement than P = NP. When the entries of A are nonnegative, however, the permanent can be computed approximately in probabilistic polynomial time, up to an error of $\backslash varepsilon\; M$, where $M$ is the value of the permanent and $\backslash varepsilon\; >\; 0$ is arbitrary.{{Citation|last1= Jerrum | first1= M.|author1-link= Mark Jerrum |last2=Sinclair | first2= A.|author2-link= Alistair Sinclair|last3=Vigoda | first3= E.|title=A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries |journal=Journal of the ACM |year=2004 |volume= 51 | issue= 4|pages= 671–697 | doi=10.1145/1008731.1008738| citeseerx= 10.1.1.18.9466| s2cid= 47361920}} The permanent of a certain set of positive semidefinite matrices is NP-hard to approximate within any subexponential factor.{{cite journal|last1=Meiburg|first1=Alexander|date=2023|title=Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography|journal=Algorithmica|volume=85 |issue=12 |pages=3828–3854 |doi=10.1007/s00453-023-01169-1|doi-access=free|arxiv=2111.03142}} If further conditions on the spectrum are imposed, the permanent can be approximated in probabilistic polynomial time: the best achievable error of this approximation is $\backslash varepsilon\backslash sqrt\{M\}$ ($M$ is again the value of the permanent).{{cite journal| last1=Chakhmakhchyan|first1=Levon|last2=Cerf|first2=Nicolas|last3=Garcia-Patron|first3=Raul|title=A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices| journal = Phys. Rev. A|volume=96 |issue=2|pages=022329 | doi=10.1103/PhysRevA.96.022329|year=2017|bibcode=2017PhRvA..96b2329C|arxiv=1609.02416|s2cid=54194194}} The hardness in these instances is closely linked with difficulty of simulating boson sampling experiments.

{{main|MacMahon's master theorem}}

Another way to view permanents is via multivariate generating functions. Let $A\; =\; (a\_\{ij\})$ be a square matrix of order n. Consider the multivariate generating function:

&= \left( \sum_{j=1}^n a_{1j} x_j \right ) \left ( \sum_{j=1}^n a_{2j} x_j \right ) \cdots \left ( \sum_{j=1}^n a_{nj} x_j \right). \end{align}

The coefficient of $x\_1\; x\_2\; \backslash dots\; x\_n$ in $F(x\_1,x\_2,\backslash dots,x\_n)$ is perm(A).{{harvnb|Percus|1971|loc=p. 14}}

As a generalization, for any sequence of n non-negative integers, $s\_1,s\_2,\backslash dots,s\_n$ define:

$$\backslash operatorname\{perm\}^\{(s\_1,s\_2,\backslash dots,s\_n)\}(A)$$ as the coefficient of $x\_1^\{s\_1\}\; x\_2^\{s\_2\}\; \backslash cdots\; x\_n^\{s\_n\}$ in$\backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{1j\}\; x\_j\; \backslash right\; )^\{s\_1\}\; \backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{2j\}\; x\_j\; \backslash right\; )^\{s\_2\}\; \backslash cdots\; \backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{nj\}\; x\_j\; \backslash right\; )^\{s\_n\}.$

MacMahon's master theorem relating permanents and determinants is:{{harvnb|Percus|1971|loc=p. 17}}

$$\backslash operatorname\{perm\}^\{(s\_1,s\_2,\backslash dots,s\_n)\}(A)\; =\; \backslash text\{\; coefficient\; of\; \}x\_1^\{s\_1\}\; x\_2^\{s\_2\}\; \backslash cdots\; x\_n^\{s\_n\}\; \backslash text\{\; in\; \}\; \backslash frac\{1\}\{\backslash det(I\; -\; XA)\},$$

where I is the order n identity matrix and X is the diagonal matrix with diagonal $[x\_1,x\_2,\backslash dots,x\_n].$

The permanent function can be generalized to apply to non-square matrices. Indeed, several authors make this the definition of a permanent and consider the restriction to square matrices a special case.In particular, {{harvtxt|Minc|1978}} and {{harvtxt|Ryser|1963}} do this. Specifically, for an m × n matrix $A\; =\; (a\_\{ij\})$ with m ≤ n, define

$$\backslash operatorname\{perm\}\; (A)\; =\; \backslash sum\_\{\backslash sigma\; \backslash in\; \backslash operatorname\{P\}(n,m)\}\; a\_\{1\; \backslash sigma(1)\}\; a\_\{2\; \backslash sigma(2)\}\; \backslash ldots\; a\_\{m\; \backslash sigma(m)\}$$

where P(n,m) is the set of all m-permutations of the n-set {1,2,...,n}.{{harvnb|Ryser|1963|loc=p. 25}}

Ryser's computational result for permanents also generalizes. If A is an m × n matrix with m ≤ n, let $A\_k$ be obtained from A by deleting k columns, let $P(A\_k)$ be the product of the row-sums of $A\_k$, and let $\backslash sigma\_k$ be the sum of the values of $P(A\_k)$ over all possible $A\_k$. Then

$$\backslash operatorname\{perm\}(A)=\backslash sum\_\{k=0\}^\{m-1\}\; (-1)^\{k\}\backslash binom\{n-m+k\}\{k\}\backslash sigma\_\{n-m+k\}.$$

The generalization of the definition of a permanent to non-square matrices allows the concept to be used in a more natural way in some applications. For instance:

Let S₁, S₂, ..., S_m be subsets (not necessarily distinct) of an n-set with m ≤ n. The incidence matrix of this collection of subsets is an m × n (0,1)-matrix A. The number of systems of distinct representatives (SDR's) of this collection is perm(A).{{harvnb|Ryser|1963|loc=p. 54}}

• Computing the permanent
• Bapat–Beg theorem, an application of permanents in order statistics
• Slater determinant, an application of permanents in quantum mechanics
• Hafnian

{{Reflist|30em}}

• {{cite book | zbl=1106.05001 | last=Brualdi | first=Richard A. | author-link=Richard A. Brualdi | title=Combinatorial matrix classes | series=Encyclopedia of Mathematics and Its Applications | volume=108 | location=Cambridge | publisher=Cambridge University Press | year=2006 | isbn=978-0-521-86565-4 | url-access=registration | url=https://archive.org/details/combinatorialmat0000brua }}
• {{cite book | last=Minc | first=Henryk | title= Permanents | others=With a foreword by Marvin Marcus | series=Encyclopedia of Mathematics and its Applications | volume=6| publisher=Addison–Wesley | year= 1978 | issn=0953-4806 | oclc=3980645 | zbl=0401.15005 | location=Reading, MA }}
• {{cite book| last1=Muir | first1=Thomas | last2=Metzler | first2=William H. | year=1960 | orig-year=1882| title = A Treatise on the Theory of Determinants |location=New York| publisher=Dover | oclc=535903}}
• {{citation|first=J.K.|last=Percus|title=Combinatorial Methods|series=Applied Mathematical Sciences #4|publisher=Springer-Verlag|place=New York|year=1971|isbn=978-0-387-90027-8}}
• {{citation|first=Herbert John|last=Ryser|author-link=H. J. Ryser|title=Combinatorial Mathematics|series=The Carus Mathematical Monographs #14|year=1963|publisher=The Mathematical Association of America}}
• {{citation|last1=van Lint|first1=J.H. |last2=Wilson|first2=R.M. |title=A Course in Combinatorics|publisher=Cambridge University Press|year= 2001|isbn=978-0521422604}}

• {{citation|first=Marshall|last=Hall Jr.| author-link=Marshall Hall (mathematician)|title=Combinatorial Theory|edition=2nd|year=1986|publisher=John Wiley & Sons|place=New York|isbn=978-0-471-09138-7|pages=56–72}} Contains a proof of the Van der Waerden conjecture.
• {{citation|first1=M.|last1=Marcus|first2=H.|last2=Minc|title=Permanents|journal=The American Mathematical Monthly|volume=72|issue=6|year=1965|pages=577–591|doi=10.2307/2313846|jstor=2313846}}

• {{PlanetMath |urlname=Permanent |title=Permanent}}
• {{PlanetMath |urlname=VanDerWaerdensPermanentConjecture |title=Van der Waerden's permanent conjecture}}

Category:Algebra

Category:Linear algebra

Category:Matrix theory

Category:Permutations