Permanent of a matrix with duplicate rows/columns

Question

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.

Answer 1

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 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)