tilings, pseudo-self-similar tilings, and (pseudo) self-affine tilings. One di-
mensional examples include the Thue-Morse and Fibonacci tilings (see Fig-
ure 1.6), and the period-doubling tiling. Two dimensional examples include
the chair tiling, the “table” or “domino” tiling, the half-hex, the Penrose
tiling, and the pinwheel tiling. Most of the examples in this book will be
substitution tilings.
Our second class of tilings also goes by many names. Cut-and-project
tilings are closely related to model sets, to canonical projection tilings, and to
diffractive sets. Examples include the Fibonacci tiling in one dimension, the
Penrose and octagonal tilings in two dimensions, and the icosahedral tiling in
three dimensions. This class of tilings overlaps with the substitution tilings,
but neither is a subset of the other. There are plenty of substitution tilings
that are not cut-and-project, and plenty of cut-and-project tilings that do
not come from a substitution.
The third class of tilings are those defined by local matching rules. Imag-
ine being given a box of tiles and having to tile the plane in any manner
that fits. The tilings that result form a space that may or may not be the
hull of a single tiling.
Substitutions in one dimension. To understand substitution tilings,
we begin in one dimension. Pick a finite set (or “alphabet”) A, whose el-
ements are called “letters”. For instance, we might take A = {a, b}. A
sequence of letters is called a “word”. We associate a word to each letter.
(E.g., in the Thue-Morse tiling we associate a ab, b ba.) The substitu-
tion σ maps words to words, replacing each letter with its associated word.
For instance, the Thue-Morse substitution has σ(abbab) = abbabaabba.
Definition. The substitution matrix M keeps track of the populations
of different letters, with Mij equaling the number of times that the i-th letter
appears in σ(j-th letter).
For example, the Thue-Morse substitution has M = ( 1 1
1 1
). In general,
is the number of times that the i-th letter appears in
Definition. A (substitution) matrix M is primitive if there is a positive
integer n such that every entry of M
is positive. Equivalently, there is an
n such that
letter) contains every letter at least once. In such cases
we will say that σ is a primitive substitution.
Theorem 1.2 (Perron-Frobenius). Let M be a primitive matrix, and
let λP
be its largest positive real eigenvalue (sometimes called the Perron-
Frobenius eigenvalue). This eigenvalue has multiplicity one, and the corre-
sponding right- and left-eigenvectors have strictly positive entries. All other
eigenvalues have norm strictly less than λP
For Thue-Morse, λP
= 2, the left-eigenvector is L = (L1, L2) = (1, 1),
and the right-eigenvector is R =
Previous Page Next Page