mortality problem
The problem is undecidable for 3x3 matrices with integer entries:
https://en.wikipedia.org/wiki/List_of_undecidable_problems#Problems_about_matrices
Therefore, there is no (computable) bound on the size of the optimal solution. (otherwise one could decide the problem by first computing the bound, then testing all possible answers of this size)
More details and I guess an answer to your third point here:
http://arxiv.org/abs/1404.0644