The long run behaviour of linear dynamical systems is often studied by looking at eventual properties of matrices and recurrences that underlie the system. A basic problem that lies at the core of many questions in this setting is the following: given a set of pairs of rational weights and matrices {(w1, A1), . . . , (wm, Am)}, we ask if the weighted sum of powers of these matrices is eventually non-negative (resp. positive), i.e., does there exist an integer N s.t for all n greater than N , (w1.A1^n + w2.A2^n+ ... + w_m.Am^n) \geq 0 (resp. > 0). The restricted setting when m = w1 = 1, results in so-called eventually non-negative (or eventually positive) matrices, which enjoy nice spectral properties and have been well-studied in control theory. More applications arise in varied contexts, ranging from program verification to partially observable and multi-modal systems.

Our goal is to investigate this problem and its link to linear recurrence sequences. Our first result is that for m > 1, the problem is as hard as the ultimate positivity of linear recurrences, a long standing open question (known to be coNP-hard). Our second result is a reduction in the other direction showing that for any m \geq 1, the problem reduces to ultimate positivity of linear recurrences. This shows precise upper bounds for several subclasses of matrices by exploiting known results on linear recurrence sequences. Our third main result is an effective algorithm for the class of diagonalizable matrices, which goes beyond what is known on linear recurrence sequences.