Introduction

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.

Try It

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">Edit the matrix, then compute. The <b>determinant</b> and the <b>permanent</b> are the same sum over permutations — the determinant keeps the +/- signs, the permanent throws them away. Watch how the term count grows as n!.</p>
<div class="size">
  <span>Size:</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 both</button>
  <button id="terms" type="button" class="ghost">Show all terms</button>
  <button id="random" type="button" class="ghost">Randomize</button>
</div>
<div class="results">
  <div class="card det"><span class="lbl">Determinant (signed)</span><span id="detVal" class="val">—</span></div>
  <div class="card per"><span class="lbl">Permanent (all +)</span><span id="perVal" class="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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The determinant and permanent are BOTH sums over the n! permutations sigma of
    // the product a[0][sigma0]*a[1][sigma1]*...  The determinant multiplies each term
    // by sign(sigma) (+1 / -1); the permanent uses +1 for every term. Identical formula,
    // minus the signs. Determinant is in P (Gaussian elimination, ~n^3); the permanent
    // is #P-complete (Valiant, 1979) — its positive terms never cancel.
let n = 3;
let A = [];
const $ = id => document.getElementById(id);

function buildMatrix(seed){
  A = [];
  for(let i=0;i<n;i++){ A.push([]); for(let j=0;j<n;j++){
    A[i].push(seed ? Math.floor(Math.random()*9) - 2 : (i===j?2:(i+j)%3)); } }
  renderMatrix();
}
function renderMatrix(){
  const m = $('matrix'); m.style.gridTemplateColumns = `repeat(${n}, 46px)`; m.innerHTML='';
  for(let i=0;i<n;i++)for(let j=0;j<n;j++){
    const inp=document.createElement('input'); inp.type='number'; inp.value=A[i][j];
    inp.addEventListener('input',()=>{ A[i][j]=parseInt(inp.value||'0',10); });
    m.appendChild(inp); }
}
// All permutations of [0..n-1].
function permutations(arr){
  if(arr.length<=1) return [arr.slice()];
  const out=[];
  for(let i=0;i<arr.length;i++){ const rest=arr.slice(0,i).concat(arr.slice(i+1));
    for(const p of permutations(rest)) out.push([arr[i]].concat(p)); }
  return out;
}
function sign(p){ // parity of permutation
  let s=1; for(let i=0;i<p.length;i++)for(let j=i+1;j<p.length;j++) if(p[i]>p[j]) s=-s; return s;
}
function evalBoth(){
  const idx=[...Array(n).keys()]; const perms=permutations(idx);
  let det=0, per=0; const terms=[];
  for(const p of perms){ let prod=1; for(let i=0;i<n;i++) prod*=A[i][p[i]];
    const sg=sign(p); det+=sg*prod; per+=prod; terms.push({p,prod,sg}); }
  return {det,per,terms};
}
function compute(){
  const r=evalBoth(); $('detVal').textContent=r.det; $('perVal').textContent=r.per; $('expand').innerHTML='';
  console.log('det =',r.det,'per =',r.per,'over',r.terms.length,'terms');
}
function showTerms(){
  const r=evalBoth(); let html=i18nFmt('<span class="nterms">%length% = %n%! terms</span>', { length: r.terms.length, n: n }) + "\n";
  const fmt=t=> (t.sg<0?'−':'+') + ' ' + t.p.map((c,i)=>'a'+(i+1)+(c+1)).join('·') + ' = ' + (t.sg*t.prod);
  html += i18nFmt('DET (signed): %map% = %det%', { map: r.terms.map(fmt).join('  '), det: r.det }) + "\n\n";
  html += i18nFmt('PER (all +):  %map% = %per%', { map: r.terms.map(t=>'+ '+t.p.map((c,i)=>'a'+(i+1)+(c+1)).join('·')+' = '+t.prod).join('  '), per: r.per });
  $('expand').innerHTML=html;
}
document.querySelectorAll('.size button').forEach(b=>b.addEventListener('click',()=>{
  document.querySelectorAll('.size button').forEach(x=>x.classList.remove('on'));
  b.classList.add('on'); n=parseInt(b.dataset.n,10); buildMatrix(false);
  $('detVal').textContent='—'; $('perVal').textContent='—'; $('expand').innerHTML=''; }));
$('compute').addEventListener('click',compute);
$('terms').addEventListener('click',showTerms);
$('random').addEventListener('click',()=>{ buildMatrix(true); compute(); });
buildMatrix(false);
Result
Console

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.

The Real Complexity

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 n3n^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/determinant-vs-permanent/Content licensed under CC BY-NC 4.0.