Determinant vs Permanent

Write down the determinant of a square matrix and you get a famous sum over all the ways to pick one entry from each row and column, where half the terms come with a plus and half with a minus. The signs alternate by a tidy rule.

Now do something almost rude: erase every minus sign and add everything up. That sum has a name too — the permanent. The two formulas are typographic twins; the only difference is those signs.

And yet the determinant is one of the easiest quantities in all of mathematics to compute, while the permanent is one of the hardest we know. That gap, opened by a single missing symbol, is one of the most surprising facts in complexity theory.

Here is a small matrix you can edit. Both values are sums over the same set of permutations — the difference is whether the signs are kept (determinant) or thrown away (permanent).

<p class="hint">{{hint}}</p>
<div class="size">
  <span>{{size_label}}</span>
  <button data-n="2" type="button">2×2</button>
  <button data-n="3" type="button" class="on">3×3</button>
  <button data-n="4" type="button">4×4</button>
</div>
<div id="matrix" class="matrix"></div>
<div class="btns">
  <button id="compute" type="button">{{compute_btn}}</button>
  <button id="terms" type="button" class="ghost">{{show_terms_btn}}</button>
  <button id="random" type="button" class="ghost">{{randomize_btn}}</button>
</div>
<div class="results">
  <div class="card det"><span class="lbl">{{det_label}}</span><span id="detVal" class="val">{{empty_val}}</span></div>
  <div class="card per"><span class="lbl">{{per_label}}</span><span id="perVal" class="val">{{empty_val}}</span></div>
</div>
<div id="expand" class="expand"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.size { display: flex; align-items: center; gap: .4rem; margin: .3rem 0 .7rem; font-size: .9rem; }
.size button { padding: .25rem .6rem; }
.matrix { display: inline-grid; gap: 5px; margin: .3rem 0 .7rem; }
.matrix input { width: 46px; height: 40px; text-align: center; font: 600 16px ui-monospace, monospace;
                border: 1px solid #cdd9e3; border-radius: 7px; background: #f3f7fa; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.on { background: #457b9d; border-color: #457b9d; }
.results { display: flex; gap: .7rem; flex-wrap: wrap; }
.card { flex: 1 1 160px; border-radius: 10px; padding: .7rem .9rem; border: 1px solid #cdd9e3; }
.card .lbl { display: block; font-size: .78rem; color: #555; margin-bottom: .2rem; }
.card .val { font: 700 24px ui-monospace, monospace; }
.card.det { background: #e8f3ec; } .card.det .val { color: #0a7d33; }
.card.per { background: #fdecec; } .card.per .val { color: #c92f3c; }
.expand { margin-top: .8rem; font: 13px ui-monospace, monospace; line-height: 1.7; color: #333;
          white-space: pre-wrap; max-height: 220px; overflow: auto; }
.expand .nterms { font-weight: 700; color: #1d3557; }

// Code not found

Click Show all terms to expand the full permutation sum. For the determinant, the signed terms cancel in clever ways, which is why a fast method like Gaussian elimination exists. For the permanent every term is positive, nothing cancels, and there is no known shortcut. Bump the size up and watch the number of terms explode as n-factorial.

Both formulas are a sum over all n! permutations, so a naive evaluation of either is astronomically slow. The difference is what you can do instead.

• The determinant is in P. The signs make the terms cancel along rows and columns, so Gaussian elimination computes it in about $n^{3}$ steps. Easy, fast, taught in week one of linear algebra.
• The permanent is #P-complete. In 1979, Leslie Valiant proved that computing the permanent — even of a 0/1 matrix — is #P-hard: as hard as counting the solutions to any problem in NP. There is no known polynomial algorithm, and finding one would collapse far more than P vs NP.
• Why the gap? Cancellation. The minus signs let the determinant factor and simplify; without them, the positive terms of the permanent have nothing to collapse into.
• A concrete meaning. The permanent of a 0/1 matrix exactly counts the perfect matchings of a bipartite graph — so counting matchings is hard, even though finding one is easy.

This is the headline of counting complexity: deciding whether a solution exists can be polynomial while counting how many exist is #P-hard. The determinant and the permanent are the cleanest illustration in mathematics.

The easy/hard split is not a curiosity — the permanent appears wherever you need to count configurations:

• Perfect matchings: the permanent of a 0/1 adjacency matrix counts the ways to pair up two sets perfectly, central to combinatorics and scheduling.
• Statistical physics: the dimer model — counting how many ways tiles cover a surface — is a permanent in disguise.
• Quantum computing: boson sampling rests on the fact that the output amplitudes of a photonic circuit are permanents, so a quantum device computes something classically intractable.
• Reliability and probability: many "count the valid assignments" problems reduce to a permanent, linking it to SAT counting and #P counting.

Learn why the permanent is hard and you have met the whole landscape of counting problems, where existence is cheap but enumeration is expensive.

The determinant and the permanent are written almost identically, yet they sit on opposite shores of the easy/hard divide. Strip the minus signs and you lose the cancellation that makes the determinant fast; what remains — the permanent — is #P-complete, a difficulty Leslie Valiant pinned down in 1979.

It is a humbling lesson: the hardness of a problem need not be visible in its formula. Sometimes the entire gulf between trivial and intractable hides in a few minus signs — and learning to see where that gulf lives is what complexity theory, and P vs NP, is really about.