22
$\begingroup$

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.

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.

$\endgroup$
26
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ To be more precise about what "represented by a permanent means", if I remember correctly the norm squared of a permanent of an $n \times n$ unitary matrix is the probability that $n$-interacting bosons, each passing through a gate with $n$ input states and n output states described by that unitary matrix, end up in $n$ distinct output states. The probability of particles appearing with some multiplicity in the output states is given by the permanent with the rows repeated the corresponding number of time. $\endgroup$ – Will Sawin Aug 29 '17 at 18:18
  • $\begingroup$ @WillSawin --- yes, thanks for the clarification, for a more extensive description see this Wikipedia page --- and note that the bosons should be non interacting. $\endgroup$ – Carlo Beenakker Aug 29 '17 at 20:39
  • $\begingroup$ Good point - $n$-interacting was a typo for $n$ non-interacting. $\endgroup$ – Will Sawin Aug 29 '17 at 20:51
  • $\begingroup$ @WillSawin If $FP=\#P$ you argument that 'The computational complexity of the evaluation of a permanent explains why it is possible to design a quantum computer with linear optics' goes away. $\endgroup$ – Turbo Dec 6 '18 at 8:46
  • 1
    $\begingroup$ @Freeman. That wasn't my argument, but rather Carlo's. One could say that if P=BQP any argument that explains why it is possible to design a quantum computer must go away, so it isn't so surprising that there is some theoretically possible failure case. $\endgroup$ – Will Sawin Dec 6 '18 at 22:49
13
$\begingroup$

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 immanant1 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 theorem2 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 Conjecture3 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:

enter image description here

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'):

enter image description here

wherein 'Soules POT', a little goofily (I think4), 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.5)

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.

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

2 Issai Schur: Uber endliche Gruppen und Hermitische Formen, Mathematische Zeitschrift 1, p. 184-207.

3 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)

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

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

$\endgroup$
  • 1
    $\begingroup$ Please see mathoverflow.net/a/108533/8430 --- it seems you are mixing up Soules' conjecture (now refuted) with permantental dominance (in a sequence of normalized immanants); the latter is still open. $\endgroup$ – Suvrit Sep 1 '17 at 15:28
  • $\begingroup$ @Suvrit: many thanks for pointing this out. I tried to improve the answer. I also tried to analyse what happened here. It seems that my mind was misled by the (with all due respect) silly moniker 'Permanent On Top Conjecture', which I mistook to talk of the 'top element' interpretation. Thanks again. If there is something wrong still, please let me know. $\endgroup$ – Peter Heinig Sep 1 '17 at 20:03
  • $\begingroup$ Thanks, looks good; of these the per-in-per is really very nice; but of course, there are so many other nice open problems on permanents (Cheon & Wanless's survey covers some). What do you mean by "certification of ... disproof" though? $\endgroup$ – Suvrit Sep 1 '17 at 21:38
  • $\begingroup$ @Suvrit: thanks for having a look. Re "What do you mean": getting into this in detail would be inappropriate. Briefly, I more or less mean: a proof in the 'classical' sense, by a finite number of logical deductions from axioms (or lemmas) in some respected proof system. Results which at some point have recourse to "help of computation utility" (to use Zhang's words in the survey), to my mind are not mathematics, rather an interesting hybrid of experimental physics and mathematics. This is not to blame anyone. 'Hybrid proofs' of this kind are an important phenomenon in modern mathematics,[...] $\endgroup$ – Peter Heinig Sep 2 '17 at 8:41
  • $\begingroup$ [...] and e.g. there is the problem of constructing a humanly checkable proof that an $n$-vertex triangle-free graph can contain at most $(n/5)^5$ distinct $5$-circuits, the first published 'proofs' of which appeal to machine computations, and do so to a larger extent than Shchesnovich's. Finally, disclaimer: I do not have any grounds to doubt Shchesnovich's results. (Already for the strong reasons that I did not read that paper; the paper's existence was pointed out to me only after I wrote the first version of my answer to the OP.) $\endgroup$ – Peter Heinig Sep 2 '17 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.