  Is there an algorithm to determine attributes such as positivity or
non-zeroness of linear recurrence sequences? This long-standing question is
known as Skolem's problem. In this paper, we study the complexity of an
equivalent problem, namely the (generalized) moment membership problem for
matrices. We show that this problem is decidable for orthogonal, unitary and
real eigenvalue matrices, and undecidable for matrices over certain commutative
and non-commutative polynomial rings. Our results imply that the positivity
problem for simple unitary linear recurrence sequences is decidable, and is
undecidable for linear recurrence sequences over the ring of commutative
polynomials. As a byproduct, we prove a free version of Polya's theorem.
