Introduction

Here is a question a curious child could ask. I hand you a small set of matrices — say three of them, full of plain integers. You may multiply them in any order, repeating any of them as often as you like: a long word like A·C·A·B·A. The only question is whether some such product, somewhere, equals the zero matrix — every entry zero.

A set of matrices is called mortal if a zero product exists, and immortal if no product ever reaches zero. So: is this set mortal?

It sounds like the kind of thing a computer eats for breakfast. Just multiply and check. And yet there is no algorithm that can answer it in general — not a slow one, not a clever one, none at all. The question is undecidable, and that is one of the cleanest surprises in all of computation.

Hunt for Zero

Below are three matrices, A, B and C. Click them to append each one to your product (multiplying on the right). The running result updates instantly. Your goal: find a sequence whose product is the zero matrix.

<p class="hint">Click <b>A</b>, <b>B</b> or <b>C</b> to multiply it onto the right of your product. Watch for the <b>zero matrix</b> (every entry 0). Checking a product is instant — finding a zero one means searching words that triple in number every step.</p>
<div class="gens" id="gens"></div>
<div class="word">Word: <span id="word" class="mono">(empty)</span></div>
<div class="result" id="result"></div>
<div class="status" id="status">Build a product, or auto-search for zero.</div>
<div class="btns">
  <button id="undo" type="button" class="ghost">Undo</button>
  <button id="clear" type="button" class="ghost">Clear</button>
  <button id="search" type="button">Auto-search</button>
</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 .8rem; line-height: 1.45; }
.mono { font-family: ui-monospace, monospace; }
.gens { display: flex; gap: .9rem; flex-wrap: wrap; margin: .3rem 0 .9rem; }
.gen { cursor: pointer; border: 1px solid #cdd9e3; border-radius: 10px; padding: .5rem .7rem;
       background: #f3f7fb; text-align: center; transition: all .12s; user-select: none; }
.gen:hover { background: #e6eef6; border-color: #9fb6cc; transform: translateY(-1px); }
.gen .name { font: 700 1.1rem ui-monospace, monospace; color: #1d3557; margin-bottom: .25rem; }
.mat { display: grid; grid-template-columns: repeat(2, 26px); gap: 2px; justify-content: center; }
.mat span { display: flex; align-items: center; justify-content: center; width: 26px; height: 26px;
            font: 600 14px ui-monospace, monospace; background: #fff; border: 1px solid #dde6ee; border-radius: 4px; }
.word { font-size: 1rem; margin: .5rem 0; }
#word { font-weight: 700; color: #1d3557; }
.result { display: grid; grid-template-columns: repeat(2, 38px); gap: 4px; margin: .5rem 0; }
.result span { display: flex; align-items: center; justify-content: center; width: 38px; height: 38px;
               font: 700 17px ui-monospace, monospace; border-radius: 6px; background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.result.zero span { background: #0a7d33; color: #fff; border-color: #086628; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Matrix MORTALITY: given a set of matrices, is there a product (a "word" over
// the matrices, any order, repeats allowed) that equals the zero matrix?
// Checking one product is a quick chain of multiplies; but deciding whether
// ANY product can reach zero is UNDECIDABLE for 3x3 integer matrices (Paterson, 1970) — there is no length at which a search may safely stop. This hand-picked 2x2 set is "mortal": the shortest zero word is A·C·A.
const MATS = {
  A: [0,0,0,1],   // [[0,0],[0,1]]
  B: [0,0,1,1],   // [[0,0],[1,1]]
  C: [0,1,1,0],   // [[0,1],[1,0]]
};
const KEYS = ['A','B','C'];
const mul = (M,N) => [
  M[0]*N[0]+M[1]*N[2], M[0]*N[1]+M[1]*N[3],
  M[2]*N[0]+M[3]*N[2], M[2]*N[1]+M[3]*N[3],
];
const isZero = M => M.every(x => x === 0);
function product(word){           // product of a word, or null if empty
  let P = null;
  for(const ch of word) P = (P===null) ? MATS[ch].slice() : mul(P, MATS[ch]);
  return P;
}

let word = [];

function renderGens(){
  const g = document.getElementById('gens'); g.innerHTML='';
  KEYS.forEach(k=>{
    const m = MATS[k];
    const d = document.createElement('div'); d.className='gen';
    d.innerHTML = '<div class="name">'+k+'</div><div class="mat">'+
      m.map(v=>'<span>'+v+'</span>').join('')+'</div>';
    d.addEventListener('click',()=>{ word.push(k); render(); });
    g.appendChild(d);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function render(){
  document.getElementById('word').textContent = word.length ? word.join('·') : '(empty)';
  const res = document.getElementById('result');
  const P = product(word);
  if(P===null){ res.className='result'; res.innerHTML='<span>?</span><span>?</span><span>?</span><span>?</span>';
    setStatus('Build a product, or auto-search for zero.',''); return; }
  const zero = isZero(P);
  res.className = 'result'+(zero?' zero':'');
  res.innerHTML = P.map(v=>'<span>'+v+'</span>').join('');
  if(zero) setStatus(fmt('Zero matrix! The word %word% is mortal.', { word: word.join('·') }),'ok');
  else setStatus('Not zero yet — keep multiplying.','bad');
}
// Auto-search: breadth-first over all words, increasing length, until a zero
// product is found. Counts how many products it had to examine.
function autoSearch(){
  let examined = 0;
  let level = KEYS.map(k => ({ w:[k], p: MATS[k] }));
  for(const n of level){ examined++; if(isZero(n.p)){ word=n.w; render();
    setStatus(fmt('Found %w% after %examined% products.', { w: n.w.join('·'), examined: examined }),'ok'); return; } }
  for(let len=2; len<=8; len++){
    const next=[];
    for(const n of level) for(const k of KEYS){
      const p = mul(n.p, MATS[k]); examined++;
      const w = n.w.concat(k);
      if(isZero(p)){ word=w; render();
        setStatus(fmt('Found %w% (length %len%) after examining %examined% products.', { w: w.join('·'), len: len, examined: examined }),'ok'); return; }
      next.push({ w, p });
    }
    level = next;
  }
  setStatus('No zero found within length 8 — but that proves nothing.','bad');
}
document.getElementById('undo').addEventListener('click',()=>{ word.pop(); render(); });
document.getElementById('clear').addEventListener('click',()=>{ word=[]; render(); });
document.getElementById('search').addEventListener('click',autoSearch);
renderGens(); render();
Result
Console

Notice the asymmetry. Checking a product you've built is effortless — just multiply and look. But finding a mortal word means searching: there are 3 words of length 1, 9 of length 2, 27 of length 3, and the count triples with every extra letter. Press Auto-search and the computer tries every word in order. For this hand-picked set the answer hides at length three (try A·C·A) — but in general there is no length at which you are allowed to give up.

The Real Complexity

How hard is mortality, really?

  • Checking one product is trivial: multiply the chosen matrices and compare with zero.
  • Brute force tries every word — but the number of words of length up to L grows like kᴸ for k matrices, and there is no upper bound on the length you'd need to try.
  • It's undecidable. In 1970, Michael Paterson proved that for sets of 3×3 integer matrices there is no algorithm that decides whether the set is mortal. He did it by encoding the Post correspondence problem — itself undecidable — into matrices: pairs of strings become matrices, and a matching sequence of strings becomes a product that lands on zero.
  • So the search can never be safely bounded. If your computer hasn't found a zero product yet, that tells you nothing: the answer might be a word a million letters long, or it might never come, and no test can distinguish the two cases.

That is the punchline. Mortality joins the halting problem on the far side of the line: not merely expensive to decide, but impossible to decide. The two-matrix and many low-dimensional cases remain partly open, but for 3×3 the verdict is final and permanent.

Where It Matters

"Apply one of several linear updates, in some order, and ask where you can end up" is the shape of countless real systems — which is why mortality is more than a curiosity:

  • Program verification: a loop that picks among a few linear transformations is exactly a set of matrices; asking whether some run reaches a forbidden state (like the zero vector) is a reachability question with the same impossible core.
  • Hybrid and control systems: machines that switch between linear modes are modeled by matrix products, and stability or safety questions inherit this hardness.
  • The frontier of automation: mortality is a clean landmark showing why fully automatic verification tools must sometimes give up, time out, or answer "don't know."
  • Matrix semigroups: it anchors a whole family of decision problems — membership, freeness, the matrix multiplication machinery they all rely on — many of which are undecidable too.

Understand why matrix mortality is impossible, and you understand why no tool will ever fully verify every loop you write.

Conclusion

Matrix mortality is disarmingly simple to state and stubbornly impossible to solve. Multiplying matrices is something a calculator does without breaking a sweat; deciding whether some product can ever reach zero is something no machine will ever do for every input.

So the next time the auto-search keeps spinning without finding a zero, remember: it isn't being slow, and it isn't broken. You've simply handed it a question from the wrong side of the line — the side it shares with the halting problem — where the honest answer is that there is no answer at all.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/mortal-matrices/Content licensed under CC BY-NC 4.0.