Uniformly at Random

Archive for July 2009

Matrix mortality

with 2 comments

The matrix mortality problem is the following:

Given n \times n matrices M_1, M_2, \ldots, M_k, is there some product M_{i_1}M_{i_1}\cdots M_{i_\ell} = 0?

Remarkably, this problem is undecidable for n=3.  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 A and B be finite alphabets and let A^* and B^* denote the sets of words over the alphabets A and B respectively.  The Post Correspondence Problem is the following:

Let g,h be maps from A \to B^*, which extend by concatenation to maps from A^* \to B^*.  Does there exist a word w such that g(w) = h(w)?

This problem is undecidable, even when the alphabet B 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 n=3:

Given n \times n matrices M_1, M_2, \ldots, M_k, is there some product M_{i_1}M_{i_1}\cdots M_{i_\ell} that has its upper left entry equal to 0?

Let A = \{1,2,3\} and let B = \{2,3\}.  Define a map \sigma: A^* \to Z^{3 \times 3} by \sigma(a_1a_2\cdots a_\ell) = \sum_{i=1}^\ell a_i 3^{\ell-i}, for all words w = a_1a_2\cdots a_\ell, where a_i \in A.  The map \sigma is injective and satisfies \sigma(uv) = 3^{|v|}\sigma(u) + \sigma(v) for all words u,v \in A^*, where |v| denotes the length of the word v.

Define the matrix T = \left( \begin{array}{ccc} 1&0&1\\ 1&1&0\\ 0&0&1 \end{array} \right).

Define the map \gamma: A^* \times A^* \to Z^{3\times 3} by \gamma(u,v) = T \left( \begin{array}{ccc} 3^{|u|}&0&0\\ 0&3^{|v|}&0\\ \sigma(u)&\sigma(v)&1 \end{array} \right) T^{-1}.

It is easy to show that \gamma is injective and is a homomorphism (i.e., \gamma(u'u'', v'v'') = \gamma(u',v')\gamma(u'',v'')).  Furthermore, the upper left entry of \gamma(u,v) is equal to 3^{|u|} + \sigma(u) - \sigma(v).

Consider now an instance g,h of the Post Correspondence Problem: i.e., g,h:A^* \to B^*.  Define matrices N_a = \gamma(h(a),g(a)) and N_a' = \gamma(h(a),1g(a)) for all a \in A.  Consider a product M = M_{a_1} M_{a_2} \cdots M_{a_\ell}, where w = a_1a_2\cdots a_\ell is a word with a_i \in A, and M_{a_i} is either N_{a_i} or N_{a_i}'.  The upper left corner of M equals 3^{|u|} + \sigma(u) - \sigma(v), where u = h(w) is a word over the alphabet B and v is some word over the alphabet A.  One then shows that this upper left corner is 0 if and only if 1u = v if and only if v = 1g(w) if and only if g(w) = h(w).

To show that the mortality problem is undecidable for n=3, let S = \left( \begin{array}{ccc} 1&0&0\\ 0&0&0\\ 0&0&0 \end{array} \right).  For any matrix M, the matrix SMS consists of all 0’s except for its upper left corner, which is equal to the upper left corner of M.  Thus if given matrices M_1, M_2, \ldots, M_k, some product M has upper left corner 0, then SMS = 0.  On the other hand, one can show that if some product is 0, say wlog of the form, S A_1 S A_2 \cdots S A_\ell S = 0, where A_i is a product of the M_j‘s, then some A_i has its upper left corner equal to 0.

The decidability of the mortality problem for 2 \times 2 matrices remains open.


Written by uncudh

July 9, 2009 at 3:41 pm