Jordan canonical form $\bmod p$ of a $p\times p$ cyclic permutation matrix

Question

Let $p$ be a prime number, Consider $V$ a vector space over $\mathbb{Z}/p$ with basis $e_0$, $e_1$, $\ldots$, $e_{p-1}$ and the permutation operator $T(e_i) = e_{i+1}$, $i$ modulo $p$. The characteristic polynomial of $T$ is $\lambda^p - 1 = (\lambda-1)^p$, and so $T$ has the eigenvalue $1$ with multiplicity $p$. The problem is to determine the Jordan canonical form of $T$. It probably is a single block $J_{p, 1}$. $\bf{Added:}$ Indeed, as @Jyrki Lahtonen: pointed out, since the eigenspace for $\lambda=1$ is $1$ dimensional, spanned by $e_0+ \cdots + e_{p-1}$, there is only one block.

How to get a basis in which $T$ has the Jordan form $J_{p,1}$?

For $p=2$ it's easy, $p=3$ is just a bit of calculations. Note that we need to use $p$ is prime. If it worked $\bmod n$ for arbitrary $n$, we would have $x^n-1 = (x-1)^n \bmod n$, not true in general.

Any feedback would be appreciated. Thank you for your attention!

$\bf{Added:}$ I thank all the people who provided input. Jyrki Lahtonen clarified the things a lot for me.

Any cyclic operator on an $n$-dimensional space over $k$ "is" multiplication by $T$ on the quotient $k$-algebra $k[T]/(T^n-1)$. If $n=p$, and $\operatorname{char} k = p$, then $T^n-1= T^p-1 = (T-1)^p$. So in characteristic $p$ we have this special decomposition of $T^p-1$. Now, notice that $(T-1)$ acts nilpotently, and a Jordan basis will be $$1 \mapsto (T-1)\mapsto (T-1)^2 \mapsto \cdots \mapsto (T-1)^{p-1} \mapsto 0$$ where by $(T-1)^k$ we understand its residue $\bmod (T-1)^p$.

Now, writing $e_i = T^i$, we see that $T e_i = e_{i+1}$, and the corresponding basis will be $$e_0 \mapsto (e_1-e_0) \mapsto (e_2 - 2 e_1 + e_0) \mapsto \cdots \mapsto (e_{p-1} - \binom{p-1}{1} e_{p-2} + \cdots )\mapsto 0$$ Note that $\binom{p-1}{k} \equiv (-1)^k \bmod p$ for $0\le k \le p-1$, so the last element in the basis is exactly $e_0 + e_1 + \cdots + e_{p-1}$ . This is also the solution obtained by Carl Schildkraut.

I was thinking at some point about the operator $T$ acting on functions on $k$ with values in $k$, acting by the circular shift by $1$. Then $T-I$ is just the discrete derivative ( forward or backward). If we prefer forward derivatives, then we can consider the functions $\phi_m\colon x \mapsto \binom{x}{m}$. We have $(T-I) \phi_m= \Delta \phi_m = \phi_{m-1}$. Note that we need $0 \le m \le m-1$, due to the denominator $m!$. It seems to be an equivalent solution, up to shift in direction, and some signs. While a clever trick, it seems now that considering operators acting as multiplications on quotient rings clarifies things a lot. For instance, if $T$ acted as multiplication on $k[T]/(f)$, one only needs to decompose $f$ into powers of irreducible ( over $k$ or some extension of it). Say we write $f= (T-\lambda_1)^{e_1} \cdots (T-\lambda_l)^{e_l}$. Then we have (Chinese remainder theorem) $$k[T]/(f) \simeq \prod k[t]/(T-\lambda_i)^{e_i}$$ as $k$ algebras, so also as $k$ vectors spaces with the action of $T$. On each component $T$ will act as a Jordan cell $J_{e_i, \lambda_i}$.

$\bf{Added:}$ was lead to this question after this question which says: the regular representation of $\mathbb{Z}/3$ on $k[\mathbb{Z}/3]$ is not completely reducible if $\operatorname{char} k = 3$. In fact, Maschke's Theorem says that the group algebra $k[G]$ is semisimple if and only if $\operatorname{char} k$ does not divide $|G|$.

Answer 1

Such a basis is a basis $[v_0,\dots,v_{p-1}]$ of $V$ for which $Tv_0=v_0$ and $(T-1)v_{i+1}=v_i$ for all $0\leq i<p-1$.

One such basis is defined by $v_i$ so that $(v_i)_j=(-1)^i\binom{j+i}i$. We see that $v_0$ is the all-ones vector, and for each $i\geq 0$ and $1\leq j\leq p$, \begin{align*} ((T-1)v_{i+1})_j &=(Tv_{i+1})_j-(v_{i+1})_j\\ &=(v_{i+1})_{j-1}-(v_{i+1})_j\\ &=(-1)^{i+1}\left(\binom{j+i}{i+1}-\binom{j+i+1}{i+1}\right)\\ &=(-1)^i\binom{j+i}i\\ &=(v_i)_j, \end{align*} so $(T-1)v_{i+1}=v_i$.

Answer 2

This is mostly a comment around the answers to the questions.

First, assume that $G$ is a set, and $k$ a field. Consider $k[G]$ the $k$ vector space with basis $(g)_{g\in G}$. The elements of $k[G]$ are finite formal sums $\sum_{g\in G} a_g g$, where only finitely many $a_g$ are non-zero. Now this construction is covariant in $G$: for a map from $G$ to $H$ we have a map from $k[G]$ to $k[H]$

The dual notion, which is $k^G$, consists of functions from $G$ to $k$. This is a contravariant notion in $G$: for a map $G\to H$ we have a map $k^H \to k^G$. While $k[G]$ consists superficially of functions from $G$ to $k$ with finite support, one should recall that $k[G]$ is in fact covariant in $G$.

Now, the dual of $k[G]$ is naturally $k^G$ ( not the other way around). Now, given a $k$-linear map $T\in End_k[k[G]]$, we get the dual map $T^{*}\in End_k[k^G]$ as follows: $\langle T^{*} \phi, v\rangle \colon = \langle \phi, T v\rangle$.

Assume now that $G$ is a group. Let $g \in G$. Consider the map $T\colon k[G]\to k[G]$ obtained as the linear extension of the map $L_g\colon G \to G$, $h \mapsto g h$. Therefore $$L_g \colon \sum a_h h \mapsto \sum_h a_h\, g h$$

Now, the duality $k^G \times k[G]\to k$ takes $(\phi, \sum a_h h)$ to $\sum \phi(h) a_h$. What is the adjoint map of $L_g$ ? We have $$\langle L_g^{*} (\phi), \sum a_h h\rangle = \langle \phi, \sum a_h g h\rangle$$ Now the RHS bracket equals $$\langle \phi, \sum a_{g^{-1} h} g\rangle = \sum_h \phi(h) a_{g^{-1}h}= \sum_{h} \phi(g h)a_h$$ Therefore $$L_g^{*}(\phi)(h) = \phi(gh)$$ Note: this could have been guessed from the covariance. The action of $G$ on $k^G$, $g\mapsto L_g^{*}$ is an action on the right. All is good...

Say $V$ is finite dimensional (over $k$), $T$ nilpotent operator on $V$, $v_0$, $v_1$, $\ldots$, $v_{n-1}$ a basis of $V$ such that $T v_i = v_{i+1}$, $T v_{n-1} = 0$. Let now $\phi_i$, $i=0, n-1$ the dual basis in $V^{*}$. Then for the dual operator on $V^{*}$ we have $T^{*} \phi_{i} = \phi_{i-1}$.

Let's consider now the case $G=\mathbb{Z}/p$. Then we can regard $k[T]/(T^p-1)$ in a natural way as $k[\mathbb{Z}/p]$, with $m \mapsto T^m$. The linear operator $L_{\bar 1}$ on $k[\mathbb{Z}/p]$ "is" the multiplication by $T$ in $k[T]/(T^p-1)$. Now, assume moreover that $\operatorname{char} k = p$. Then $T^p-1 = (T-1)^p$. The operator $T-1$ is nilpotent with the basis $v_i = (T-1)^i$ such that $(T-I) v_i = v_{i+1}$, $(T-I) v_{p-1} = 0$. In the standard basis $e_0$, $e_1$, $\ldots$, $e_{p-1}$ we have $$v_i = e_i - i e_{i-1} + \binom{i}{2} e_{i-2} + \cdots + (-1)^i e_0$$

Now, the dual operator $(T-I)^{*}$ acts on functions in $k^{\mathbb{Z}/p}$ as $$(T-I)^{*}\phi(x) = \phi(x+1)- \phi(x)= \Delta[\phi](x)$$ In other words, $(T-I)^{*}$ is the forward difference $\Delta= \Delta_1$. Now, if we find the dual basis to $v_i$, we get a Jordan basis for $(T-I)^*$.

We claim that the functions $$\phi_m(x)\colon = \frac{x(x-1) \cdots (x-m+1)}{m!}$$ for $0\le m \le p-1$ form the dual basis to $v_i$. First, let's check that $\Delta[\phi_m]= \phi_{m-1}$ for $m\ge 1$, and $\Delta[\phi_0] = 0$. Now, let's think what $v_i$ is: every element in $k[\mathbb{Z}/p]$ is a linear combination of deltas, that is, of evaluations. Now check that
$$\langle \phi, v_i\rangle = \Delta^i[\phi](0)$$

With this "new" Jordan basis ( for $k^{\mathbb{Z}/p}$) we can get another basis for $k[\mathbb{Z}/p]$. We only need to "identify" the two spaces ( with a shift in direction). The final result: we have the Jordan basis for $(T-I)$ $$w_m =\sum_{l=0}^{p-1} \binom{p-l}{m} e_{l}$$ with $(T-I) v_{m} = v_{m-1}$

$\bf{Added:}$ For illustration purposes, let's solve the following problem: bring the cyclic permutation matrix of size $2p$ to the Jordan canonial form over a field of characteristic $p$. The linear map acts on basis vectors $e_0$, $\ldots$, $e_{2p-1}$ by $T e_i = e_{i+1}$, $i$ modulo $2p$. So it is the transformation "multiplication by $T$" on the quotient $k$-algebra $k[T]/(T^{2p}-1)$. Note that $T^{2p}-1= (T-1)^p(T+1)^p$. Therefore, we have the multiplication by $T$ on $k[T]/((T-1)^p(T+1)^p)$. Consider the following basis of $k[T]/((T-1)^p(T+1)^p)$: $(T-1)^i (T+1)^p$, $(T-1)^p (T+1)^j$, for $0\le i,j \le p-1$. We have our Jordan basis here, and the transformation has two blocks $J_{p,1}$, and $J_{p,-1}$.

The general case should be clear now: $T$ acts by multiplication on $k[T]/(f(T))$. Decompose $f(T) = \prod_i (T-\lambda_i)^{e_i}$. Once we have the decomposition of $f(T)$ ( and that may vary with $k$), we know the Jordan structure of $T$. The Jordan basis is produced similarly.

It is interesting in char $p$ to get the dual basis. Will come back with more details at a later time.