Periodicity in rectangular arrays

We discuss several two-dimensional generalizations of the familiar Lyndon-Schützenberger periodicity theorem for words. We consider the notion of primitive array (as one that cannot be expressed as the repetition of smaller arrays). We count the number of m×n arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.