# Invertible linear automata

### Linear cellular automata

Linear cellular automata are those automata whose dependency on neighbouring cells is always via `XOR`, 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 matrix

Since 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, `V` is added. The resulting vector (considered modulo 2) is then interpreted as the new state.

### Results

If the matrix is non-singular - i.e. it has a non-zero 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 `|(Ix - A)|` - where `A` is the matrix of the transition function, `I` is the identity matrix of the same size, and `x` is a variable - whose coefficients correspond to the coefficients of the polynomial to be found [and `|M|` = "the determinant of matrix `M`"].

If this polynomial is primitive, then the whole FSM will exhibit behaviour with a period equal to `2^n - 1` - where `n` is the number of binary variables present.

### Notes

Very 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 maximal-period linear FSM with a single output has an exact equivalent in the form of some maximal-period LFSR.

Tim Tyler | tim@tt1.org | http://cell-auto.com/