API

permanent.opt()

Compute the permanent of a matrix using the best algorithm for the shape of the given matrix.

Parameters:

matrix (np.ndarray(M, N, dtype=(np.double|np.complex)))

Returns:

permanent – Permanent of matrix.

Return type:

(np.double|np.complex)

permanent.combinatoric()

Compute the permanent of a matrix combinatorically.

\[\text{per}(A) = \sum_{\sigma \in P(N,M)}{ \prod_{i=1}^M{a_{i,{\sigma(i)}}} }\]

Parameters:

matrix (np.ndarray(M, N, dtype=(np.double|np.complex)))

Returns:

permanent – Permanent of matrix.

Return type:

(np.double|np.complex)

permanent.glynn()

Compute the permanent of a matrix via Glynn’s algorithm [Glynn].

\[\text{per}(A) = \frac{1}{2^{N-1}} \cdot \sum_{\delta}{ \left(\sum_{k=1}^N{\delta_k}\right) \prod_{j=1}^N{\sum_{i=1}^N{\delta_i a_{i,j}}} }\]

The original formula has been generalized here to work with \(M\)-by-\(N\) rectangular permanents with \(M \leq N\) by use of the following identity (shown here for \(M \geq N\)):

\[\begin{split}{\text{per}}\left( \begin{matrix} a_{1,1} & \cdots & a_{1,N} \\ \vdots & \ddots & \vdots \\ a_{M,1} & \cdots & a_{M,N} \\ \end{matrix} \right) = \frac{1}{\left(M - N + 1\right)!} \cdot {\text{per}}\left( \begin{matrix} a_{1,1} & \cdots & a_{1,N} & 1_{1,N+1} & \cdots & 1_{1,M} \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{M,1} & \cdots & a_{M,N} & 1_{M,N+1} & \cdots & 1_{M,M} \\ \end{matrix} \right)\end{split}\]

This can be neatly fit into the original formula by extending the inner sums over \(\delta\) from \(\left[1,M\right]\) to \(\left[1,N\right]\):

\[\text{per}(A) = \frac{1}{2^{N-1}} \cdot \frac{1}{\left(N - M + 1\right)!} \cdot \sum_{\delta}{ \left(\sum_{k=1}^N{\delta_k}\right) \prod_{j=1}^N{\left( \sum_{i=1}^M{\delta_i a_{i,j}} + \sum_{i=M+1}^N{\delta_i} \right)} }\]

[Glynn]

Glynn, D. G. (2010). The permanent of a square matrix. European Journal of Combinatorics, 31(7), 1887-1891.

Parameters:

matrix (np.ndarray(M, N, dtype=(np.double|np.complex)))

Returns:

permanent – Permanent of matrix.

Return type:

(np.double|np.complex)

permanent.ryser()

Compute the permanent of a matrix via Ryser’s algorithm [Ryser].

\[\begin{split}\text{per}(A) = \sum_{k=0}^{M-1}{ {\left(-1\right)}^k \left(\begin{matrix}N - M + k\\ k\end{matrix}\right) \sum_{\sigma \in P(N,M-k)}{ \prod_{i=1}^M{ \sum_{j=1}^{M-k}{a_{i,{\sigma(j)}}} } } }\end{split}\]

for .. [Ryser] Ryser, H. J. (1963). Combinatorial Mathematics (Vol. 14).

American Mathematical Soc..

Parameters:

matrix (np.ndarray(M, N, dtype=(np.double|np.complex)))

Returns:

permanent – Permanent of matrix.

Return type:

(np.double|np.complex)