# Uniformly at Random

## 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.

Advertisements

Written by uncudh

July 9, 2009 at 3:41 pm

Posted in math