skip to content

The permanent and the determinant differ only by the sign attached to each permutation, so why is one polynomial-time and the other #P-complete?

level: seniorimportance: nice to knowfreq 24%

answer

  1. same n! terms, one sign apart
  2. cancellation is what elimination exploits
  3. row operations preserve one, not the other
  4. unsigned sum counts perfect matchings
  5. #P-complete even on 0/1 entries

basics

~20 s

The signs make the determinant change predictably under row operations, so elimination evaluates it in cubic time without touching its factorially many terms. The permanent has no cancellation to exploit, and computing it is #P-complete: it counts a bipartite graph's perfect matchings.

solid answer

~40 s

Both quantities are sums over all `n!` permutations of the product of the entries a permutation selects. The determinant weights each product by the sign of the permutation; the permanent weights every product by one. That single difference is decisive. The signs make the determinant an alternating multilinear function, which is exactly the property row operations preserve, so Gaussian elimination computes it in about `n^3` operations. The permanent has no such algebra: nothing cancels, so no elimination-style shortcut is known, and computing the permanent of a matrix of zeros and ones was proved `#P`-complete. That matrix reading is the punchline — for a bipartite graph's biadjacency matrix, the permanent **is** the number of perfect matchings, while the determinant is a signed sum of the same matchings and can vanish even when many exist.

go deeper

for a junior

Recall that two formulas can look almost identical and still differ enormously in cost, and that the determinant is the cheap one despite its definition summing factorially many terms.

for a middle

Explain the mechanism: the signs make the determinant alternating, row operations preserve it, and elimination therefore avoids the permutation sum entirely, while the permanent offers no such invariance.

for a senior

Demonstrate the consequence in practice: recognise a quantity as a permanent in disguise, such as a count of perfect matchings, and redirect the request to an estimate or to a structural special case.

for a principal

Take the general lesson to design reviews: the cost of a quantity is a property of its algebra, not of how its definition is written, and a requirement for an exact count is where feasibility should be challenged.

## The same sum, one factor apart For an `n`-by-`n` matrix, both quantities range over every permutation of the columns. Each permutation picks one entry from each row, in a different column, and their product is one term: - **Permanent** — add up all `n!` products. - **Determinant** — add up the same `n!` products, each multiplied by `+1` or `-1` according to whether the permutation is even or odd. Written side by side, the permanent looks like the *simpler* object: no signs to track. That is what makes the outcome memorable, because the simpler-looking one is the intractable one. ## What the signs buy The signs turn the determinant into an **alternating** function: swap two rows and the value negates, and a matrix with two equal rows evaluates to zero. Together with linearity in each row, that is precisely the structure row operations respect. Adding a multiple of one row to another leaves the determinant unchanged, because the extra contribution is a determinant with a repeated row and is therefore zero. So you may reduce the matrix to triangular form and multiply the diagonal. Elimination touches on the order of `n^3` entries and never enumerates a single permutation. The `n!` terms were never the real cost; they were an artefact of how the quantity is defined. | | determinant | permanent | |---|---|---| | weight per permutation | sign of the permutation | always one | | behaviour under row operations | unchanged by adding a multiple of a row | no such invariance | | cost | about `n^3` by elimination | no polynomial algorithm known | | classification | polynomial time | `#P`-complete, even on entries of 0 and 1 | | graph meaning of a 0/1 matrix | signed sum of perfect matchings | number of perfect matchings | ## Why the permanent resists the same treatment Without signs there is no cancellation, and cancellation is the whole mechanism. Adding a multiple of one row to another changes the permanent by a term that does not vanish, so the operation destroys the value instead of preserving it. Every natural attempt runs into the same wall, and the classification result explains why the wall is expected to hold: computing the permanent of a matrix whose entries are only zeros and ones is `#P`-complete, so a polynomial-time algorithm for it would give one for every counting problem in `#P`, including counting the satisfying assignments of a formula. ## The graph reading, which makes it concrete Take a bipartite graph with `n` vertices on each side, and build the matrix whose entry is `1` when the corresponding pair is joined by an edge and `0` otherwise. A permutation contributes a product of `1` exactly when every pair it selects is an edge — that is, exactly when the permutation *is* a perfect matching. Therefore: - The **permanent** of that matrix is the number of perfect matchings. - The **determinant** of the same matrix is a signed sum of those matchings, in which matchings of opposite parity cancel. It can be zero for a graph with many perfect matchings, so it does not count them. This lines up with the general separation between finding and counting: a perfect matching can be found in polynomial time, and the count is `#P`-complete. ## Two refinements worth knowing 1. **Structure can restore the signs.** For a graph drawn in the plane without crossing edges, the edges can be oriented so that every perfect matching acquires the same sign. The signed sum then coincides with the unsigned one, and a determinant computes the count in polynomial time. So the hardness is not a property of matchings as such; it is a property of the general case where the cancellation cannot be aligned. 2. **Approximation is a different question.** For a matrix with non-negative entries, a randomized sampling scheme estimates the permanent to within any chosen relative error with any chosen confidence, in polynomial time. Exact hardness and approximate feasibility coexist, which is the recurring lesson of this corner of the subject. ## What this is testing in an interview It is not asking for either formula. It is checking whether you can explain **why a definition's apparent cost is not its real cost**, and whether you notice that a tiny change in an expression can move it across a complexity boundary. The transferable point: a quantity written as a sum over exponentially many objects may still be cheap, if the algebra permits cancellation — and if it does not, the exponential in the definition may be the honest price.

  • If the determinant of a bipartite graph's 0/1 matrix is zero, does the graph have no perfect matching?
    No. The determinant is a signed sum in which matchings of opposite parity cancel, so it can be zero while many perfect matchings exist. Only the unsigned sum, the permanent, counts them. Deciding whether at least one exists is done with a matching algorithm, not by evaluating a determinant.
  • Is counting perfect matchings hard for every graph?
    No. For a graph drawn in the plane with no crossing edges, the edges can be oriented so that all perfect matchings take the same sign, which makes the signed sum equal the unsigned count and lets a determinant compute it in polynomial time. The #P-completeness is about the general case.
  • Does #P-completeness of the permanent rule out useful answers?
    Not by itself. For a matrix with non-negative entries there is a randomized scheme that estimates the permanent within any chosen relative error, at any chosen confidence, in polynomial time. What is ruled out, unless the class collapses, is an efficient exact value.

saying these in an interview costs you the question

  • Assumes the permanent must be easier since it has no signs to track
  • Thinks elimination works for the permanent with minor adjustments
  • Reads the determinant of a 0/1 matrix as a matching count
  • Believes n! terms in a definition always mean factorial cost
  • Concludes that counting matchings is hard for every class of graph