1
$\begingroup$

I have a square matrix $U$ of dimension $L\times L$, I am interested in the following quantity

$U_{1,j}U_{2,k}U_{3,l}U_{4,m}\cdots U_{L,q}$

summed over all permutations of the letter indices, e.g., $\{j,k,l,m,\cdots q\}$ is an element of Permutations[Range[L]]. What is a fast and efficient way of doing this? I am using the following function:

f[mat_, l_] := Total[Product[Part[mat, j, #[[j]]], {j, l}] & /@ Permutations[Range[l]]]

which is very inefficient. In fact it even runs out of memory for $L>11$

$\endgroup$
  • 3
    $\begingroup$ Permanent[] is a built-in function, but it is not very fast. You might want to look at the solutions here. $\endgroup$ – J. M.'s technical difficulties Dec 18 '15 at 17:28
  • $\begingroup$ @J.M. Thanks for your suggestion. I was wondering if there is a matrix operation corresponding to what I want to do. It is indeed the permanent. Thanks for pointing this out. $\endgroup$ – user64620 Dec 18 '15 at 17:37
3
$\begingroup$

To settle this:

The function being sought by the OP is actually now built-in into Mathematica as Permanent[]. Unfortunately, it is not terribly quick. You can, for instance, use a function like the one in this answer instead.

permanent[mat_?SquareMatrixQ] := Module[{l = Length[mat] - 1, b}, b = 2^l; 
          PadRight[{}, b, {1, -1}].(Times @@@
          ((2 IntegerDigits[2 b - Experimental`GrayCode[l] - 1, 2] - 1).mat))/b]

AbsoluteTiming[permanent[Array[C, {3, 3}]] // Simplify]
   {0.001485, C[1, 3] (C[2, 2] C[3, 1] + C[2, 1] C[3, 2]) +
    C[1, 2] (C[2, 3] C[3, 1] + C[2, 1] C[3, 3]) +
    C[1, 1] (C[2, 3] C[3, 2] + C[2, 2] C[3, 3])}

AbsoluteTiming[Permanent[Array[C, {3, 3}]] // Simplify] (* built-in *)
   {0.005706, C[1, 3] (C[2, 2] C[3, 1] + C[2, 1] C[3, 2]) +
    C[1, 2] (C[2, 3] C[3, 1] + C[2, 1] C[3, 3]) +
    C[1, 1] (C[2, 3] C[3, 2] + C[2, 2] C[3, 3])}
$\endgroup$

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.