  This note considers linear recurrences (also called linear difference
equations) in unknowns indexed by the integers. We characterize a unique
\emph{reduced} linear recurrence with the same solutions as a given linear
recurrence, and construct a \emph{solution matrix} which parametrizes the space
of solutions. Several properties of solution matrices are shown, including a
combinatorial characterization of bases and dimension of the space of
solutions.
