  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 {(w_1 ,
A_1 ), . . . , (w_m , A_m )}, we ask if the weighted sum of powers of these
matrices is eventually non-negative P (resp. n positive), i.e., does there
exist an integer N s.t for all n greater than N , (w_1 A_1^n + ... + w_m A_m^n)
is atmost 0 (resp. greater than 0). The restricted setting when m = w_1 = 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 at least 2, 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 at least 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 a novel reduction technique for a large
class of problems (including those mentioned above) over rational
diagonalizable matrices to the corresponding problem over simple real-algebraic
matrices. This yields effective decision procedures for diagonalizable
matrices.
