## Archive for **July 2009**

## Matrix mortality

The matrix mortality problem is the following:

Given matrices , is there some product ?

Remarkably, this problem is undecidable for . Paterson first proved this in 1970; we follow the treatment of Halava and Harju in the *Amer. Math. Monthly*, Aug.-Sep. 2001. The proof is by a reduction from the Post Correspondence Problem, which is well-known to be undecidable. Let and be finite alphabets and let and denote the sets of words over the alphabets and respectively. The Post Correspondence Problem is the following:

Let be maps from , which extend by concatenation to maps from . Does there exist a word such that ?

This problem is undecidable, even when the alphabet consists of only two symbols. Before proving the undecidability of the mortality problem, we first sketch a proof that the following problem is undecidable for :

Given matrices , is there some product that has its upper left entry equal to 0?

Let and let . Define a map by , for all words , where . The map is injective and satisfies for all words , where denotes the length of the word .

Define the matrix .

Define the map by .

It is easy to show that is injective and is a homomorphism (i.e., ). Furthermore, the upper left entry of is equal to .

Consider now an instance of the Post Correspondence Problem: i.e., . Define matrices and for all . Consider a product , where is a word with , and is either or . The upper left corner of M equals , where is a word over the alphabet and is some word over the alphabet . One then shows that this upper left corner is 0 if and only if if and only if if and only if .

To show that the mortality problem is undecidable for , let . For any matrix , the matrix consists of all 0’s except for its upper left corner, which is equal to the upper left corner of . Thus if given matrices , some product has upper left corner 0, then . On the other hand, one can show that if some product is 0, say wlog of the form, , where is a product of the ‘s, then some has its upper left corner equal to 0.

The decidability of the mortality problem for matrices remains open.