Interpretations and models of permanent

Question

The standard interpretation of permanent of a $0/1$ matrix if considered as a biadjacency matrix of a bipartite graph is number of perfect matchings of the graph or if considered as a adjacency matrix of a directed graph is number of vertex-disjoint cycle covers and these are also the standard models.

Given the importance of permanent as a $\#P$ complete problem that arises in various contexts such as lattices and polyhedra are there any other non-trivial interpretations of the permanent?

I would be interested in any interpretations to number theory (I know none and if there is one it would be very interesting) or algebraic geometry (however tenuous it may be) particularly since the latter is contemplated to be useful in studying the Permanent-Determinant problem.

I would even consider this as an interpretation for special matrices. Permanent represents natural numbers in a canonical way through special matrices Is every positive integer the permanent of some 0-1 matrix?. However if there is any multiplicative and additive property that comes along with it that would be very great and so far I do not see it but it looks like it should be manageable to concoct interesting classes of matrices which have specific interpretations.

Answer 1

In quantum physics, the state of non-interacting particles that are fermions is represented by a determinant, while for bosons it is a permanent. The computational complexity of the evaluation of a permanent explains why it is possible to design a quantum computer with linear optics (LOQC) --- so with noninteracting photons, which are bosons. If the quantum computer would be evaluating determinants there would be no speedup with respect to a classical computer, so for electrons (which are fermions) one would need to resort to interactions to achieve any gain.

Answer 2

If you are not aware of this, then the following, widely known 'interpretations' of the permanent should be pointed out to you.

0. A definitional interpretation and generalization (permanents are special immanants). Let $\mathbb{L}_n$ denote the lattice of subgroups of the symmetric group $\mathfrak{S}_n$. For each finite permutation group $G\in\mathbb{L}_n$ and any irreducible character $\chi\colon G\rightarrow\mathbb{C}^\times$, the function

$f_\chi^G\colon\color{white}{(a_{i,j})_{(i,j)\in n\times n}}\mathbb{C}^{n\times n}\rightarrow\mathbb{C}$

${\quad}{\quad}\quad\ \ \ (a_{i,j})_{(i,j)\in n\times n}\mapsto \sum_{g\in G}\quad \chi(g)\cdot\prod_{i\in n} a_{i,g(i)}$

is called the immanant¹ w.r.t. $\chi$.

If $\chi$ is the function which is constantly $1$, also called the principal character, then the immanant $f_\chi^{\mathfrak{S}_n}$ is just the permanent of $(a_{i,j})_{(i,j)\in n\times n}$.

In that sense: every permanent is an immanant.

(One can count this as an 'interpretation', sort of. I say 'definitional' above since here the definition of 'permanent' is interpreted in the sense of constructing a larger definition which the permanent is but an instance of.)

1.Conjectural interpretation (Lieb's Permantal Dominance Conjecture: permanents are top elements of a poset on the set of all irreducible characters of the symmetric group on $n$ elements; not to be confused with the so-called, apparently still open). For each $G\in\mathbb{L}_n$ let $\mathbb{K}_G$ denote the set of all irreducible complex characters of $G$. Then $\mathbb{K}_G$ has the following poset structure $\leq$, in other words, is partially ordered by the following definition.

Let $\chi_0\leq \chi_1$ if and only if (using the notation from 0.)

for all Hermitian positive-semidefinite matrices $A\in\mathbb{C}^{n\times n}$ we have $\frac{f_{\chi_0}^G(A)}{\chi_0(\mathrm{id})}\leq\frac{f_{\chi_1}^G(A)}{\chi_1(\mathrm{id})}$.

It is a famous theorem² of Issai Schur that the alternating character $\mathrm{sgn}$ is a bottom element of the poset $(\mathbb{K}_{\mathfrak{S}_n},\leq)$.

(And the immanant w.r.t. $\mathrm{sgn}$ is just the determinant.)

A notorious conjecture (and this is what I mean by 'conjectural interpretation' of the permanent) is whether for any $G\in\mathbb{L}_n$ whatsoever, the principal character is a top element of the poset $(\mathbb{K}_G,\leq)$.

This goes by the name 'Permanental Dominance Conjecture'.

Explicitly, the (apparently still open) Permanental Dominance Conjecture³ states:

For every Hermitian positive semidefinite $A\in\mathbb{C}^{n\times n}$

for every subgroup $G$ of $\mathfrak{S}_n$

for every irreducible character $\chi\colon G\rightarrow\mathbb{C}^\times $

we have $\frac{1}{\chi(\mathrm{id})}\sum_{g\in G}\chi(g)\prod_{i\in n}a_{i,g(i)}\leq\mathrm{per}(A)$.

For $n=4$, an explicit Hermitian positive-semidefinite matrix is known which achieves equality in the conjectural equality. (I am writing from memory here; I once saw this matrix, yet do not find it now.)

A 2016 survey on conjectures on inequalities involving permanents is Fuzhen Zhang: An update on a few permanent conjectures. Volume 4, Issue 1 (Aug 2016). From Zhang's work I take the following:

at the end of which we see appear what came to be know by the (to my mind) a little sillily-named and misleadingly-nfamed 'Permanent On Top Conjecture' published by Soules in his 1966 thesis. The conjecture states that the permanent of a Hermitian positive semi-definite matrix $A$ equals the (of necessity real) largest eigenvalue of the Schur power matrix of $A$.

Note that Zhang emphasizes something which sounds like that electronic machines are necessary to check Shchesnovich's counterexample.

From Zhang's above survey I also take the following 'diagram' (in the informal everyday sense of 'diagram'):

wherein 'Soules POT', a little goofily (I think⁴), refers to the 'Permanent On Top' conjecture, and wherein 'Lieb per-dom' refers to the open 'Permanental Dominance Conjecture', and wherein I colored red what seems to now be known to be semantically false, colored yellow what seems to be open conjectures, and colored green the material/syntactic implications which are known to exist. (Soules, Bapat and Sunder can take solace in the fact that there are many mathematicians who find material implications at least as interesting as semantic truth-values; also, from what I understand of this so far, the certification of Shchesnovich's disproof seems to be an interesting and useful problem in itself.⁵)

EDIT: As an exercise in the important method of criticizing, and then improving one's own answers, let me add the following

In light of Ryo Taba's publication, it seems wrong to say that the permanent can be interpreted as the top element of a poset structure. Of a good interpretation I demand that it is right through and through (as is e.g. the interpretation of the rhythm of day and night as the effect of a tilted axis of revolution), which this interpretation just does not seem to be: it is too weak a statement in dimension $n=3$, as Taba's sharper estimate shows.

¹ _{Language-hazard: the correct spellings in contemporary mathematical discourse are like given here: imman$\mathbf{a}$nt, yet perman$\mathbf{e}$nt. Note that 'imman$\mathbf{e}$nt' lexically also exists. Note also that there is the following randomness: in the case of 'permanent' the usual adjective was also made the noun. In the case of 'immanent', for some reason people avoided making the adjective the noun, and used the variant spelling 'immanant'.}

² _{Issai Schur: Uber endliche Gruppen und Hermitische Formen, Mathematische Zeitschrift 1, p. 184-207.}

³ _{It was pointed out to me recently (I had not kept up with this, was partly writing from what I remembered from what I learned when I worked on counting sign-matrices, and was unaware of this 2015-development when I wrote my answer) that a disproof of 'Soules POT' has recently been published: Valery S. Shchesnovich: The permanent-on-top conjecture is false. Linear Algebra and its Applications Volume 490, 1 February 2016, Pages 196-201 The counterexample is given in dimension $n=5$. Also, there is a stunningly elementary proof by Ryo Tabata in Hiroshima Mathematical Journal 40 (2010), 205-213 that the Permanental Dominance Conjecture is 'more than true' in dimension $n=3$ and $\large \text{for $G=$alternating group on $n$ elements}$: discounting the introduction and references, Ryo Tabata on a mere five pages gives a proof, readable by anyone knowing high-school calculus and linear algebra over $\mathbb{C}$, of a weird strengthening of the Permantental Domimance Conjecture, replacing the upper bound $\mathrm{per}(A)$ by $\lambda\cdot \mathrm{per}(A) + (1-\lambda)\cdot \mathrm{det}(A)$ where $\lambda=\frac{1}{\sqrt[3]{2}}$. I.e., a nontrivial convex linear combination of the permanent and the determinant is an upper bound in dimension $n=3$. $\large \text{Again, please note that Tabata's proof was formulated for characters of the alternating group only.}$}

In dimension $n=4$, even the truth of 'Soules POT' seems to be an open problem. (Cf. remarks of Zhang in loc. cit. to the effect that Shchesnovich tried to disprove it)

⁴ _{I think it is fair to say that the publisher of the survey I cite should have given Zhang better editorial advice and services. One linguistic infelicity chases the next. It is not the author who is to blame.}

⁵ _{This is not to cast doubt on the correctness of Shchesnovich's result. I was led to write this because it seems that no one has not used numerical computations when checking Shchesnovich's result. And numerical computations are an important science of its own, full of pitfalls.}

Answer 3

The permanent appears in various "weighted" versions of Bézout's theorem (on number of solutions of systems of polynomials). Recall that Bézout's theorem says that the number of isolated solutions of $n$ polynomials $f_1, \ldots, f_n$ in $n$ variables is bounded by $\prod_i \deg(f_i)$. The weighted version of Bézout's theorem generalizes this bound to $\prod_i (\omega(f_i)/\omega(x_i)$, where $\omega$ is any "weighted degree" with positive weights. This is further generalized by the "weighted multi-homogeneous" version which lets you partition the variables into a bunch of (disjoint) groups and consider separately the weights on these groups, and this is where permanent appears naturally.

Indeed, let $I_1, \ldots, I_s$ be a partition of $[n] := \{1, \ldots n\}$, i.e. $[n] = \bigcup_j I_j$ and $\sum_j |I_j| = n$. For each $j$, fix a weighted degree $\omega_j$ on $(x_k: k \in I_j)$ such that

1. $\omega_{j,k} := \omega_j(x_k)$ is positive for each $j,k$, and
2. the $\gcd$ of the weights $\omega_{j,k}$ is $1$ for each $j$.

Then the weighted multi-homogeneous Bézout bound for the number of isolated zeroes of $f_1, \ldots, f_n$ is $$\frac{\text{perm}(D)}{(\prod_j n_j!)(\prod_{j,k} \omega_{j,k})}$$ where $n_j := |I_j|$ and $D$ is the following matrix: $$ \begin{pmatrix} d_{1,1} & \cdots & d_{1,1} & \cdots & \cdots & d_{1,s} & \cdots & d_{1,s} \\ \vdots & & \vdots & & & \vdots & & \vdots \\ d_{n, 1} & \cdots & d_{n,1} & \cdots & \cdots & d_{n,s} & \cdots & d_{n,s} \end{pmatrix} $$ where each $d_{i,j} := \omega_j(f_i)$ is repeated $n_j$ times in the $i$-th row.

One can also try to generalize the weighted bound and the weighted multi-homogeneous bound to incorporate non-positive weights, see Theorems X.36 and X.39 of arxiv:1806.05346 for my attempts - permanent appears naturally in both places. The classical versions described above are also treated in that document (see Chapter VIII).

As asked by OP in a comment below, all these are related to mixed volumes of polytopes via the Bernstein-Kushnirenko theorem. More precisely:

• The Bézout bound $\prod(\deg(f_i))$ is the mixed volume of simplices $\{\alpha \in \mathbb{R}_{\geq 0}^n: \alpha_1 + \cdots + \alpha_n \leq \deg(f_i)\}$.

• More generally, the weighted Bézout bound is the mixed volume of simplices $\{\alpha \in \mathbb{R}_{\geq 0}^n: \langle \omega, \alpha \rangle \leq \omega(f_i)\}$.

• More generally, the weighted multi-homogeneous Bézout bound is the mixed volume of products of the above simplices.

• If $\omega = (\omega_1, \ldots, \omega_n)$ has some negative/zero components, then the problem is that the polyhedron $\{\alpha \in \mathbb{R}_{\geq 0}^n: \langle \omega, \alpha \rangle \leq \omega(f_i)\}$ is unbounded, and one has to decide on a polytope that has a facet on the hyperplane $\{\alpha:\langle \omega, \alpha \rangle = \omega(f_i)\}$. One natural choice is to bound the body by hyperplanes parallel to coordinate hyperplanes, i.e. to consider the polytopes $$\{\alpha \in \mathbb{R}_{\geq 0}^n: \langle \omega, \alpha \rangle \leq \omega(f_i),\alpha_j \leq \deg_{x_j}(f_i)\ \text{for all}\ j\ \text{such that}\ \omega_j \leq 0\}$$ The general weighted (respectively, weighted multi-homogeneous) Bézout bound cited above corresponds to the mixed volume of these (respectively, products of these) polytopes.