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.