Computing the permanent

The number of perfect matchings in a bipartite graph is counted by the permanent of the graph's biadjacency matrix, and the permanent of any 0-1 matrix can be interpreted in this way as the number of perfect matchings in a graph. For planar graphs (regardless of bipartiteness), the FKT algorithm computes the number of perfect matchings in polynomial time by changing the signs of a carefully chosen subset of the entries in the Tutte matrix of the graph, so that the Pfaffian of the resulting skew-symmetric matrix (the square root of its determinant) is the number of perfect matchings. This technique can be generalized to graphs that contain no subgraph homeomorphic to the complete bipartite graph K_3,3.[5]

George Pólya had asked the question[6] of when it is possible to change the signs of some of the entries of a 01 matrix A so that the determinant of the new matrix is the permanent of A. Not all 01 matrices are "convertible" in this manner; in fact it is known (Marcus & Minc (1961)) that there is no linear map ${\displaystyle T}$ such that ${\displaystyle \operatorname {per} T(A)=\det A}$ for all ${\displaystyle n\times n}$ matrices ${\displaystyle A}$. The characterization of "convertible" matrices was given by Little (1975) who showed that such matrices are precisely those that are the biadjacency matrix of bipartite graphs that have a Pfaffian orientation: an orientation of the edges such that for every even cycle ${\displaystyle C}$ for which ${\displaystyle G\setminus C}$ has a perfect matching, there are an odd number of edges directed along C (and thus an odd number with the opposite orientation). It was also shown that these graphs are exactly those that do not contain a subgraph homeomorphic to ${\displaystyle K_{3,3}}$, as above.

Modulo 2, the permanent is the same as the determinant, as ${\displaystyle (-1)\equiv 1{\pmod {2}}.}$ It can also be computed modulo ${\displaystyle 2^{k}}$ in time ${\displaystyle O(n^{4k-3})}$ for ${\displaystyle k\geq 2}$. However, it is UP-hard to compute the permanent modulo any number that is not a power of 2. Valiant (1979)

There are various formulae given by Glynn (2010) for the computation modulo a prime p. First, there is one using symbolic calculations with partial derivatives.

Second, for p = 3 there is the following formula for an n×n-matrix ${\displaystyle A}$, involving the matrix's principal minors (Kogan (1996)):

${\displaystyle \operatorname {per} (A)=(-1)^{n}\Sigma _{J\subseteq \{1,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}}),}$

where ${\displaystyle A_{J}}$ is the submatrix of ${\displaystyle A}$ induced by the rows and columns of ${\displaystyle A}$ indexed by ${\displaystyle J}$, and ${\displaystyle {\bar {J}}}$ is the complement of ${\displaystyle J}$ in ${\displaystyle \{1,\dots ,n\}}$, while the determinant of the empty submatrix is defined to be 1.

The expansion above can be generalized in an arbitrary characteristic p as the following pair of dual identities:

$${\displaystyle {\begin{aligned}\operatorname {per} (A)&=(-1)^{n}\Sigma _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})\\\det(A)&=(-1)^{n}\Sigma _{{J_{1}},\ldots ,{J_{p-1}}}\operatorname {per} (A_{J_{1}})\dotsm \operatorname {per} (A_{J_{p-1}})\end{aligned}}}$$

where in both formulas the sum is taken over all the (p − 1)-tuples ${\displaystyle {J_{1}},\ldots ,{J_{p-1}}}$ that are partitions of the set ${\displaystyle \{1,\dots ,n\}}$ into p − 1 subsets, some of them possibly empty.

The former formula possesses an analog for the hafnian of a symmetric ${\displaystyle A}$ and an odd p:

$${\displaystyle \operatorname {haf} ^{2}(A)=(-1)^{n}\Sigma _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})(-1)^{|J_{1}|+\dots +|J_{(p-1)/2}|}}$$

with the sum taken over the same set of indexes. Moreover, in characteristic zero a similar convolution sum expression involving both the permanent and the determinant yields the Hamiltonian cycle polynomial (defined as ${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ where ${\displaystyle H_{n}}$ is the set of n-permutations having only one cycle):

$${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}.}$$

In characteristic 2 the latter equality turns into ${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$ what therefore provides an opportunity to polynomial-time calculate the Hamiltonian cycle polynomial of any unitary ${\displaystyle U}$ (i.e. such that ${\displaystyle U^{\textsf {T}}U=I}$ where ${\displaystyle I}$ is the identity n×n-matrix), because each minor of such a matrix coincides with its algebraic complement: ${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$ where ${\displaystyle I_{/1}}$ is the identity n×n-matrix with the entry of indexes 1,1 replaced by 0. Moreover, it may, in turn, be further generalized for a unitary n×n-matrix ${\displaystyle U}$ as ${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$ where ${\displaystyle K}$ is a subset of {1, ..., n}, ${\displaystyle I_{/K}}$ is the identity n×n-matrix with the entries of indexes k,k replaced by 0 for all k belonging to ${\displaystyle K}$, and we define ${\textstyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}(K)}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ where ${\displaystyle H_{n}(K)}$ is the set of n-permutations whose each cycle contains at least one element of ${\displaystyle K}$.

This formula also implies the following identities over fields of characteristic 3:

for any invertible ${\displaystyle A}$

${\displaystyle \operatorname {per} (A^{-1})\operatorname {det} ^{2}(A)=\operatorname {per} (A);}$

for any unitary ${\displaystyle U}$, that is, a square matrix ${\displaystyle U}$ such that ${\displaystyle U^{\textsf {T}}U=I}$ where ${\displaystyle I}$ is the identity matrix of the corresponding size,

${\displaystyle \operatorname {per} ^{2}(U)=\det(U+V)\det(-U)}$

where ${\displaystyle V}$ is the matrix whose entries are the cubes of the corresponding entries of ${\displaystyle U}$.

It was also shown (Kogan (1996)) that, if we define a square matrix ${\displaystyle A}$ as k-semi-unitary when ${\displaystyle \operatorname {rank} (A^{\textsf {T}}A-I)=k}$, the permanent of a 1-semi-unitary matrix is computable in polynomial time over fields of characteristic 3, while for k > 1 the problem becomes #3-P-complete. (A parallel theory concerns the Hamiltonian cycle polynomial in characteristic 2: while computing it on the unitary matrices is polynomial-time feasible, the problem is #2-P-complete for the k-semi-unitary ones for any k > 0). The latter result was essentially extended in 2017 (Knezevic & Cohen (2017)) and it was proven that in characteristic 3 there is a simple formula relating the permanents of a square matrix and its partial inverse (for ${\displaystyle A_{11}}$ and ${\displaystyle A_{22}}$ being square, ${\displaystyle A_{11}}$ being invertible):

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}=\operatorname {det} ^{2}(A_{11})\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}}$$

and it allows to polynomial-time reduce the computation of the permanent of an n×n-matrix with a subset of k or k − 1 rows expressible as linear combinations of another (disjoint) subset of k rows to the computation of the permanent of an (n − k)×(n − k)- or (n − k + 1)×(n − k + 1)-matrix correspondingly, hence having introduced a compression operator (analogical to the Gaussian modification applied for calculating the determinant) that "preserves" the permanent in characteristic 3. (Analogically, it would be worth noting that the Hamiltonian cycle polynomial in characteristic 2 does possess its invariant matrix compressions as well, taking into account the fact that ham(A) = 0 for any n×n-matrix A having three equal rows or, if n > 2, a pair of indexes i,j such that its i-th and j-th rows are identical and its i-th and j-th columns are identical too.) The closure of that operator defined as the limit of its sequential application together with the transpose transformation (utilized each time the operator leaves the matrix intact) is also an operator mapping, when applied to classes of matrices, one class to another. While the compression operator maps the class of 1-semi-unitary matrices to itself and the classes of unitary and 2-semi-unitary ones, the compression-closure of the 1-semi-unitary class (as well as the class of matrices received from unitary ones through replacing one row by an arbitrary row vector — the permanent of such a matrix is, via the Laplace expansion, the sum of the permanents of 1-semi-unitary matrices and, accordingly, polynomial-time computable) is yet unknown and tensely related to the general problem of the permanent's computational complexity in characteristic 3 and the chief question of P versus NP: as it was shown in (Knezevic & Cohen (2017)), if such a compression-closure is the set of all square matrices over a field of characteristic 3 or, at least, contains a matrix class the permanent's computation on is #3-P-complete (like the class of 2-semi-unitary matrices) then the permanent is computable in polynomial time in this characteristic.

Besides, the problem of finding and classifying any possible analogs of the permanent-preserving compressions existing in characteristic 3 for other prime characteristics was formulated (Knezevic & Cohen (2017)), while giving the following identity for an n×n matrix ${\displaystyle A}$ and two n-vectors (having all their entries from the set {0, ..., p − 1}) ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ such that ${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$, valid in an arbitrary prime characteristic p:

$${\displaystyle \operatorname {per} (A^{(\alpha ,\beta )})=\det ^{p-1}(A)\operatorname {per} (A^{-1})^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)\left(\prod _{j=1}^{n}\beta _{j}!\right)(-1)^{n+\sum _{i=1}^{n}\alpha _{i}}}$$

where for an n×m-matrix ${\displaystyle M}$, an n-vector ${\displaystyle x}$ and an m-vector ${\displaystyle y}$, both vectors having all their entries from the set {0, ..., p − 1}, ${\displaystyle M^{(x,y)}}$ denotes the matrix received from ${\displaystyle M}$ via repeating ${\displaystyle x_{i}}$ times its i-th row for i = 1, ..., n and ${\displaystyle y_{j}}$ times its j-th column for j = 1, ..., m (if some row's or column's multiplicity equals zero it would mean that the row or column was removed, and thus this notion is a generalization of the notion of submatrix), and ${\displaystyle {\vec {1}}_{n}}$ denotes the n-vector all whose entries equal unity. This identity is an exact analog of the classical formula expressing a matrix's minor through a minor of its inverse and hence demonstrates (once more) a kind of duality between the determinant and the permanent as relative immanants. (Actually its own analogue for the hafnian of a symmetric ${\displaystyle A}$ and an odd prime p is ${\textstyle \operatorname {haf} ^{2}(A^{(\alpha ,\alpha )})=\det ^{p-1}(A)\operatorname {haf} ^{2}(A^{-1})^{((p-1){\vec {1}}_{n}-\alpha ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)^{2}(-1)^{n(p-1)/2+n+\sum _{i=1}^{n}\alpha _{i}}}$).

And, as an even wider generalization for the partial inverse case in a prime characteristic p, for ${\displaystyle A_{11}}$, ${\displaystyle A_{22}}$ being square, ${\displaystyle A_{11}}$ being invertible and of size ${\displaystyle {n_{1}}}$x${\displaystyle {n_{1}}}$, and ${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$, there holds also the identity

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}^{(\alpha ,\beta )}={\det }^{p-1}(A_{11})\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{1,i}!\right)\left(\prod _{j=1}^{n}\beta _{1,j}!\right)(-1)^{n_{1}+\sum _{i=1}^{n}\alpha _{1,i}}}$$

where the common row/column multiplicity vectors ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ for the matrix ${\displaystyle A}$ generate the corresponding row/column multiplicity vectors ${\displaystyle \alpha _{s}}$ and ${\displaystyle \beta _{t}}$, s,t = 1,2, for its blocks (the same concerns ${\displaystyle A}$'s partial inverse in the equality's right side).