Mortal Matrices

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.

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">{{hint}}</p>
<div class="gens" id="gens"></div>
<div class="word">{{word_label}} <span id="word" class="mono">{{empty}}</span></div>
<div class="result" id="result"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="undo" type="button" class="ghost">{{btn_undo}}</button>
  <button id="clear" type="button" class="ghost">{{btn_clear}}</button>
  <button id="search" type="button">{{btn_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; }

// Code not found

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.

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.

"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.

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.