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.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ It would be useful to add a link to the referred formula (or even mention it inline) $\endgroup$
    – Suresh Venkat
    Commented Nov 8, 2011 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
    Commented Nov 8, 2011 at 22:11
  • $\begingroup$ It's possible the key word here is "exact" i.e without O() ? $\endgroup$
    – Suresh Venkat
    Commented Nov 8, 2011 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
    Commented Nov 9, 2011 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
    Commented Nov 9, 2011 at 0:49

1 Answer 1

Reset to default
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$.

Improve this answer
$\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
    Commented Nov 9, 2011 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$
    – Joshua Grochow
    Commented Nov 9, 2011 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$
    – Gregory Morse
    Commented Dec 20, 2021 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$
    – Joshua Grochow
    Commented Dec 21, 2021 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$
    – Gregory Morse
    Commented Dec 21, 2021 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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