2
$\begingroup$

Ryser has shown that the permanent of an $n \times n$ matrix $A=(a_{ij})$ can be expressed as

\begin{align} Perm(A) = (-1)^n \sum_{s \subset [n]} (-1)^{|s|} \prod_{i=1}^n \sum_{j \in s} a_{ij}, \end{align}

where $[n]=\{1,2,\dots,n\}$. This algorithm runs in $\mathcal{O}(2^{n-1}n^2)$ time. I've been trying to derive this, but can't quite get the result. Here's my work so far.

The outer sum is over all non-empty subsets of $[n]$, of which there are $2^n-1$. We recall that the number of subsets of size $r$ is ${n \choose r}=\frac{n!}{r!(n-r)!}$.

For each set $s$ in the outer sum we compute $\sum_{j \in s} a_{ij}$, which uses $|s|-1$ additions. Next, this sum sees the product $\prod_{i=1}^n$, which takes $n-1$ multiplications. This happens for each non-empty subset of $[n]$, so there are the following number of total additions:

\begin{align} \sum_{s \subset [n]} \left(|s|-1\right) &= \sum_{k=1}^n (k-1) {n \choose k} \\ &= \sum_{k=1}^n k {n \choose k} - \sum_{k=1}^n {n \choose k} \\ &= n \sum_{k=1}^n {n-1 \choose k-1} - \left(2^n - 1\right) \\ &= n \left( 2^{n-1}-1 \right) - \left(2^n - 1\right) \\ &=n2^{n-1} - 2^n -n +1. \end{align}

The total number of multiplications is $(n-1)(2^n-1)$.

There is also the $(-1)^{|s|}$, which takes another $2^n-1$ operations in total.

This gives us a grand total of $n2^n + n 2^{n-1} - 2^n -2n+1$, which is not correct. It looks like I'm off by a factor of $n$ on the second term here. Where am I going wrong?

$\endgroup$

1 Answer 1

3
$\begingroup$

For a given $s$, you do $(|s|-1)n$ additions, not $|s|-1$ additions: you have to compute the inner sum for each $i\in [n]$. Thus, you are missing a factor of $n$.

$\endgroup$

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.