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.

  • $\begingroup$ 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$. $\endgroup$ – Eric Auld Nov 23 '16 at 15:19
  • $\begingroup$ 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.) $\endgroup$ – liczman Nov 23 '16 at 16:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Nov 24 '16 at 9:59
  • $\begingroup$ @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! $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.