CS Paper Radar

Mortality Is Undecidable for $2 \times 2$ Integer Matrices

Thanin Quartz, Ivan O. Shevchenko, Hans De Sterck, Jun Liu

cs.CC ·submitted 2026-11-04 14:25 UTC · v1

Abstract

The matrix mortality problem asks whether a given finite family of matrices can be multiplied, in any order and with possible repetition, to get the zero matrix. It is one of the most basic decision problems about matrix products, and it arises naturally in the study of switched linear systems and of finite automata. Mortality is trivially decidable in dimension one and has been known to be undecidable for integer matrices in dimensions three and higher since 1970; only the problem in dimension $2$ is left open. We resolve this problem by proving that mortality is undecidable for families of 5,799 distinct $2\times2$ integer matrices. All but one of the matrices are fixed and nonsingular, with determinants $\pm p$ for a single fixed prime $p$. The input affects only the remaining rank-one matrix, which encodes this input into its kernel. Our proof encodes the computation of a fixed universal machine into products of $2\times2$ matrices. We represent each configuration of the computation by a single rational number, which we identify with a line through the origin in $\mathbb{Q}^2$, and each nonsingular matrix carries out a small piece of one computation step. The main difficulty is that the matrices may be multiplied in any order, so we design them to check their own work: a "wrong'' step puts a factor of a prime number $p$ into the denominator of the rational number corresponding to the current computation step, where no later matrix can remove it. As a result, products of these matrices can go from one encoded configuration to another only by following a valid computation. The rank-one matrix then turns the question of whether the machine halts into the question of whether some product equals zero. A companion formalization in the Lean proof assistant verifies the complete reduction.

Closest papers

Nearest neighbours by meaning across the whole index.

Factorisability of Low Dimensional Non-Negative Integer Matrices

cs.DM cs.DScs.IT ·2026-09-22 ·Paul C. Bell, Eva Foster, Daniel Reidenbach, Pavel Semukhin
published similarity 0.65
Abstract · Accepted for publication at 20th International Conference on Reachability Problems, RP 2026

We consider the problem of determining if a given two-dimensional nonnegative integer matrix $M$ is the product of two such matrices, excluding trivial units. A matrix $M$ with no such factorisation is called prime and therefore belongs to the minimal (infinite rank) generator of $2 \times 2$ matrices over the natural numbers, otherwise it is called composite. We also consider the problem of finding a (non-unique) factorisation of a composite matrix. Our results have applications in computational group theory and the theory of codes, where such matrices are called incidence matrices. We analyse the complexity of primality and finding a factorisation for a composite matrix, providing a first efficient algorithm.

0.42

Quadratic bounds for uncompletable words and matrix mortality

cs.FL math.CO ·2026-09-25 ·Rahul Chandelkar, Samrath Singh Chadha
similarity 0.59
Abstract · Lean formalization and implementation pilot included as ancillary material

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

0.33

Explicit matrix hitting points for noncommutative algebraic branching programs

cs.CC math.RAmath.CO ·2026-10-11 ·Zhipeng Lu
similarity 0.58
Abstract · 24 pages. There's statement about reproducibility and Lean verification in section 5

We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\ge1$ and an ABP vertex bound $S\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.

0.16

The rank of 3x3 matrix multiplication over F2 is 23

cs.CC math.RA ·2026-10-08 ·Tejasvi Singh Tomar
theorycode/data similarity 0.58
Abstract · 18 pages. Kernel-only Lean proof: https://github.com/tejasvi/rank333-f2-kernel (archived at https://doi.org/10.5281/zenodo.23304899). Lean p…

The rank of the tensor of $3\times 3$ matrix multiplication over the field with two elements is at most $23$ by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least $22$. We prove that it equals $23$. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over $\mathbb{F}_2$ and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for $111$ of Wang's $496$ classes of subspaces, constrain the ranks of the first factors through a $27\times 27$ flattening of the tensor, and list, up to symmetry, all sets of $22$ first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

0.22

A Lower Bound of 21 for $3\times3$ Matrix Multiplication over $\mathbb{F}_2$

cs.CC cs.DS ·2026-09-06 ·Chengu Wang
theory similarity 0.57
Abstract

We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$. Lower bounds for restrictions of the first input constrain how many first factors of a decomposition can lie in each subspace. For a hypothetical $20$-term decomposition, the strengthened restriction bounds force all first factors of matrix rank at least two into a single coset of a three-dimensional rank-one subspace. An exhaustive computation finds no admissible first-factor profile with $20$ terms. We also prove that $2\times3$ by $3\times3$ matrix multiplication over $\mathbb{F}_3$ has rank exactly $15$: three profiles with $14$ terms survive the corresponding computation up to symmetry, and short restriction arguments exclude them. We combine Wang's automated framework for tensor-rank lower bounds with D'Ambrosio's capacity-and-profile strategy. Our computational contributions are rank-one-span searches that strengthen the subspace lower-bound table and a direct, symmetry-reduced profile enumerator that enforces all subspace capacities simultaneously.

0.28

Partial Homogenization and the Structure of Optimal Algebraic Algorithms

cs.SC ·2026-11-17 ·Yuval Spiizer
theory similarity 0.57
Abstract

A quadratic map, such as the product of two polynomials, two complex numbers or two matrices, is classically computed by products of two linear forms. By Strassen's homogenization, their least number is also the least number of product gates of fan-in two. With unbounded fan-in, terms of higher degree can cancel, so the classical lower bounds and classifications do not apply. We ask whether unbounded fan-in beats fan-in two, and what the optimal circuits are. Our tool is constant-free partial homogenization, which keeps the terms of higher degree. Let a quadratic map have $K$ independent outputs. We prove that, under a mild condition, unbounded fan-in needs as many product gates as fan-in two whenever fan-in two needs at most $K+2$. For $2\times2$ matrix multiplication, we classify all optimal circuits with fan-in two and arbitrary constants. We prove that none of them nests products, and that their quadratic parts are Strassen's algorithm, one new algorithm, the Waksman-type algorithms, or a one-parameter family. Over $\mathbb{R}$, we prove that unbounded fan-in needs at least $6$ product gates, and approximate circuits exactly $5$. Below the threshold $K+2$, we prove that optimal circuits are rigid, for every fan-in. Every optimal circuit for polynomial multiplication is Toom-Cook at unisolvent points, up to constant scalings and shifts. Every optimal circuit for a tubal ring over $\mathbb{C}$ applies its transform. Every optimal circuit for complex multiplication over $\mathbb{R}$ is Gauss's algorithm at three real points, after a rotation. In at least two variables, every optimal division-free homogeneous component extractor is Ben-Or's construction with shifted points. Above the threshold, for $c\ge2$ complex products over $\mathbb{R}$, we prove that fan-in two needs exactly $3c$ product gates, unbounded fan-in at least $2c+2$, and approximate circuits exactly $2c+1$.

0.49

Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers

cs.CC ·2026-10-01 ·Isaac Rudich, Louis-Martin Rousseau
publishedtheory similarity 0.56
Abstract

Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3). The best known 3x3 recursive matrix multiplication algorithm uses 23 multiplications O(n^2.854). The best published lower bound of 21 (on algorithms with integer constants) leaves room for an algorithm with O(n^2.771) multiplications, and thus does not rule out the possibility of an algorithm that would beat Strassen's. We prove a lower bound of 22 multiplications for any 3x3 recursive algorithm with integer constants, proving that no such algorithm can do better than O(n^2.814) multiplications, and eliminating the possibility of a 3x3 algorithm that beats Strassen's 2x2 method. The proof builds on a recent decomposition method from Wang, who approached the problem by turning it into 496 subproblems. We provide exact solutions for 359 of them. The proof is in Lean; verification requires auditing only a few short files. The Lean formalization directly encodes statements about the limitations of recursive algorithms for matrix multiplication, as opposed to just a statement about the rank of the problem.

0.19

Eventual Nonnegativity of a Matrix Is in P

cs.LO ·2026-09-20 ·Julian D'Costa
theorycode/data similarity 0.56
Abstract · 19 pages, including appendix. v2: added a reference and minor edits to the exposition. A Lean 4 formalisation of the structural criterion an…

Given a rational matrix $A$, is every sufficiently large power $A^n$ entrywise nonnegative? We prove that this problem is decidable in deterministic polynomial time. This is in contrast with deciding eventual nonnegativity of a single prescribed entry sequence $(A^n)_{ij}$, which amounts to the Ultimate Positivity Problem for linear recurrence sequences, whose decidability is open. The previous decidability procedure (D'Costa, Ouaknine and Worrell, STACS 2024) splits the matrix powers into residue classes modulo a torsion exponent $D$ whose value can be exponential in the input size. We show that it is sufficient to check a single progression $A^{Dk+1}$: the exponents $n$ with $A^n \geq 0$ are closed under addition, and two consecutive exponents of the progression are coprime, so they generate every sufficiently large exponent. Along the progression, eigenvalues are grouped by their common $D$th power, and the required coefficients for each group are computed without forming $A^D$, any $λ^D$, or a splitting field: each summand is evaluated in its own root field $\mathbb{Q}(λ)$, and Galois equivariance keeps the degree and height of every class sum polynomially bounded, enabling certified zero and sign tests. The same algorithm with one case rejected decides eventual positivity, and a variant decides whether the matrix has any nonnegative power at all.

0.40