# 'cyclically shifted subspace' of prime dimensional vector space

I've encountered this situation.

Let $p$ be a prime number, $V$ a $\mathbb{Q}$-linear space of dimension $p$ and some basis $v_0,\dots, v_{p-1}$, now let $u_0$ be a vector $$u_0 = v_{i_1} + \cdots + v_{i_k},$$ where the indexes are different and some are missing (i.e. $k<p$). Now we are going to 'cyclically shift' the $u_0$ vector as follows $$u_{n}=v_{i_1+n} + \cdots + v_{i_k+n},$$ where $n=0,\dots,p-1$ and the indices are to be computed modulo $p$.

Question: Do $u_0,\dots,u_{p-1}$ form a basis of $V$?

I think they do. But it is immediately obvious, it doesn't hold for non-prime dimensions or for permutations that aren't full cycles.

I've seen it proven in a special case by methods of group representation flavour. The case was when the space is the group algebra $\mathbb{Q}[\mathbb{Z}/p\mathbb{Z}]=A$ and the original basis consists of the elements of the group (that's ok since they are included in A) and the shifting is done by adding $1$. Then, shortly, there's established an isomorphism between $A$ and $\mathbb{Q}\times\mathbb{Q}[\zeta_p]$, where $\zeta_p$ is a primitive $p$-th root of the unity. The images of $u$'s form a basis. I'm not sure if this proof is adaptable to the general situation.

But don't mind that, I'm actually looking for more elementary approach, using only linear algebra language. I'm giving a lecture on something, and this is just a small part in one elegant proof. But I don't want to introduce the $\mathbb{Q}[\zeta_p]$ ring, it looks unnatural and tricky and I think my audience will be put off track If I start using new language in a lecture that has nothing to do with algebra. A small detour using only linear algebra should be easier to digest.

I've just came across a notion of cyclic subspace and cyclic vector. So in a more compact language we want to decide if $u_0$ is a $T$-cyclic vector, where $T$ is the linear transformation given by the cyclic permutation of basis.

• Shouldn't you be able to show (with some clever elimination argument) that you can add and subtract these from each other to get the original basis vectors? Sounds like a proof by induction on $k$. – Eric Auld Nov 23 '16 at 15:19
• Well, I'm not. Hence the post. But I agree it looks like an exercise from first chapter of any lingebra textbook. (However I doubt that some elimination argument will be prone to induction on k.) – liczman Nov 23 '16 at 16:30
• Well, you can translate the representation theory proof into pure linear algebra. Just let $T:V\to V$ be the shift map, and let $W$ be the span of the $u_n$. Then $T$ restricts to a map $T:W\to W$. Since $T^p=I$, the minimal polynomial of $T|_W$ must be a factor of $x^p-1$. Now using the irreducibility of $(x^p-1)/(x-1)$ and the fact that some but not all vectors in $W$ are fixed by $T$, you can show that minimal polynomial must be $x^p-1$ itself. But the dimension of $W$ is greater than or equal to the degree of the minimal polynomial by Cayley-Hamilton. – Eric Wofsey Nov 24 '16 at 9:59
• @EricWofsey thanks, Eric! That worked. Can you post if as an answer so I can accept it? If you are in the mood, you can add how is this actually a translation of the representation theory proof :) Thanks again! – liczman Nov 27 '16 at 11:49

The representation theory argument can be stated using just linear algebra. You're saying that the span of the $u_n$ is an ideal in the ring $A=\mathbb{Q}[\mathbb{Z}/p\mathbb{Z}]=\mathbb{Q}[x]/(x^p-1)\cong\mathbb{Q}\times\mathbb{Q}[\zeta_p]$, and then showing the only ideal it could be is $A$ itself. But you can also say this just in terms of polynomials: to say that the ideal is all of $A$ is just to say that no proper factor of $x^p-1$ annihilates the ideal. And this is just a statement about the behavior of the linear map $x$ on $A$.
Here's the details. Let $T:V\to V$ be the linear map given by $T(v_n)=v_{n+1}$ and let $U$ be the span of the $u_n$. Since $T(u_n)=u_{n+1}$, $T$ maps $U$ to itself; let $S:U\to U$ be the restriction of $T$ to $U$.
Let's now determine the minimal polynomial of $S$. We know that $T^p=I$, so $S^p=I$ and the minimal polynomial is a factor of $x^p-1$. The irreducible factors of $x^p-1$ over $\mathbb{Q}$ are $x-1$ and $\sum_{n=0}^{p-1}x^n$ (here is where we use that $p$ is prime). Since $S(u_0)=u_1\neq u_0$, $S-I\neq 0$ (here is where we use that $k<p$). Also, $$\sum_{n=0}^{p-1} S^nu_0=\sum_{n=0}^{p-1}u_n=k\sum_{n=0}^{p-1}v_n\neq 0$$ (since each $v_n$ appears a total of $k$ times among the different $u_n$), so $\sum_{n=0}^{p-1}S^n\neq 0$. So the minimal polynomial does not divide $x-1$ or $\sum_{n=0}^{p-1}x^n$, and the only possibility for the minimal polynomial is $x^p-1$.
Since the minimal polynomial of $S$ divides the characteristic polynomial of $S$, the characteristic polynomial has degree at least $p$. But the degree of the characteristic polynomial is $\dim U$, so $\dim U\geq p$. This is only possible if $\dim U=p$ and $U=V$. Thus the $u_n$ span all of $V$, and are a basis since there are $p$ of them.