GPT-5.6 Sol · elicited by @eternalism_4eva

What is matrix mortality?#

For fixed positive integers d and k, Md(k) asks: given at most k integer d × d matrices, does some nonempty product equal the zero matrix?

Ai1 Ai2 ⋯ Ain = 0, n≥1.

The entries and the length of the product are unbounded, and factors may repeat in any order, so a product is a word over the k generators. Mortality is semidecidable: enumerating products by length finds a zero product whenever one exists. It is decidable when some algorithm also recognizes every family without one. An undecidability theorem says that no single algorithm is correct on all inputs, not that any particular input is hard.

Two related problems test one coefficient instead of the whole product. Scalar zero reachability Zd(k) supplies a row L and a column C and asks whether LYC = 0 for some nonempty product Y; the structured form Z̊ requires every generator to have first column e1. The corner problem Rd(k) fixes the coefficient to one entry. A reduction from one problem to another transfers undecidability toward the target and decidability back toward the source.

How the proofs work#

Every undecidability proof in this series is a computable map from programs to matrix families that are mortal exactly when the program halts. The map is assembled from five stages, each a translation between problems.

  1. Halting as a word equation. A tag system repeatedly reads the first letter of a queue, appends a word, and deletes a fixed number of letters. Everything deleted, followed by the current queue, always equals the initial queue followed by everything appended. Four word pairs turn this identity into a correspondence problem: a solution is a halting run (M3(5)).
  2. A word equation as one coefficient. Word-pair matrices multiply like pairs of words, and one entry of a product is the difference of the two words’ numerical codes, so it vanishes exactly when the words agree. The four pairs can share coordinates: the paired scalar series uses three matrices in dimension four, and a binary code uses two in dimension six.
  3. One coefficient as a zero product. For a row r and column c, the rank-one separator S = cr satisfies SXS = (rXc)S, so a vanishing coefficient becomes a zero product. More generally, a low-rank generator forces every product through a small space, and interface compression reduces mortality to products there.
  4. Fewer generators, lower dimension. Generator packing spells many generators with few letters and pays in dimension. A transition A and a cut UO present a whole sequence of matrices OAnU, and its least dimension is a Hankel rank; M8(2) chooses the separator to lower that rank.
  5. Integer matrices and computability. Multiplying each generator by a nonzero integer clears denominators without creating or destroying zero products. The whole map must be computable; here it is primitive recursive, and Lean checks it.

Each stage carries three obligations. Every halting run must produce a zero. No other product may vanish, including products of malformed words, of words that begin or end in the middle of an encoding, and of words that use a separator in the wrong place. The translation must be computable and end in integer matrices. Most of every proof is spent on the second obligation.

Decidability table#

Undecidability is monotone in both parameters: extra generators may go unused, and A ↦ A ⊕ 0 preserves mortality. The minimal undecidable cells therefore determine the rest. Before this series, the minimal mortality cells were M3(6), M5(4), M9(3), and M15(2) [Cassaigne et al. 2014]. With the constructions here and the reductions of Cassaigne, Halava, Harju, and Nicolas, they are

M: M3(5),M4(4),M6(3),M8(2); Z: Z3(4),Z4(3),Z6(2); R: R3(5),R4(4),R5(3),R7(2).
Decidability of Md(k): literature audited through 24 July 2026; repository results through 5 September 2026
d \ k 1 2 3 4 5 ≥6
1DDDDDD
2DD????
3D???U★U
4D??U★U★U
5D??UUU
6–7D?U★UUU
8DU★U★UUU
9DU★UUUU
10–11DU★UUUU
12–14DU★UUUU
≥15DUUUUU

D means decidable, ? unresolved, and U undecidable. U★ marks cells first resolved by this series; each star links to the earliest article establishing the cell, directly or as a corollary. The other U entries follow from earlier work and monotonicity. A single matrix is mortal exactly when it is nilpotent, which is decidable, and 1 × 1 products vanish only when a factor is zero. Two 2 × 2 matrices are decidable by Bournez and Branicky [Bournez–Branicky 2002]. Question marks report the state of the literature and imply no prediction.

Reading paths#

Each article states what it uses under Known Stuff and links there, so any theorem can be read from its own page. Read in this order, each article supplies what the next assumes:

ResultArticles in order
M3(5), M6(3), GPCP(4)M3(5)
M4(4), Z4(3)M3(5), paired scalar series, M4(4)
Z6(2), R7(2), M10(2)M3(5), paired scalar series, binary compilers
M8(2), M9(2)M3(5), paired scalar series, M4(4), interface compression, M8(2)
Families in M3(2)interface compression, valuation guard, shortcut-Collatz incidence

The smallest open cell#

M3(2) is the smallest unresolved two-generator cell. Pairs with a zero generator, with two invertible generators, or with a rank-one generator are decidable, which leaves one invertible and one rank-two generator, or two rank-two generators. For each of these a page here exhibits a family whose mortality is exactly an arithmetic orbit question: a deterministic p-adic orbit reaching 1 in the valuation guard, and shortcut-Collatz reachability of a given integer in shortcut-Collatz incidence. A decision procedure for M3(2) would decide these questions; an undecidability proof would have to compile a universal computation into orbits of this kind. Neither is known.

Reference#

Modules#

The layers follow the stages of the proofs described above. Each card links to its statement, which is not necessarily the beginning of an article.

Kind
What the box states: a definition, a construction, a lemma, a reduction (a correctness-preserving translation), a theorem (a principal conclusion), an obstruction (a proved limit), or a witness.
Edges
Requires and Used by are the proof dependencies; other named links, such as Instantiates and Strengthens, are cross-references, not dependencies.

Problems#

The decision problems the constructions start from and end at.

  1. Definition

    Matrix mortality

    Whether some nonempty product of finitely many integer matrices is zero, with the dimension d and the number k of matrices fixed.

  2. Definition

    Two-generator projective incidence

    Whether some product of two invertible rational 2 × 2 matrices moves a given column into the kernel of a given row.

  3. Definition

    Shortcut-Collatz reachability

    Whether a given integer reaches 1 under x ↦ x/2 for even x and x ↦ (3x + 1)/2 for odd x.

Halting as a Word Equation#

The undecidable source: tag-system halting as equality of two concatenations with a fixed boundary.

  1. Theorem

    Fixed-boundary correspondence

    Four of Neary’s word pairs with one fixed boundary word recognize halting of binary tag systems, for every word over the pairs.

A Word Equation as One Coefficient#

Matrix representations whose single coefficient vanishes exactly on solutions, with fewer generators or coordinates than the naive encoding.

  1. Definition

    Word-pair matrices

    Three-dimensional integer matrices that multiply like pairs of words and detect equality of the two words in one entry.

  2. Reduction

    Paired-role compression

    Four maps that agree in pairs on an r-dimensional subspace become two data maps and a toggle in dimension 2d − r, with the same coefficients.

  3. Construction

    Paired scalar series

    Three integer 4 × 4 matrices whose coefficient vanishes on a word exactly when the decoded tiles solve fixed-boundary correspondence; four dimensions are exact.

  4. Construction

    Six-dimensional scalar compiler

    Two-bit codewords spell the four tiles; sharing coordinates after the phase bit gives two 6 × 6 matrices with the same coefficients.

One Coefficient as a Zero Product#

Separators and cuts that make a whole product vanish exactly when a coefficient does, including separator rows chosen to reduce dimension.

  1. Reduction

    Rank-one separator

    A rank-one generator built from the boundary row and column turns a vanishing coefficient into a zero product; the converse covers every product.

    Requires
    Matrix mortality
    Instantiates
    Interface compression

  2. Reduction

    Interface compression

    Mortality of transitions and factored cuts equals mortality of the transitions or of a path of small interface bridges.

    Requires
    Matrix mortality

  3. Reduction

    Singular-return compression

    For a transition A with no vanishing power and a cut UO, the pair is mortal exactly when its returns O Aⁿ U are.

  4. Lemma

    Finitely many return shapes

    If every return is a nonzero multiple of one of finitely many matrices, each occurring, the returns and those matrices are mortal together.

  5. Construction

    Tilted separator

    A separator row (1, q, q, q) whose zeros are exactly those of the paired series, by injectivity of the tilted code σ(x) + q·3^|x|.

  6. Lemma

    Wrong-phase exclusion

    The rule-phase value of the asymmetric row never vanishes: a zero would force a forbidden period of the body’s code.

  7. Construction

    Asymmetric separator

    The row (1, a, q, q) fixed by two linear conditions accepts only deletion-phase zeros; a leading toggle recovers every other witness.

Two Generators, Low Dimension, Integer Entries#

Realizations that present many shapes with two matrices, their limits, and the passage from rational to integer entries.

  1. Reduction

    Generator packing

    Spelling generators in a prefix code trades generators for dimension: M_d(hk + 1) reduces to M_kd(h + 1).

    Requires
    Matrix mortality

  2. Construction

    Binary prefix decoder

    A complete binary prefix code spells the five matrices of M₃(5) on four blocks of dimension three; a synchronizing word handles every start.

    Instantiates
    Generator packing

  3. Reduction

    Common-image restriction

    Both twelve-dimensional generators map into a ten-dimensional subspace; one appended letter turns every restricted zero into an original zero.

  4. Construction

    Nine-dimensional return realization

    A transition with Jordan blocks of sizes 3, 3, 2 and one eigenline whose returns are the three controls and multiples of the tilted separator.

    Requires
    Tilted separator

  5. Obstruction

    Floor for uniform rows

    At a benchmark source, every exact realization of the uniform-row return sequences needs nine dimensions, for every tail and slope.

    Requires
    Tilted separator

  6. Construction

    Eight-dimensional return realization

    Two nilpotent chains of length three, one static coordinate, and one eigenline realize a scaled toggle, both data controls, and the asymmetric separator.

  7. Lemma

    Denominator clearing

    Scaling each generator by its own nonzero integer preserves and reflects every zero product, and unreduced fractions keep the scaling primitive recursive.

    Requires
    Matrix mortality

Undecidability Theorems#

Each card states whether the cell is on the current frontier or implied by a sharper theorem.

  1. Theorem

    M₃(5) is undecidable

    Four tile matrices and one rank-one separator. On the current frontier.

  2. Theorem

    M₄(4) is undecidable

    The paired series and one rank-one separator, with a converse for singular controls. On the current frontier.

  3. Theorem

    M₈(2) is undecidable

    The asymmetric separator and an eight-dimensional return realization. On the current frontier; M₇(2) is open.

  4. Theorem

    Z₆(2) is undecidable

    The six-dimensional scalar compiler, with common first column e₁. On the current scalar frontier.

  5. Theorem

    M₆(3) is undecidable

    Generator packing applied to M₃(5). On the current frontier.

  6. Theorem

    R₇(2) is undecidable

    The scalar-to-corner reduction applied to Z₆(2). On the current corner frontier.

  7. Theorem

    M₉(2) is undecidable

    The tilted separator and a nine-dimensional return realization. Subsumed by M₈(2).

  8. Theorem

    M₁₀(2) is undecidable

    The binary prefix decoder restricted to its common image. Subsumed by M₉(2).

  9. Theorem

    M₁₂(2) is undecidable

    Generator packing applied to M₃(5). Subsumed by M₁₀(2).

The Cell M₃(2)#

Exact equivalences between families of 3 × 3 pairs and arithmetic orbit questions; they do not settle the cell.

  1. Construction

    Valuation guard

    Two 3 × 3 matrices whose returns act by Möbius maps, admit one wait per step by a p-adic valuation, and are mortal exactly when a deterministic orbit reaches 1.

  2. Obstruction

    Immortality certificates

    Parity of the reset-defect numerator and valuation walls at primes dividing p − 1 prove large parameter regions of the guard immortal.

    Requires
    Valuation guard

  3. Reduction

    Shortcut-Collatz incidence

    For each nonzero integer n, two fixed Möbius maps and a target depending on n have an incidence exactly when n reaches 1.

  4. Reduction

    Rank-two incidence compiler

    Every generic incidence instance becomes two rational 3 × 3 matrices of rank two, mortal exactly when the instance has a solution.

    Instantiates
    Interface compression