1
$\begingroup$

Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to most efficiently calculate the sum, over all $K$-permutations, of products $A[1,n_1] * A[2,n_2] * ... * A[k,n_K]$?

For example, let $K=3$ and $N=5$. One possible K-permutation is (5, 1, 3), and the corresponding product is $A[1,5] * A[2,1] * A[3,3]$. But what must be calculated is the sum of such products over all K-permutations, e.g.:

$$ A[1,1] * A[2,2] * A[3,3] + \\ A[1,1] * A[2,2] * A[3,4] + \\ A[1,1] * A[2,2] * A[3,5] + \\ A[1,1] * A[2,3] * A[3,4] + \\ A[1,1] * A[2,3] * A[3,5] + \\ A[1,1] * A[2,4] * A[3,5] + \\ ... $$

I am not even sure there is an efficient (polynomial time) solution, the most I have been able to come up with has about $2^M$ complexity which is unacceptable.

$\endgroup$
0
2
$\begingroup$

When $K = N$, the polynomial you are trying to compute is known as the permanent. The best algorithms for computing the permanent use $\tilde{O}(2^N)$ arithmetic operations, see Wikipedia. The VP≠VNP conjecture implies that the permanent cannot be computed using a polynomial number of operations.

For general $K$, your function is a known extension of the permanent. Ryser's algorithm, one of the $\tilde{O}(2^N)$ algorithms for the square case, extends to the rectangular case as well.

$\endgroup$
1
  • $\begingroup$ Thanks. I don't know why I couldn't find this. $\endgroup$ Feb 8 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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