First, the order of the group is k, not k-1. Second, A
n+i is not a generator of the group (it's the neutral element), but A
n+i+1 is.
Third, the maximum possible value of k is unfortunately exponential in d.
As a simple example, consider a permutation matrix. Since any permutation matrix is regular, the order of the induced group is equal to the order of the permutation, and the maximum permutation order is determined by
Landau's function, which has subexponential behavior, but still grows faster than polynomially.
For a more complex example, suppose G is the finite field of order 2
d. As all finite fields have cyclic multiplicative groups, we can take a generator c of this group and consider the G-linear map h : G -> G that takes any element in G and multiplies it by c. This map is G-linear, and the smallest k such that h
k = id
G is exactly k=2
d-1 (the order of c in the multiplicative group).
Since F
2 is a subfield of G, we can interpret G as a d-dimensional vector space over F
2, which means that h is also F
2-linear. Choose any basis of G as a F
2-vector space, and let A be the transformation matrix of h with respect to this basis. Now A is a d×d matrix with values in F
2, and by construction A has the same order as h.
So this second example proves that k
max(d) is bounded from below by 2
d-1.