Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More

Understand

We study the decidability of three well-known problems related to integer matrix multiplication: Mortality (M), Zero in the Left-Upper Corner (Z), and Zero in the Right-Upper Corner (R).

• Let d and k be positive integers.
• Define M(k, d x d) as the following special case of the Mortality problem: given a set X of d -by-d integer matrices such that the cardinality of X is not greater than k, decide whether the d-by-d zero matrix belongs to X^+, where X^+ denotes the closure of X under the usual matrix multiplication.
• In the same way, define the Z(k, d x d) problem as: given an instance X of M(k, d x d) (the instances of Z(k, d x d) are the same as those of M(k, d x d)), decide whether at least one matrix in X^+ has a zero in the left-upper corner.