Van Der Waerden's Conjecture

In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the immanant.

Definition

The permanent of an matrix is defined as

$\operatorname(A)=\sum_\prod_^n a_.$

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,

$\operatorname\begina&b \\ c&d\end=ad+bc,$

and

$\operatorname\begina&b&c \\ d&e&f \\ g&h&i \end=aei + bfg + cdh + ceg + bdi + afh.$

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. Muir and Metzler use the notation $\overset\quad \overset$.

The word, ''permanent'', originated with Cauchy in 1812 as “fonctions symétriques permanentes” for a related type of function, and was used by Muir and Metzler in the modern, more specific, sense.

Properties

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 = \left(a_\right)$ of order ''n'':
* 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 = \left(a_\right)$ and $B=\left(b_\right)$ are square matrices of order ''n'' then, $\operatorname\left(A + B\right) = \sum_ \operatorname \left(a_\right)_ \operatorname \left(b_\right)_,$ where ''s'' and ''t'' are subsets of the same size of and $\bar, \bar$ are their respective complements in that set.
* If $A$ is a triangular matrix, i.e. $a_=0$, whenever $i>j$ or, alternatively, whenever i, then its permanent (and determinant as well) equals the product of the diagonal entries: $\operatorname\left(A\right) = a_ a_ \cdots a_ = \prod_^n a_.$

Relation to determinants

Laplace's expansion by minors for computing the determinant along a row, column or diagonal extends to the permanent by ignoring all signs. For example, expanding along the first column,

$\begin \operatorname \left ( \begin 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end \right ) = & 1 \cdot \operatorname \left( \begin 1&0&0\\ 0&1&0\\ 0&0&1 \end\right) + 2\cdot \operatorname \left(\begin1&1&1\\0&1&0\\0&0&1\end\right) \\ & + \ 3\cdot \operatorname \left(\begin1&1&1\\1&0&0\\0&0&1\end\right) + 4 \cdot \operatorname \left(\begin1&1&1\\1&0&0\\0&1&0\end\right) \\ = & 1(1) + 2(1) + 3(1) + 4(1) = 10, \end$

while expanding along the last row gives,

$\begin \operatorname \left ( \begin 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end \right ) = & 4 \cdot \operatorname \left(\begin1&1&1\\1&0&0\\0&1&0\end\right) + 0\cdot \operatorname \left(\begin1&1&1\\2&0&0\\3&1&0\end\right) \\ & + \ 0\cdot \operatorname \left(\begin1&1&1\\2&1&0\\3&0&0\end\right) + 1 \cdot \operatorname \left( \begin 1&1&1\\ 2&1&0\\ 3&0&1\end\right) \\ = & 4(1) + 0 + 0 + 1(6) = 10. \end$

On the other hand, the basic multiplicative property of determinants is not valid for permanents. A simple example shows that this is so.

$\begin 4 &= \operatorname \left ( \begin 1 & 1 \\ 1 & 1 \end \right )\operatorname \left ( \begin 1 & 1 \\ 1 & 1 \end \right ) \\ &\neq \operatorname\left ( \left ( \begin 1 & 1 \\ 1 & 1 \end \right ) \left ( \begin 1 & 1 \\ 1 & 1 \end \right ) \right ) = \operatorname \left ( \begin 2 & 2 \\ 2 & 2 \end \right )= 8. \end$

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

Applications

Symmetric tensors

The permanent arises naturally in the study of the symmetric tensor power of Hilbert spaces. In particular, for a Hilbert space $H$, let $\vee^k H$ denote the $k$th symmetric tensor power of $H$, which is the space of symmetric tensors. Note in particular that $\vee^k H$ is spanned by the symmetric products of elements in $H$. For $x_1,x_2,\dots,x_k \in H$, we define the symmetric product of these elements by
$x_1 \vee x_2 \vee \cdots \vee x_k = (k!)^ \sum_ x_ \otimes x_ \otimes \cdots \otimes x_$
If we consider $\vee^k H$ (as a subspace of $\otimes^kH$, the ''k''th tensor power of $H$) and define the inner product on $\vee^kH$ accordingly, we find that for $x_j,y_j \in H$
\langle
x_1 \vee x_2 \vee \cdots \vee x_k,
y_1 \vee y_2 \vee \cdots \vee y_k
\rangle =
\operatorname\left langle x_i,y_j \rangle\right^k
Applying the Cauchy–Schwarz inequality, we find that \operatorname \left langle x_i,x_j \rangle\right^k \geq 0, and that
\left, \operatorname \left langle x_i,y_j \rangle\right^k \^2 \leq
\operatorname \left langle x_i,x_j \rangle\right^k \cdot
\operatorname \left langle y_i,y_j \rangle\right^k

Cycle covers

Any square matrix $A = (a_)_^n$ can be viewed as the adjacency matrix of a weighted directed graph on vertex set $V=\$, with $a_$ 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" $\sigma(i)$ in the cycle cover, and so $\sigma$ represents a permutation on ''V''. Conversely, any permutation $\sigma$ on ''V'' corresponds to a cycle cover with arcs from each vertex ''i'' to vertex $\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
$\operatorname(\sigma) = \prod_^n a_,$
implying that
$\operatorname(A)=\sum_\sigma \operatorname(\sigma).$
Thus the permanent of ''A'' is equal to the sum of the weights of all cycle-covers of the digraph.

Perfect matchings

A square matrix $A = (a_)$ can also be viewed as the adjacency matrix of a bipartite graph which has vertices $x_1, x_2, \dots, x_n$ on one side and $y_1, y_2, \dots, y_n$ on the other side, with $a_$ representing the weight of the edge from vertex $x_i$ to vertex $y_j$. If the weight of a perfect matching $\sigma$ that matches $x_i$ to $y_$ is defined to be the product of the weights of the edges in the matching, then
$\operatorname(\sigma) = \prod_^n a_.$
Thus the permanent of ''A'' is equal to the sum of the weights of all perfect matchings of the graph.

Permanents of (0, 1) matrices

Enumeration

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

: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'' = 7''e'' 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 , let $A = (a_)$ 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

$\operatorname(J - I) = \operatorname\left (\begin 0 & 1 & 1 & \dots & 1 \\ 1 & 0 & 1 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \dots & 0 \end \right) = n! \sum_^n \frac,$
where ''J'' is the ''n''×''n'' all 1's matrix and ''I'' is the identity matrix, and the ménage numbers are given by

$\begin \operatorname(J - I - I') & = \operatorname\left (\begin 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 \right) \\ & = \sum_^n (-1)^k \frac (n-k)!, \end$

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

Bounds

The Bregman–Minc inequality, conjectured by H. Minc in 1963 and proved by L. M. Brégman in 1973, 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
$\operatorname A \leq \prod_^n (r_i)!^.$

Van der Waerden's conjecture

In 1926, Van der Waerden conjectured that the minimum permanent among all doubly stochastic matrices is ''n''!/''n''^''n'', achieved by the matrix for which all entries are equal to 1/''n''. Proofs of this conjecture were published in 1980 by B. Gyires and in 1981 by G. P. Egorychev and D. I. Falikman; 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.

Computation

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

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases