×

When is a pair of matrices mortal? (English) Zbl 1337.68123

Summary: A set of matrices over the integers is said to be \(k\)-mortal (with \(k\) positive integer) if the zero matrix can be expressed as a product of length \(k\) of matrices in the set. The set is said to be mortal if it is \(k\)-mortal for some finite \(k\). We show that the problem of deciding whether a pair of \(48 \times 48\) integer matrices is mortal is undecidable, and that the problem of deciding, for a given \(k\), whether a pair of matrices is \(k\)-mortal is NP-complete.

MSC:

68Q25 Analysis of algorithms and problem complexity
15B36 Matrices of integers
03D15 Complexity of computation (including implicit computational complexity)
03D35 Undecidability and degrees of sets of sentences
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Branicky, Personal communication, May 1996.; M. Branicky, Personal communication, May 1996.
[2] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[3] Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman and Co: Freeman and Co New York) · Zbl 0411.68039
[4] Krom, M.; Krom, M., Recursive solvability of problems with matrices, Z. Math. Logik Grundlag. Math., 35, 437-442 (1989) · Zbl 0663.03033
[5] Matiyasevich, Y.; Sénizergues, G., Decision problem fors semi-Thue systems with a few rule (1996), Preprint
[6] Pansiot, J. J., A note on Post’s correspondence problem, Inform. Process. Lett., 12, 233 (1981) · Zbl 0485.03018
[7] Papadimitriou, C. H.; Tsitsiklis, J. N., The complexity of Markov decision processes, Math. Oper. Res., 12, 441-450 (1987) · Zbl 0638.90099
[8] Paterson, M. S., Unsolvability in 3 × 3 matrices, Stud. Appl. Math., 49, 105-107 (1970) · Zbl 0186.01103
[9] Toker, O., On the algorithmic unsolvability of some stability problems for discrete event systems, (Proc. IFAC World Congress (1996)), 353-358
[10] Tsitsiklis, J. N.; Blondel, V. D., Spectral quantities associated to pairs of matrices are hard — when not impossible — to compute and to approximate, (Tech. Rept. LIDS-P-2325 (1996), Laboratory for Information and Decision Systems, M.I.T: Laboratory for Information and Decision Systems, M.I.T Cambridge, MA) · Zbl 0985.93042
[11] also in: Math. Control SignalsSystems; also in: Math. Control SignalsSystems
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.