This is a generalization of Strang's Linear Algebra (5th ed) Chap 3.4, problem 42 . Let $\mathbf{x}=\langle x_1, x_2, …, x_n\rangle$ and let $S%$ be the set of all the vectors that are the permutation of its components ($\langle x_2, x_1, …, x_n\rangle, \langle x_3, x_4, …, x_1\rangle,$ etc). Name the span of $S$ as $\mathbf{X}$. The question is, what are the possible dimensions of $\mathbf{X}$?
E.g. for $n=4$, $\dim(\mathbf{X})$ can only be $0, 1,3,4$. Proof: Let $\mathbf{x}$ be the $0$ vector, $\langle 1, 1,1,1\rangle$, $\langle 1, 1,-1,-1\rangle$ and $\langle 1, 0,0,0\rangle$, respectively. Aditionally, there's no $\mathbf{x}$ such that $\dim(\mathbf{X})=2$.
Best Answer
Assume the field is $\mathbb{C}$. Then the vector space $\mathbb{C}^n$ is a representation of the symmetric group $S_n$. It is well-known that this is a direct sum of the trivial representation spanned by $v=(1,\cdots,1)$ and the kernel of the linear map $L(x)=v\cdot x$, that is $\{(x_1,\cdots,x_n)\mid x_1+\cdots+x_n=0\}$. These two representations are both irreducible. Any subspace spanned by permutations of a particular vector $x$ will be the cyclic submodule generated by $x$ (recall $S_n$-representations are $\mathbb{C}[S_n]$-modules). Thus, by semisimplicity, the only possible dimensions will be $0,1,n-1,n$. (I thinks this works over arbitrary fields, or at least characteristic zero.)
Low-tech version. Let $V$ the space spanned by $v=(1,\cdots,1)$ and let $W$ be the aforementioned complementary subspace. Notice $W$ is spanned by $(1,-1,0,\cdots),\cdots,(0,\cdots,1,-1)$.
Let $x=(x_1,\cdots,x_n)$ be arbitrary. The dimension is $0,1,n-1,n$ based on:
If $x=0$ then the span is $0$.
If $x\ne 0$ and $x\in V$ then the span is $V$.
If $x\in W$ then permute it so two distinct components are next to each other. Sum over every permutation of the other $n-2$ components, call it $u$. Let $u'$ be $u$ with the chosen two components swapped. Then $u-u'$ is a scalar multiple of any one of $W$'s basis vectors. In this case the span will be precisely $W$.
Else, let $y$ be the sum of every permutation of $x$ (counted with multiplicity if necessary), which will be a scalar multiple of $v$, and then the difference $x-y/n!$ will be in $W$. In this case both $V$ and $W$ are spanned, so the span is all of $\mathbb{C}^n$.