10 1. BASIC NOTIONS

tilings, pseudo-self-similar tilings, and (pseudo) self-aﬃne 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,

(M

n)ij

is the number of times that the i-th letter appears in

σn(j-th

letter).

Definition. A (substitution) matrix M is primitive if there is a positive

integer n such that every entry of M

n

is positive. Equivalently, there is an

n such that

σn(any

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

F

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

F

.

For Thue-Morse, λP

F

= 2, the left-eigenvector is L = (L1, L2) = (1, 1),

and the right-eigenvector is R =

(

R1

R2

)

=

(

1

1

)

.