computing Ryser's formula for the permanent I am a bit confused on how to actually use Ryser's formula for the calculation of permanents of a square matrix. Wikipedia states the formula as:
$$ \mathrm{perm}(A)= (-1)^n \sum_{S \subset \{1,2,...,n\}}(-1)^{|S|} \prod _{i=1}^{n} \sum_{j \in S} a_{ij}$$
for a matrix, such as
$A=\begin{pmatrix}a & d & g\\ 
b & e & h\\
c & f & i
 \end{pmatrix}$, I am a bit confused on how to compute the permanent according to the above equation. Here A has nine different elements, but I am a bit unsure specifically on the how to calculate it explicitly. The wiki article mentions something about calculating row sums, but it is not obvious to me if $|S|$ would be referring to specific subsets. Just need to see an example of how Ryser's equation works and I think I will understand.
 A: The permanent is defined to be a sum of all products, where you pick one element from each row, and every choice has to come from distinct rows.
For this 3 x 3 matrix, that would be
$ aei + ahf + dbi + dhc + gbf + gec $
Computing this quantity for a large matrix requires a lot of computation. Ryser is trying to speed that up.
Sometimes, you can compute a sum of product by doing a product of sum, much faster, for example:
$ (a + b + c)(d + e + f) $ requires 4 adds and 1 multiplication
is the same as
$ ad + ae + af + bd + be + bf + cd + ce + cf $ which requires 8 additions and 9 multiplications.
Sadly, there are no good factorization for just the permanant sum, not one that can give significant speed up anyway.
That being said, it is easy to over-compute, for example, $ (a + d + g)(b + e + h)(c + f + i) $ will contain all terms in the permanent, we just created a lot more terms, which we need to figure out a way to cancel them.
That explains the product-of-sum part of the formula above, the goal is to compute a sum-of-product faster through product-of-sum. The alternative signs is meant for cancellation.
That hopefully gives the intuition of the formula. Now let's get to the details.
To avoid clutter, let's just consider the only the terms starting with $ a $, we have
$$
(a + d + g)(b + e + h)(c + f + i) = \\
abc + abf + abi + \\
aec + aef + aei + \\
ahc + ahf + ahi + \cdots
$$
Out of all the terms starting with $ a $, there are only two terms we wanted, $ aei $ and $ ahf $. The remaining term have chosen a value coming from the same column. Now let's consider this term
$$
(a + d)(b + e)(c + f) = \\
abc + abf + \\
aec + aef  + \cdots
$$
By considering terms only coming from the first two columns, now we can cancel all of them from the equation. We will also want to do the same for column 1 and 3 (note that we should consider column 2 and 3 as well, but they won't contain any term starting with $ a $, so we can ignore it for it now)
$$
(a + g)(b + h)(c + i) = \\
abc + abi + \\
ahc + ahi + \cdots
$$
That's great, we get 4 more terms to cancel, but wait, out of the 9 terms in the full expansion, 2 terms are useful, and now we can cancelling 8 of them? (4 of them from each pair of columns)
The problem is that $ abc $ is cancelled twice, this is because $ abc $ coming from column 1 only, that is why we need to add back $ abc $.
That is why you would want to have alternating sign, for product-of-sum consisting two columns, you would want to subtract. For product-of-sum consisting of just one column, you would like to add it back.
This is the intuition behind that formula, the rigorous proof for this is done by modifying the proof of the inclusion-exclusion principle, which this illustration looks very much alike anyway.
Here is a link where I learn the idea from, I hope it helps.
