Decomposition theorem for invertible substitutions on three-letter alphabet

Tan, B.; Wen, Z. -X.; Zhang, Y. -P.

Decomposition theorem for invertible substitutions on three-letter alphabet

Authors

Tan, B.

Wen, Z. -X.

Zhang, Y. -P.

Description

We shall characterize the structure of invertible substitutions on three-letter alphabet. We show that any invertible substitution, after some cyclic operation, can be written as a finite product of permutations and Fibonacci's substitution. As a consequence, a matrix (of order 3 and with non-negative integral coefficients) is the matrix of an invertible substitution if and only if it is a finite product of non-negative elementary matrices.
18 pages,pdf