Consider the set of -by- matrices whose entries are integers modulo , for some prime . The matrices in this set with nonzero determinant are invertible, and thus form a group under matrix multiplication; this group is given the name , where the "GL" stands for "general linear."
Given a matrix , its order is defined to be the smallest integer such that , where denotes the identity matrix. In this problem, you will compute the maximum possible order of a matrix in . That is, you will answer the question "What is the largest integer such that is the order of a matrix in "
Hint & Proof Sketch:
Let be a matrix in . Consider the vector space generated by the powers of , with coefficients in the field of elements. That is, is the vector space (under addition) of linear combinations where the coefficients are integers modulo . The Cayley-Hamilton theorem implies is finite dimensional; what is the largest possible value of its dimension as ranges over the group
Suppose . What does this imply about the order of in To answer this question, note that any power of must be in , since the exponents in powers of can be reduced using the polynomial relation produced by Cayley-Hamilton.
Let denote the largest possible value of when ranges over . Can you find a matrix whose order is at least What does this imply in light of the previous two steps?
As your answer to this problem, submit the maximum possible order of a matrix in , i.e.