Putnam 2012: A5

jakncoke

Active member
Let $\mathbb{F}_p$ denote the integers mod p and let n be a positive integer.
Let v be a fixed vector $\in \mathbb{F}_p^{n}$, Let M be a nxn matrix with entries from $\mathbb{F}_p$. Define G:$\mathbb{F}_p^{n} \to \mathbb{F}_p^{n}$ by
G(x) = v + Mx. Define the k-fold composition of G by itself by $G^{1}(x) = G(x)$
and $G^{k+1} = G (G^{k}(x))$ Determine all pairs p,n for which there exists a vector v and a matrix M such that the $p^n$ vectors of $G^{k}(0), k=1,...,p^{n}$ are distinct.

jakncoke

Active member
I've solved it but it will take a bit to type the justification for some of the points but contained in the spoiler are general tips for how to think about the problem
This is a pretty interesting question.
Basically it is asking, for which matrix group $GL_{n+1}(F_p)$, can you generate all the elements in $(F_p)^n$ by iterating a matrix (raising it to the power), and get all the elements in $(F_p)^n$.

Basically for which $GL_{n+1}(F_p)$ does there exist an element of order $p^{n}$.

jakncoke

Active member
Still writing it, hit sumbit by mistake, bear with me.