7
$\begingroup$

What is the exact number of multiplication operations and addition operations needed to calculate the permanent in Ryser's formula (both original and the Gray coded version)?

I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for $4 \times 4$ determinant where he uses Gaussian elimination. He mentions estimating the precise gap between permanent and determinant calculation for $4 \times 4$ is already a notorious open problem.

I am also looking for counts for other calculations/formulas of Permanent.

$\endgroup$
8
  • 2
    $\begingroup$ It would be useful to add a link to the referred formula (or even mention it inline) $\endgroup$ Nov 8 '11 at 17:42
  • $\begingroup$ A good upperbound seems to be stated in the Wikipedia article so I am confused about the motivation for this question. $\endgroup$
    – Kaveh
    Nov 8 '11 at 22:11
  • $\begingroup$ It's possible the key word here is "exact" i.e without O() ? $\endgroup$ Nov 8 '11 at 23:56
  • 1
    $\begingroup$ @SureshVenkat Yes. Precisely. I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for 4x4 determinant where he uses Gaussian elimination. scottaaronson.com/talks/wildidea.ppt He mentions estimating the precise gap between permanent and determinant calculation for 4x4 is already a notorious open problem. $\endgroup$
    – v s
    Nov 9 '11 at 0:33
  • 2
    $\begingroup$ @vs: thanks for the explanation. :) By the way, it might be better to include what you wrote in the comment about inside the post so other would know why you are interested in the problem without a need to read comments. $\endgroup$
    – Kaveh
    Nov 9 '11 at 0:49
7
$\begingroup$

Ryser: $n(n-2)2^{n-1} + n$ additions and $(n-1)(2^{n}-1)$ multiplications.

Ryser+Gray code: $n(2^{n}-2)$ additions and $(n-1)(2^{n}-1)$ multiplications.

Number of multiplications: For each nonempty subset of $[n]$, $n-1$ multiplications are used to multiply $n$ sums together.

Number of additions for Ryser: for each nonempty $S \subseteq [n]$, and for each $i \in [n]$ you compute $\sum_{j \in S} a_{ij}$ which uses $|S|-1$ additions. $\sum_{\emptyset \neq S \subseteq [n]}(|S|-1) = \sum_{k=1}^{n} (k-1) \binom{n}{k} = \sum_{k=1}^{n} k \binom{n}{k} - \sum_{k=1}^{n} \binom{n}{k} = n2^{n-1} - (2^{n}-1)$.

Additions for Ryser+Gray: The Gray code version does not give you a smaller formula, but only a smaller circuit (which is still good, I just thought it was worth pointing out). Its savings require the re-use of previously computed quantities. For each $i \in [n]$, it does a Gray code over the nonempty sets $S \subseteq [n]$. Since there are $2^{n}-1$ such sets, and each transition of the Gray code involves a single addition/substraction, that gives the $2^{n}-2$.

$\endgroup$
9
  • $\begingroup$ Are you sure about Ryser + Gray count? It seems to give $3 \times 6 + 2 \times 7=32$ total for $n=3$. However, brute force would give $2(3!)$ multiplies and $3!-1$ additions which will be $17$. For $n=4$, your count gives is $4 \times 14 + 3 \times 15=101$ while brute force would give $3(4!)+4!-1=95$. The gap reduces but still was just wondering! $\endgroup$
    – v s
    Nov 9 '11 at 13:01
  • 1
    $\begingroup$ You can check my reasoning. I'm pretty sure I did it right, but of course it's possible I made a mistake. I would not find it too surprising if either of these algorithms were less efficient than brute force for very small input sizes. After all, as a simpler example, $n! < 2^{n}$ when $n < 4$. $\endgroup$ Nov 9 '11 at 19:05
  • $\begingroup$ Wikipedia claims O(2^(n-1)*n^2) and O(2^(n-1)*n) respectively for these. So you are suggesting that the formula on the "Computing the Permanent" page is off by a factor of 2? $\endgroup$ Dec 20 '21 at 3:30
  • $\begingroup$ @GregoryMorse: big-Oh notation hides any constant factor by definition, so what it says on Wikipedia is consistent with what I wrote. I also spelled out all my calculations so readers can check for themselves. If you find an error in my calculation please do let me know. $\endgroup$ Dec 21 '21 at 9:51
  • $\begingroup$ @JoshuaGrochow no your precise estimations are wrong and wikipedia is right. For every set S is a subset equal of [n] can be partitioned into 2 partitions P0 and P1 such that they can be ordered so S0 in P0, S1 in P1, |S0|+|S1|=n. Therefore the worst case is this average which results in halving so there are actually only 2^(n-1) sums. There is an error and you should be quite a bit less confident in contradicting a source that although can have mistake, is far more authoritative than yourself. Especially since you certainly made a mistake in your calculations based on this simple argument. $\endgroup$ Dec 21 '21 at 20:38

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.