The Cardinality of the Sets Involved in Lattice Games - Search Theory: A Game Theoretic Perspective - page 101

Fig. 7.1 Paths on the torus

To obtain the cardinality of these sets we will use the tridiagonal Toeplitz matrices.
Other games where these matrices appear can be seen in [2].

n , m and F n , m

7.2 The Cardinality of F

n

Let us consider the set F

m defined by ( 7.3 ). Let a pair r , s be given, 1

≤ r ≤ m , 1 ≤

,

m , and let us denote by a ( n )

n

s ≤

rsm the number of paths of

F

m satisfying A

( 1 )= r

,

and A ( n )= s ,since m is fixed, we omit it for simplification, so

= A s a ( n )

0
n

∈ F

m : A

( 1 )= r , A ( n )=

rs

,

and hence

F

m = r , s a ( n )

0
n

, r = 1 ,..., m , s = 1 ,..., m . (7.7)

rs

,

Let B denote the square matrix of order m