Invertible linear automataLinear cellular automataLinear cellular automata are those automata whose dependency on neighbouring cells is always viaXOR , or XNOR . The state at
any subsequent time period may be expressed as some
linear function of the initial state.Linear cellular automata are a subset of linear finite state machines  for which there are a number of existing theoretical results of relevance to invertability.
Modelling the transition function with a matrixSince the contributions from dependent cells can be simply added together, the transition function of linear finite state machines may be expressed as a matrix,A and a fixed vector
V .
The current state is represented by a vector. To
perform the transition function, the current state is
multiplied by the matrix, and then the fixed vector,
ResultsIf the matrix is nonsingular  i.e. it has a nonzero determinant, then the corresponding FSM is invertible. This fact results in a relatively simple test for reversibility  and in a concrete method for constructing the inverse of the transition rule of a given FSM.
There is a "primitive polynomial" corresponding to the
transition function, whose coefficients may be found by
computing
If this polynomial is primitive, then the
whole FSM will exhibit behaviour with a period equal to
NotesVery frequently, the inverse of a linear cellular automaton is found to require a much larger neighbourhood than the original automaton.It has been proven that every maximalperiod linear FSM with a single output has an exact equivalent in the form of some maximalperiod LFSR.
