Products of matrices and recursively enumerable sets

• We show how to represent recursively enumerable sets of matrices by products of matrices.
• We give a version of Rice's theorem for products of matrices.
• The proof is based on the Diophantine representation of recursively enumerable sets.

We study connections between products of matrices and recursively enumerable sets. We show that for any positive integers m and n   there exist three matrices M,N,BM,N,B and a positive integer q   such that if LL is any recursively enumerable set of m×nm×n matrices over nonnegative integers, then there is a matrix A   such that the matrices in LL are the nonnegative matrices in the set {AMm1NMm2N⋯NMmqB|m1,…,mq≥0}{AMm1NMm2N⋯NMmqB|m1,…,mq≥0}. We use this result to deduce an undecidability result for products of matrices which can be viewed as a variant of Rice's theorem stating that all nontrivial properties of recursively enumerable sets are undecidable.