@ Appl. Gen. Topol. 20, no. 2 (2019), 407-418 doi:10.4995/agt.2019.11541 c© AGT, UPV, 2019 Matrix characterization of multidimensional subshifts of finite type Puneet Sharma and Dileep Kumar Department of Mathematics, Indian Institute of Technology Jodhpur, India (puneet.iitd@yahoo.com, pg201383502@iitj.ac.in) Communicated by F. Balibrea Abstract Let X ⊂ AZ d be a 2-dimensional subshift of finite type. We prove that any 2-dimensional subshift of finite type can be characterized by a square matrix of infinite dimension. We extend our result to a general d-dimensional case. We prove that the multidimensional shift space is non-empty if and only if the matrix obtained is of positive dimension. In the process, we give an alternative view of the necessary and sufficient conditions obtained for the non-emptiness of the multidimensional shift space. We also give sufficient conditions for the shift space X to exhibit periodic points. 2010 MSC: 37B10; 37B20; 37B50. Keywords: multidimensional shift spaces; shifts of finite type; periodicity in multidimensional shifts of finite type. 1. INTRODUCTION The study of dynamical systems originated to facilitate the study of natu- ral processes and phenomenon. Many natural phenomenon can be modeled as discrete dynamical systems and their long term behavior can be approximated using the modeled system. However, investigating a general discrete dynamical system is complex in nature and the long term behavior of the system cannot always be determined accurately. The uncertainty in predicting long term be- havior introduces dynamical complexity in the system which in turn results in Received 21 March 2019 – Accepted 07 May 2019 http://dx.doi.org/10.4995/agt.2019.11541 P. Sharma and D. Kumar erroneous behavior of the modeled system. Thus, there is a need to develop tools to facilitate the study of a general dynamical system which are not erro- neous and can model the physical system with the sufficient accuracy. Symbolic dynamics is one of such tools which are structurally simpler and can be used to model the physical system with desired accuracy. In one of the early stud- ies, Jacques Hadamard used symbolic dynamics to study the geodesic flows on surfaces of negative curvature [6]. Claude Shennon applied symbolic dynamics to the field of communication to develop the mathematical theory of commu- nication systems [14]. Since then the topic has found applications in areas like data storage, data transmission and planetary motion to name a few. The area has also found significant applications in various branches of science and engineering [9, 11]. Its simpler structure and easy computability can be used to investigate any general dynamical system. Infact, it is known that every discrete dynamical system can be embedded in a symbolic dynamical system with appropriate number of symbols [5]. Thus, to investigate a general discrete dynamical system, it is sufficient to study the shift spaces and its subsystems. Multidimensional shift spaces has been a topic of interest to many researchers. In one of the early works, Berger investigated multidimensional subshifts of fi- nite type over finite number of symbols. He proved that for a multidimensional subshift, it is algorithmically undecidable whether an allowed partial config- uration can be extended to a point in the multidimensional shift space [3]. Consequently, he observed that it is algorithmically undecidable to verify the non-emptiness of a multidimensional shift defined by a set of finite forbidden patterns. In [13], the author gives examples to show that a multidimensional shift space may or may not contain any periodic points. These results unraveled the uncertainty associated with a multidimensional shift space and attracted at- tention of several researchers around the globe. As a result, several researchers have explored the field and a lot of work has been done [1, 2, 4, 7, 8, 10, 12]. In [12], authors proved that multidimensional shifts of finite type with positive topological entropy cannot be minimal. In fact, if X is subshift of finite type with positive topological entropy, then X contains a subshift which is not of finite type, and hence contains infinitely many subshifts of finite type. In the same paper, the authors proved that every shift space X contains an entropy minimal subshift Y , i.e., a subshift Y of X such that h(Y ) = h(X). While [1] investigated mixing properties of multidimensional shift of finite type, [2] investigated minimal forbidden patterns for multidimensional shift spaces. In [4], authors exhibit mixing Zd shifts of finite type and sofic shifts with large entropy. However, they establish that such systems exhibit poorly separated subsystems. They give examples to show that while there exists Zd mixing systems such that no non-trivial full shift is a factor for such systems, they provide examples of sofic systems where the only minimal subsystem is a single point. In [8], for multidimensional shifts with d ≥ 2, authors proved that a real number h ≥ 0 is the entropy of a Zd shift of finite type if and only if it is the infimum of a recursive sequence of rational numbers. In [7], Hochman c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 408 Matrix characterization of multidimensional subshifts of finite type improved the result and showed that h ≥ 0 is the entropy of a Zd effective dy- namical system if and only if it is the lim inf of a recursive sequence of rational numbers. The problem of determining which class of shifts have a dense set of periodic points is still open. For two-dimensional shifts, Lightwood proved that strongly irreducible shifts of finite type have dense set of periodic points [10]. However, the problem is still open for shifts of dimension greater than two. Let A = {ai : i ∈ I} be a finite set and let d be a positive integer. Let the set A be equipped with the discrete metric and let AZ d , the collection of all functions c : Zd → A be equipped with the product topology. Any such func- tion c is called a configuration over A. Any configuration c is called periodic if there exists u ∈ Zd (u 6= 0) such that c(v + u) = c(v) ∀v ∈ Zd. The set Γc = {w ∈ Zd : c(v + w) = c(v) ∀v ∈ Zd} is called the lattice of periods for the configuration c. The function D : AZ d ×AZ d → R+ be defined as D(x,y) = 1 n+1 , where n is the least non-negative integer such that x 6= y in Rn = [−n,n]d, is a metric on AZ d and generates the product topology. For any a ∈ Zd, the map σa : A Zd → AZ d defined as (σa(x))(k) = x(k + a) is a d-dimensional shift and is a homeomorphism. For any a,b ∈ Zd, σa ◦ σb = σb ◦σa and hence Zd acts on AZ d through commuting homeomorphisms. A set X ⊆ AZ d is σa-invariant if σa(X) ⊆ X. Any set X ⊆ AZ d is shift-invariant if it is invariant under σa for all a ∈ Zd. A non-empty, closed shift invariant subset of AZ d is called a shift space. If Y ⊆ X is a closed, nonempty shift invariant subset of X, then Y is called a subshift of X. For any nonempty S ⊂ Zd, the projection map πS : A Zd → AS defined as πS = AZ d |S projects the elements of AZ d to AS. Any element in AS is called a pattern over S. A pattern is said to be finite if it is defined over a finite subset of Zd. A pattern q over S is said to be extension of the pattern p over T if T ⊂ S and q|T = p. The extension q is said to be proper extension if T ∩Bd(S) = φ, where Bd(S) denotes the boundary of S. Let F be a given set of finite patterns (possibly over different subsets of Zd) and let X = {x ∈ AZd : any pattern from F does not appear in x}. The set X defines a subshift of Zd generated by set of forbidden patterns F. If the set F is a finite set of finite patterns, we say that the shift space X is a shift of finite type. We say that a pattern is allowed if it is not an extension of any forbidden pattern. We denote the shift space generated by the set of forbidden patterns F by XF. Two forbidden sets F1 and F2 are said to be equivalent if they generate the same shift space, i.e. XF1 = XF2 . A forbidden set F of patterns is called minimal for the shift space X if F is the set with least cardinality such that X = XF. It is worth mentioning that a shift space X is of finite type if and only if its minimal forbidden set is a finite set of finite patterns. It may be noted that the shift space can equivalently be defined in terms of the allowed patterns. For a shift space X and any set S ⊂ Zd, let AS = {x ∈ AS : x = πS(y), for some y ∈ X}. Then, AS is the set of al- lowed patterns (for X) over S. The set A = ⋃ S⊂Zd AS is called the language c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 409 P. Sharma and D. Kumar for the shift space X. Given a set S ⊂ Zd and a set of patterns P in AS, the set X = X(S,P) = {x ∈ AZd : πS ◦σn(x) ∈P for every n ∈ Zd} is a subshift generated by the (allowed) patterns P. Refer [2, 12] for details. Let M be a square 0 − 1 matrix (possibly infinite) with indices {i : i ∈ I}. We say that the index i is u-related to j if Mji = 1. Let the collection of indices u-related to j be denoted by Ruj . We say that the indices j is d-related to i if Mji = 1. Let the collection of indices d-related to i be denoted by R d i . It may be noted that i is u-related to j if and only if j is d-related to i. The non-empty subset K of the index set I is said to be complementary if for each i ∈ K, there exists j,k ∈ K such that j is u-related to i and k is d-related to i. In this paper we investigate some of the questions raised in [3]. In the process we address the problem of non-emptiness and existence of periodic points for a multidimensional shift of finite type. We prove that the any 2-dimensional shift of finite type can be characterized by an infinite square matrix (possibly of infinite dimension). We prove that the elements of a shift of finite type can equivalently be characterized by limits of periodic configurations arising from allowed cubes for the shift space X. We investigate the non-emptiness problem using complementary set of indices. We extend our results to a general d-dimensional case. We also give sufficient condition ensuring existence of periodic points for a shift space X. 2. Main results Proposition 2.1. X is a d-dimensional shift of finite type =⇒ there exists a set C of d-dimensional cubes such that X = XC. Proof. Let X be a shift of finite type and let F be the minimal forbidden set of patterns for the shift space X. It may be noted that F contains finitely many patterns defined over finite subsets of Zd. For any pattern p in F, let lip be the length of the pattern p in the i-th direction. Let lp = max{liP : i = 1, 2, . . . ,d} denote the width of the pattern p and let l = max{lp : p ∈ F}. Let Cl be the collection of d-dimensional cubes of length l and let EF denote the set of extensions of patterns in F. Let C = Cl ∩EF. It may be observed that if p is a pattern with width l, forbidding a pattern p for X is equivalent to forbidding all extensions q of p in Cl. Thus, each pattern in the forbidden set of width l can be replaced by an equivalent forbidden set of cubes of length l and C is an equivalent forbidden set for the shift space X. Consequently, X = XC and the proof is complete. � Remark 2.2. The above result proves that every d-dimensional shift of finite type is generated by a set of cubes of fixed finite length. Such a consideration leads to an equivalent forbidden set which in general is not minimal. The above result constructs an equivalent forbidden set by considering all the cubes which are extension of the set of patterns in F. However, the cardinality of the new set can be reduced by considering only those cubes which are not c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 410 Matrix characterization of multidimensional subshifts of finite type proper extensions of patterns in F (but are of same size l). Such a construction reduces the cardinality of the forbidden set considerably and hence reduces the complexity of the system. It may be noted that the forbidden set obtained on reduction is still not minimal. However, the d-dimensional cubes generating the elements of X are of same size and can be used for generating the shift space X. We say that a shift of finite type X is generated by cubes of length l if there exists a set of cubes C of length l such that X = XC. Proposition 2.3. Every 2-dimensional shift of finite type X can be character- ized by an infinite square matrix. Proof. Let X be a 2-dimensional shift of finite type and let F be the equivalent set of forbidden cubes (of fixed length, say l) for the space X. Let A be the generating set of cubes (of length l) for the space X. It may be noted that as cubes of length l form a generating set for the shift space X, to verify whether any x ∈ AZ d belongs to X, it is sufficient to examine strips of height l in x. Let A2 = { ( S1 S2 ) : S1,S2 ∈A, ( S1 S2 ) is allowed in X}. By construction, A2 is a finite set of 2l×l allowed rectangles, say {a1,a2, . . . ,ak}, generating the shift space X. Define a k ×k matrix M as Mij = { 0, (aiaj) is forbidden in X; 1 (aiaj) is allowed in X; Then, the sequence space corresponding to the matrix M, ΣM = {(xn) : Mxixi+1 = 1, ∀i} generates all allowed infinite strips(of height 2l) in X. It may be noted that any element in ΣM is element of the form ( P Q ) , where P and Q are allowed infinite strips of height l. Generate an infinite matrix M, indexed by allowed infinite strips of height l, using the following algorithm: (1) Pick any ( P Q ) ∈ ΣM and index first two rows and columns of the matrix by P and Q. Set mQP = 1. (2) For each ( P Q ) ∈ ΣM , if the rows and columns indexed P and Q exist, set mQP = 1. Else, label next row and/or column as P and/or Q (whichever required) and set mQP = 1. (3) In the infinite matrix generated in step 2, set mQP = 0, if mQP has so far not been assigned a value. (4) In the infinite matrix obtained, if there exists an index P such that the P-th row or column is zero, delete the P-th row and column from the matrix generated. c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 411 P. Sharma and D. Kumar The above algorithm generates an infinite 0-1 matrix where mQP = 1 if and only if ( P Q ) is allowed in X, where P and Q are allowed infinite strips (of height l) in X. Let ΣM be the sequence space associated with the matrix M. Consequently, any sequence in ΣM gives a vertical arrangement of infinite allowed strips (of height l) such that the arrangement is allowed in X and hence generates an element in X. Conversely, any element in X is a sequential (vertical) arrangement of infinitestrips of height l and hence is generated by a sequence in ΣM. Consequently, X = ΣM and the proof is complete. � Remark 2.4. The above result characterizes elements of the shift space X by a infinite square matrix M. It may be noted that if row/column for an index A is zero, the algorithm deletes the row and column with index A. Such a criteria reduces the size of the matrix and will result in a matrix of dimension 0, if the shift space is empty. Further, the characterization of the space may yield a matrix of infinite (uncountable) dimension. Consequently, it is undecidable whether a shift of finite type generated by set of cubes A is non-empty. It may be noted that although the algorithm does not guarantee a positive dimensional matrix, if the shift space X is non-empty the matrix generated is definitely of positive dimension and characterizes the elements in X. Further, as each row/column of the matrix generated has atleast one non-zero entry, each block indexing the matrix can be extended to an element of X. Consequently, any submatrix of the matrix M cannot generate the shift space X. In light of the remark stated, we get the following result. Corollary 2.5. A 2-dimensional shift of finite type is non-empty if and only if the characterizing matrix M is of positive dimension. Further, any proper submatrix of the matrix M generates a proper subshift and hence the matrix M is minimal. Remark 2.6. It may be noted that although the above algorithm characterizes the elements of the shift space using (possibly) a matrix of infinite dimension, the same can be achieved by approximating each point of X by a sequence of periodic points (which may not lie in the shift space X). To illustrate, let A is the collection of generating cubes (of size l) of X and let Ar be the collection of all allowed cubes of rl×rl obtained by r×r arrangement of elements of A. Let Xr denote the all periodic configurations arising from the collection Ar. Then X = ∞⋂ k=1 Xk and hence any element of the shift space can be obtained by approximation through periodic points (which may not lie in X themselves). Hence we get the following result. Proposition 2.7. Any point in a 2-dimensional shift of finite type can be approximated by a sequence of periodic points. Proof. Let A denote the collection of generating cubes (of size l) of X and Ar be the collection of all allowed cubes of rl×rl obtained by r ×r arrangement of elements of A. Note that as all central blocks of an element in X are c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 412 Matrix characterization of multidimensional subshifts of finite type allowed, any element is a limit of periodic configurations (generated by its central blocks). Also, if x is a limit of periodic configurations arising from the collection Ar, then any central block of x is allowed and hence x is an element of the shift space X (proof follows from the fact that any element belongs to X if and only if all central blocks of x are allowed in X). Consequently X = ∞⋂ k=1 Xk and the proof is complete. � Remark 2.8. For a shift space X, with generating set of cubes of height l, let L denote set of all allowed infinite strips of height l. Recalling the notions of u-related indices for a square matrix M, for any two infinite strips P,Q of height l, we say that P is u-related (d-related) to Q if P and Q are indices of M such that MQP = 1 (MP Q = 1). Further, generalizing the definition, a family of allowed infinite strips of height l is complementary if for each P in L there exists infinite strips Q,R ∈L such that Q is u-related to P and R is d-related to P . Thus, the algorithm generates u-related (d-related) infinite strips for the shift space X which in turn generates an arbitrary element of X. As any element of the shift space is a sequential arrangement of u-related (d-related) infinite strips, the characterization of the elements of the space X by a matrix M is equivalent to finding all the u-related (d-related) pairs of infinite strips for the space X. As any infinite strip of height l (say P) can be extended to an element of X only if there exists infinite strips Q,R of height l such that Q is u-related to P and R is d-related to P , only members of complementary family can form the building blocks for an element of X. As a result, we get the following corollary. Corollary 2.9. Let X be a multidimensional shift space generated by cubes of length l and let B be the infinite strips of height l allowed in X. Then, the shift space X is non-empty if and only if there exists non-empty set of indices B0 ⊆ B such that B0 is complementary. Remark 2.10. The above result provides an alternate view of the criteria estab- lished for the non-emptiness of the space X. Although the matrix generated characterizes the elements of the shift space X, one does not require the matrix M for establishing the non-emptiness for the shift space. The set of indices of the matrix may be observed at each iteration and existence of a complementary subfamily can be used to establish the non-emptiness of the space X. However, as the algorithm does not provide any optimal technique for picking the block( P Q ) at each iteration, such a consideration does not reduce the time com- plexity of the problem. However, algorithms for optimal selection of the infinite blocks ( P Q ) may be proposed which in turn may reduce the time complexity of the algorithm. As an extension of the proposed algorithm characterizes the elements of a d-dimensional shift space, similar results are true for a general d-dimensional shift of finite type. For the sake of completion, we include the proof of the result below. c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 413 P. Sharma and D. Kumar Proposition 2.11. If X is a d-dimensional shift of finite type, then the ele- ments of X can be determined by an infinite square matrix. Proof. Let X be a d-dimensional shift of finite type and let F be the equivalent set of forbidden cubes (of fixed length, say l) for the space X. Let A be the generating set of cuboids of size 2l× 2l× . . . 2l︸ ︷︷ ︸ d−1times ×l for the space X. By construction, A is a finite set of allowed rectangles, say {a1,a2, . . . ,ak}. Define a k ×k matrix M0 as M0ij = { 0, (aiaj) is forbidden in X; 1 (aiaj) is allowed in X; where (aiaj) denotes adjacent placement of aj with ai in the positive d-th direction. Then, the sequence space corresponding to the matrix M0, ΣM0 = {(xn) : M0xixi+1 = 1, ∀i} generates all allowed one directional (in d-th direction) infinite strips in X. It may be noted that any element in ΣM0 is element of the form ( P Q ) 0 , where P and Q are allowed infinite strips (in direction d) of dimension 2l× 2l× . . . 2l︸ ︷︷ ︸ d−2times ×l ×∞ and ( P Q ) 0 denotes adjacent placement of Q with P in the negative d− 1-th direction. Generate an infinite matrix M1, indexed by allowed infinite strips of dimen- sion 2l× 2l× . . . 2l︸ ︷︷ ︸ d−2times ×l×∞ , using the following algorithm: (1) Pick any ( P Q ) 0 ∈ ΣM0 and index first two rows and columns of the matrix by P and Q. Set mQP = 1. (2) For each ( P Q ) 0 ∈ ΣM0 , if the rows and columns indexed P and Q exist, set mQP = 1. Else, label next row and/or column as P and/or Q (whichever required) and set mQP = 1. (3) In the infinite matrix generated in step 2, set mQP = 0, if mQP has so far not been assigned a value. (4) In the infinite matrix obtained, if there exists an index P such that the P-th row or column is zero, delete the P-th row and column from the matrix. The above algorithm generates an infinite 0-1 matrix where mQP = 1 if and only if ( P Q ) 0 is allowed in X, where P and Q are of dimension 2l× 2l× . . . 2l︸ ︷︷ ︸ d−2times ×l ×∞. Let ΣM1 denote the sequence space corresponding to c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 414 Matrix characterization of multidimensional subshifts of finite type the matrix generated above. It can be seen that the space ΣM1 precisely is the collection of allowed bi-infinite strips (in direction d and d − 1). Further, as any element in ΣM1 is of the form ( P Q ) 1 , where P and Q are allowed infinite strips (in direction d and d− 1) of dimension 2l× 2l× . . . 2l︸ ︷︷ ︸ d−3times ×l ×∞×∞ and ( P Q ) 1 denotes adjacent placement of Q with P in the negative d− 2-th di- rection, a repeated application of the algorithm generates a matrix M2 which extends the infinite patterns in ΣM1 along the direction d− 3 to generate the space ΣM2 . Consequently, repeated application of the above algorithm extends the allowed patterns infinitely in all the d directions (one direction at each step) to obtain a point in X. Further, as any point in X can be visualized as such an extension of allowed cubes in the d directions, the matrix obtained (at the final step) characterizes the elements of the space X. � Remark 2.12. The above result characterizes the multidimensional shift space by a infinite matrix M. The characterization is obtained by repeated applica- tion of the 2-dimensional case, extending the allowed blocks in each of the d directions. In the process, at each step we obtain an infinite matrix character- izing the extension of an allowed block in the i-th direction. Although the rows and columns of the characterizing matrix M are indexed by infinite blocks al- lowed in X, their existence is guaranteed as they are procured from the allowed blocks obtained in the previous step. It may be noted that extension in any of the directions (at i-th step) does not guarantee an extension to the element of X. In particular, a block extendable in a direction i (or in a few directions i1, i2, . . . , ir) need not necessarily extend to an element in X. In particular if the shift space is empty, positive dimension of matrix at i-th step does not guarantee a matrix of positive dimension at the final step. Consequently, once again, the shift space is non-empty if and only if the matrix generated (at the final step) is of positive dimension. Thus, we obtain the following corollary. Corollary 2.13. A multidimensional shift of finite type is non-empty if and only if the characterizing matrix M is of positive dimension. Further, any proper submatrix of M generates a proper subshift and hence the matrix M is minimal. Remark 2.14. It may be noted that the matrix characterizing the elements of the multidimensional shift space is once again (possibly) infinite. However, such a construction helps in better visualization of the problem and can help in better understanding of the subsystems of the shift space under considera- tion. It may be noted that the elements of the shift space can be obtained as sequential limits of the periodic points generated using allowed cubes of finite size (which may not lie in the shift space itself). Consequently, the points of the multidimensional shift space can be obtained by approximations through c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 415 P. Sharma and D. Kumar periodic points (which may not lie in the shift space X). Hence we get the following result. Proposition 2.15. Any point in a d-dimensional shift of finite type can be approximated by a sequence of periodic points. Proof. Let A denote the collection of generating cubes (of size l) of X and Ar be the collection of all allowed cubes of side rl. It may be noted that any element of Ar is an r ×r × . . .×r︸ ︷︷ ︸ d times arrangement of elements of A. Let Xr denote the collection of all periodic configurations (periodic of same period in all the d-directions) generated by elements of Ar. As all central blocks of an element in X are allowed, any element of X is a limit of periodic configurations (generated by its central blocks). Also, if x is a limit of periodic configurations arising from the collection Ar, then any central block of x is allowed and hence x is an element of the shift space X (proof follows from the fact that any element belongs to X if and only if all central blocks of x are allowed in X). Consequently X = ∞⋂ k=1 Xk and the proof is complete. � Remark 2.16. The above proof characterizes the points of the shift space as limits of periodic points generated by the allowed cubes for the shift space. Note that although the periodic points generated are periodic in all the d-directions (with the same period), the construction of periodic points can be further simplified by constructing them as adjacent tiling of a single element (of Ar) throughout the Zd domain. As the arguments given in the proof hold good in this setting too, elements of the shift space can be realized as limits of periodic points constructed in this manner (note that as periodicity in one direction need not imply periodicity in the other, periodic points in general have infinite orbits in the multidimensional shift space). Once again, the construction of elements of the shift space can be captured through the notion of complimentary sets. As any element of the shift space can be visualized as an alignment of elements of a complimentary set, the shift space is non-empty if and only if the exists a subset B0 of indices (of matrix obtained at the final step) which forms a complimentary set. The result is an analogous extension of the result obtained for the two dimensional case and hence characterize the elements of the shift space X. Hence we get the following corollary. Corollary 2.17. Let X be a multidimensional shift space and let B be the infinite strips of height l allowed in X. Then, the shift space X is non-empty if and only if there exists B0 ⊆ B such that B0 is complementary. We now discuss the periodicity for a given multidimensional shift space. Proposition 2.18. Let X be a multidimensional shift space and let B be the infinite strips of height l allowed in X. If there exists a finite complementary set B0 ⊂ B, then the set of periodic points is non-empty. c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 416 Matrix characterization of multidimensional subshifts of finite type Proof. Let B be the infinite strips of height l allowed in X and let B0 ⊂ B be a finite complementary set. By definition, elements of B0 form indices (not all) for the matrix M. Let Nbe the submatrix of M indexed by elements of B0. As the set B0 is complementary, the shift generated by B0 (say ΣB0 ) is non-empty. Further, as shift defined by a finite dimensional matrix contains periodic points, there exists periodic points for ΣB0 (and hence for the shift space X). � Remark 2.19. The above result establishes a sufficient condition for existence of periodic points in a multidimensional shift space. However, the condition derived is sufficient in nature and the shift space may exhibit periodic points without exhibiting the derived condition. Note that a point is periodicity of a point in a direction dk ensures (and is equivalent to) existence of a finite com- plementary set in the direction dk. Consequently, a point in the shift space is periodic in all the d directions if and only if there exists a finite complementary set for the shift space under consideration. Thus we get the following corollary. Corollary 2.20. A shift space X contains a point periodic in all the directions if and only if it there exists a finite set of finite patterns complementary for the shift space X. 3. Conclusion In this paper, we investigate the non-emptiness problem and existence of periodic points for a multidimensional shift space of finite type. In the process, we prove that any multidimensional shift of finite type can be characterized by an infinite square matrix (possibly of infinite dimension). We prove that the multidimensional shift space is non-empty if and only if the characterizing matrix is of positive dimension. We prove that the elements of the shifts space can equivalently be characterized as limits of the periodic points generated by the cubes allowed for the shift space X. We also investigate the existence of periodic points for a multidimensional shift space. We address the non- emptiness problem and existence of periodic points using complementary set of indices. We prove that a shift space exhibits a point periodic in all the directions if and only if there exists a finite set of finite cubes complimentary for the shift space X. Acknowledgements. The authors thank the referee for his/her useful sugges- tions and remarks. The first author thanks National Board for Higher Math- ematics (NBHM) Grant No. 2/48(39)/2016/NBHM(R.P)/R&D II/4519 for financial support. c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 417 P. Sharma and D. Kumar References [1] J. C. Ban, W. G. Hu, S. S. Lin and Y. H. Lin, Verification of mixing properties in two-dimensional shifts of finite type, arXiv:1112.2471v2. [2] M.-P. Beal, F. Fiorenzi and F. Mignosi, Minimal forbidden patterns of multi-dimensional shifts, Int. J. Algebra Comput. 15 (2005), 73–93. [3] R. Berger, The undecidability of the Domino Problem, Mem. Amer. Math. Soc. 66 (1966). [4] M. Boyle, R. Pavlov and M. Schraudner, Multidimensional sofic shifts without separation and their factors, Transactions of the American Mathematical Society 362, no. 9 (2010), 4617–4653. [5] X.-C. Fu, W. Lu, P. Ashwin and J. Duan, Symbolic representations of iterated maps, Topological Methods in Nonlinear Analysis 18 (2001), 119–147. [6] J. Hadamard, Les surfaces a coubures opposees et leurs lignes geodesiques, J. Math. Pures Appi. 5 IV (1898), 27–74. [7] M. Hochman, On dynamics and recursive properties of multidimensional symbolic dy- namics, Invent. Math. 176:131 (2009). [8] M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimen- sional shifts of finite type, Annals of Mathematics 171, no. 3 (2010), 2011–2038. [9] B. P. Kitchens, Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts, Universitext. Springer-Verlag, Berlin, 1998. [10] S. Lightwood, Morphisms from non-periodic Z2-subshifts I: Constructing embeddings from homomorphisms, Ergodic Theory Dynam. Systems 23, no. 2 (2003), 587–609. [11] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. [12] A. Quas and P. Trow, Subshifts of multidimensional shifts of finite type, Ergodic Theory and Dynamical Systems 20, no. 3 (2000), 859–874. [13] R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177–209. [14] C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 379–423, 623–656. [15] H. H. Wicke and J. M. Worrell, Jr., Open continuous mappings of spaces having bases of countable order, Duke Math. J. 34 (1967), 255–271. c© AGT, UPV, 2019 Appl. Gen. Topol. 20, no. 2 418