WHEN IS A PAIR OF MATRICES MORTAL

Authors
BLONDEL VD TSITSIKLIS JN
Citation
Vd. Blondel et Jn. Tsitsiklis, WHEN IS A PAIR OF MATRICES MORTAL, Information processing letters, 63(5), 1997, pp. 283-286
Citations number
11
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
63
Issue
5
Year of publication
1997
Pages
283 - 286
Database
ISI
SICI code
0020-0190(1997)63:5<283:WIAPOM>2.0.ZU;2-V
Abstract
A set of matrices over the integers is said to be k-mortal (with k pos itive integer) if the zero matrix can be expressed as a product of len gth 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 x 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. (C) 1997 Elsevier Science B.V.