I'm trying to find an efficient algorithm/technique to calculate, or approximate, the permanent of a matrix. After reading some literature, it seems nothing exists faster than Ryser's algorithm in the general case. Unfortunately this is too slow for my purposes at $O(2^{n-1}n)$.


My matrix has a lot of duplicate columns, and so I was wondering if there was a way to use that structure to improve the efficiency of the calculation, or make an approximation. My matrix looks a bit like this:


$$
A = 
\begin{bmatrix}
A^2 & A^2 & A & A & A & 1 & 1 & 1 & 1\\
B^2 & B^2 & B & B & B & 1 & 1 & 1 & 1\\ 
C^2 & C^2 & C & C & C & 1 & 1 & 1 & 1\\
D^2 & D^2 & D & D & D & 1 & 1 & 1 & 1\\
E^2 & E^2 & E & E & E & 1 & 1 & 1 & 1\\
F^2 & F^2 & F & F & F & 1 & 1 & 1 & 1\\
G^2 & G^2 & G & G & G & 1 & 1 & 1 & 1\\
H^2 & H^2 & H & H & H & 1 & 1 & 1 & 1\\
J^2 & J^2 & J & J & J & 1 & 1 & 1 & 1\\
\end{bmatrix}
$$


Any ideas? Or alternatively a proof that the computation cannot be made more efficient would be very useful.



Permanent of a matrix with duplicate rows/columns
Aha! Here we go.


Just use Ryser's formula exactly as is, but be clever not to redo work you've already done. If it's an $n \times n$ matrix with $F$ distinct columns, you'll be able to compute its permanent in time roughly $F n^{1+F}$ ish (which would be great if you can get $F$ down).


**More details:**


Recall [Ryser's formula](https://en.wikipedia.org/wiki/Computing_the_permanent) is


$$\text{perm}(A) = (-1)^n \sum\_{S \subseteq [n]} (-1)^{|S|} \prod\_{i=1} ^{n} \sum\_{j \in S} a\_{i,j}.$$


The problem is that if we don't do anything clever, then there are too many terms of this sum. But! In our case, *many of these terms are equal*. The thing we're adding up depends on $S$, but it actually just depends on how many columns of each type are in $S$. [If this is already clear, then don't bother reading the rest]


Let's say that the distinct columns of $A$ are $\vec{x}^{(1)}, \vec{x}^{(2)}, \ldots , \vec{x}^{(F)}$ and that $\vec{x}^{(j)}$ appears $f\_j$ times. Then the above sum is equal to


$$\text{perm}(A) = (-1)^n \sum\_{(s\_1, s\_2, \ldots, s\_F)}(-1)^{s\_1 + s\_2 + \cdots + s\_F} \prod\_{j=1} ^{F} {f\_j \choose s\_j} \prod\_{i=1} ^{n} \sum\_{k = 1} ^{F} s\_k \vec{x}^{(k)} \_{i},$$


where the sum is taken over all non-negative vectors [summing to at most $n$, where each coordinate $s\_i$ is at most $f\_i$]. A crude bound is that there are at most $\mathcal{O}(n^F)$ such terms, giving this a running time of at most like $\mathcal{O}(n^{F+1} F)$ or whatever.


Of course, this doesn't use anything about what the columns look like (and the above sum might be easier to compute than just adding up each term). But it's a start.




---


**(Added as per suggestion) Working out $F=3$** Suppose we are in the optimistic case that the matrix has $n$ columns but only $3$ distinct columns. Let's call these columns $\vec{x}, \vec{y}$, and $\vec{z}$, and suppose each appears $f\_x, f\_y,$ and $f\_z$ times (respectively). [So we have $f\_x + f\_y + f\_z = n$]


Then we have


$$\text{perm}(A) = (-1)^n \sum\_{(a, b, c)}(-1)^{a+b+c} {f\_x \choose a} {f\_y \choose b} {f\_z \choose c} \prod\_{i=1} ^{n} (a \vec{x}\_{i} + b \vec{y}\_i + c \vec{z}\_i),$$


where the sum is taken over all triples $(a,b,c)$ summing to at most $n$.


Said slightly differently, for a vector $\vec{u} \in \mathbb{R}^n$, let $V(\vec{u}) = u\_1 u\_2 \cdots u\_n$ be the product of its coordinates. [So $V(\vec{u})$ is the (signed) volume of the axis-parallel box with one corner at the origin and an antipodal corner at $\vec{u}$] Then the above formula is just
$$\text{perm}(A) = (-1)^n \sum\_{(a, b, c)}(-1)^{a+b+c} {f\_x \choose a} {f\_y \choose b} {f\_z \choose c} V(a \vec{x} + b \vec{y} + c \vec{z}),$$
which looks a little nicer to me and feels more geometric. [I'm then tempted to write this linear combination as a product of a matrix and the vector $(a,b,c)$, but let's not]


(If you'd like me to sketch some code or work out an example or something, lemme know)


