Ryser Matrix Permanent

The permanent of a square matrix is a numerical value similar to the determinant, but computed without alternating signs. For a matrix A, it is defined as the sum over all permutations of the product of the corresponding matrix entries. Ryser's formula provides a subset inclusion-exclusion method to compute the permanent more efficiently than the naive summation of all permutation products.

Worked Example

Consider the 3x3 matrix:

M = [ 2, 4, 1 ] [ 0, 3, 2 ] [ 5, 0, 3 ]

The permanent is the sum over the 6 permutations. Let's compute them:

P(012): M[0,0]*M[1,1]*M[2,2] = 2 * 3 * 3 = 18
P(021): M[0,0]*M[1,2]*M[2,1] = 2 * 2 * 0 = 0
P(102): M[0,1]*M[1,0]*M[2,2] = 4 * 0 * 3 = 0
P(120): M[0,1]*M[1,2]*M[2,0] = 4 * 2 * 5 = 40
P(201): M[0,2]*M[1,0]*M[2,1] = 1 * 0 * 0 = 0
P(210): M[0,2]*M[1,1]*M[2,0] = 1 * 3 * 5 = 15

Adding these 6 products gives the permanent: 18 + 0 + 0 + 40 + 0 + 15 = 73. There are 3 nonzero assignment products.

Experiment

Explore different matrices and see how Ryser's formula computes the permanent:

Open the Ryser Matrix Permanent module.
Select Ones in the Matrix dropdown to see the all-ones 3x3 matrix. The permanent is exactly 6 (which is 3!).
Select Weighted and change the Permutation to see individual selected products highlighted in the visualization.
Use the Step button to iterate through Ryser's formula terms and watch the accumulated sum converge to the permanent value.

Limitations

The permanent is computationally intensive (#P-hard). Ryser's formula reduces the time complexity from O(n!) to O(n 2^n), but it remains impractical for very large matrices. Unlike determinants, the permanent is not invariant under many standard matrix operations (like subtracting a multiple of one row from another), which prevents simple Gaussian elimination-like algorithms. Furthermore, finding a single assignment with minimum cost (Hungarian algorithm) is a different problem and runs in polynomial time, unlike counting all weighted assignments.

References

References used for this module:

SageMath Matrix Documentation - Includes routines for computing the permanent and notes on subset-based algorithms.

Ryser Matrix Permanent