Putnam 2012, Problem A-5

Let $\mathbb{F}_p$ denote the field of integers modulo a prime $p$, and let $n$ be a positive integer. Let $v$ be a fixed vector in $\mathbb{F}_p^n$, let $M$ be an $n \times n$ matrix with entries of $\mathbb{F}_p$, and define $G : \mathbb{F}_p^n \to \mathbb{F}_p^n$ by $G(x) = v + Mx$. Let $G^{(k)}$ denote the $k$-fold composition of $G$ with itself, that is, $G^{(1)}(x) = G(x)$ and $G^{(k+1)}(x) = G(G^{(k)}(x))$. Determine all pairs $p, n$ for which there exist $v$ and $M$ such that the $p^n$ vectors $G^{(k)}(0)$, $k = 1, 2, \ldots, p^n$ are distinct.

Solution:
The pairs $(p,n)$ with the specified property are those pairs with $n = 1$, together with the single pair $(2,2)$. We first check that these do work. For $n = 1$, it is clear that taking $v = (1)$ and $M = (0)$ has the desired effect.

For $(p,n) = (2,2)$, we take $v = \begin{pmatrix} 0 & 1 \end{pmatrix}$ and $M = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and then observe that
$$G^{(k)}(0) = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \end{pmatrix}, k = 0,1,2,3.$$

We next check that no other pairs work, keeping in mind that the desired condition means that $G$ acts on $\mathbb{F}_p^n$ as a cyclic permutation. Assume by way of contradiction that $(p,n)$ has the desired property but does not appear in our list. In particular, we have $n \geq 2$.

Let $I$ be the $n \times n$ identity matrix over $\mathbb{F}_p$. Decompose $\mathbb{F}_p^n$ as a direct sum of two subspaces $V, W$ such that $M - I$ is nilpotent on $V$ and invertible on $W$. Suppose that $W \neq 0$. Split $v$ as $v_1 + v_2$ with $v_1 \in V, v_2 \in W$. Since $M - I$ is invertible on $W$, there exists a unique $w \in W$ such that $(M - I)w = -v_2$. Then $G^{(k)}(w) - w \in V$ for all nonnegative integers $k$. Let $k$ be the least positive integer such that $G^{(k)}(w) = w$; then $k$ is at most the cardinality of $V$, which is strictly less than $p^n$ because $W \neq 0$. This gives a contradiction and thus forces $W = 0$.

In other words, the matrix $N = M - I$ is nilpotent; consequently, $N^n = 0$. For any positive integer $k$, we have
$$G^{(k)}(0) = v + Mv + \cdots + M^{k-1}v$$
$$= \sum_{j=0}^{k-1} \sum_{i=0}^{n-1} \binom{j}{i} N^i v$$
$$= \sum_{i=0}^{n-1} \binom{k}{i+1} N^i v.$$

If $n \geq 2$ and $(p,n) \neq (2,2)$, then $p^{n-1} > n$ and so $G^k(0) = 0$ for $k = p^{n-1}$ (because all of the binomial coefficients are divisible by $p$). This contradiction completes the proof.