I am interested the following element of the group algebra $\mathbb{Q}S\_n$:
\begin{align}
\phi\_n=2e+(1\ 2)+(1\ 2\ 3)+\dotsb+(1\ldots n)
\end{align}
where $e$ is the identity permutation. My question is whether $\phi\_n$ is a unit.


For small $n$ I can see numerically that $\phi\_n$ is a unit, but I have no idea how to prove it for general $n$. As a linear map from $\mathbb{Q}S\_n$ to itself, for $n<10$, $\phi\_n$ seems to be diagonalisable with positive integer eigenvalues, and I have no idea why this should be.



Is this sum of cycles invertible in $\mathbb QS_n$?
$\newcommand{\cyc}{\operatorname{cyc}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\BB}{\mathbf{B}}
\newcommand{\AA}{\mathbf{A}}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\ww}{\mathbf{w}}
$


PART 1 OF 3
===========


[This is part of a long answer, which I had to split into 3 posts.


[Go to part 1](https://mathoverflow.net/a/308600). [Go to part 2](https://mathoverflow.net/a/308601). [Go to part 3](https://mathoverflow.net/a/308602).]


The answer that follows is an elaboration on parts of the following preprint:


* [Adriano Garsia, *On the Powers of Top to Random Shuffling*](http://gen.lib.rus.ec/book/index.php?md5=F2D15644E11EBB77C4E2DD6DC5744E3D).


In particular, the proofs I will give are taken from Section 3 of the preprint (but
I include more details). Unlike Garsia, I mean the exposition below to be
elementary, relying only on the content of a typical "abstract algebra 1"
class plus the definition of a group ring. (I even plan on reusing some of
this post in my next semester's combinatorics class.)


1. Notations
============


Let $\kk$ be any commutative ring.
For each integer $n$, we let $\left[ n\right]$
denote the set $\left\{ 1,2,\ldots,n\right\} $ (which is empty if $n\leq0$).


Fix a nonnegative integer $n$.
Let $S\_n$ be the $n$-th symmetric group; this is the
group of all $n!$ permutations of $\left[ n\right] $. We define
multiplication on $S\_n$ in the continental way (i.e., if $\alpha\in S\_n$
and $\beta\in S\_n$ are two permutations, then $\alpha\circ\beta$ is the
permutation that sends each $i\in\left[ n\right] $ to $\alpha\left(
\beta\left( i\right) \right) $). The identity permutation in $S\_n$ will
be called $\id $. (You are calling it $e$ instead.)


The *one-line notation* of a permutation $\sigma\in S\_n$ is defined to be
the $n$-tuple $\left( \sigma\left( 1\right) ,\sigma\left( 2\right)
,\ldots,\sigma\left( n\right) \right) $.


For any $k$ distinct elements $i\_1, i\_2, \ldots, i\_k$, we let
$\cyc\_{i\_1, i\_2, \ldots, i\_k}\in S\_n$ be the
permutation that sends $i\_1, i\_2, \ldots, i\_{k-1}, i\_k$ to
$i\_2, i\_3, \ldots, i\_k, i\_1$, while leaving all other elements of $\left[
n\right] $ unchanged.
(You are calling this permutation $\left( i\_1, i\_2, \ldots, i\_k \right)$.
But that notation would clash with my one-line notation.)


Consider the group ring $\kk S\_n$.
We define an element $\AA \in\kk S\_n$ by
\begin{equation}
\AA = \sum\_{i=1}^{n} \cyc\_{1,2,\ldots,i}.
\label{eq.defA} \tag{1.1}
\end{equation}


For each $k\in\left\{ 0,1,\ldots,n\right\} $, we let $B\_k$ be the set of
all permutations $\sigma\in S\_n$ satisfying $\sigma^{-1}\left( k+1\right)
<\sigma^{-1}\left( k+2\right) <\cdots<\sigma^{-1}\left( n\right) $. That
is, $B\_k$ is the set of all permutations $\sigma$ such that the numbers
$k+1,k+2,\ldots,n$ occur *in this order* in the one-line notation of $\sigma$.
For example, if $n=3$, then
\begin{align\*}
B\_0 & =\left\{ \left( 1,2,3\right) \right\} ,\\
B\_1 & =\left\{ \left( 1,2,3\right) ,\left( 2,1,3\right) ,\left(
2,3,1\right) \right\} ,\\
B\_2 & =\left\{ \left( 1,2,3\right) ,\left( 1,3,2\right) ,\left(
2,1,3\right) ,\left( 2,3,1\right) ,\left( 3,1,2\right) ,\left(
3,2,1\right) \right\} =S\_3,
\end{align\*}
where we represent each permutation $\sigma\in S\_3$ by its one-line
notation. Note that if $k\geq n-1$, then the chain of inequalities
$\sigma^{-1}\left( k+1\right) <\sigma^{-1}\left( k+2\right) <\cdots
<\sigma^{-1}\left( n\right) $ is vacuously true for every $\sigma\in S\_n$.
Thus,
\begin{equation}
\text{if }k\geq n-1\text{, then } B\_k = S\_n.
\label{eq.Bk=Sn} \tag{1.2}
\end{equation}


For each $k\in\left\{ 0,1,\ldots,n\right\} $, we define an element
$\BB\_k$ of $\kk S\_n$ by
\begin{equation}
\BB\_k = \sum\_{\sigma\in B\_k}\sigma.
\label{eq.defBk} \tag{1.3}
\end{equation}



> 
> **Theorem 1.** Let $n\geq1$. Then, $\BB\_1 = \AA$.
> 
> 
> **Theorem 2.** For each $a\in\left\{ 0,1,\ldots,n-1\right\} $, we have
>  \begin{equation}
> \BB\_a \AA = a \BB\_a + \BB\_{a+1}.
> \end{equation}
> 
> 
> **Theorem 3.** We have
>  \begin{equation}
> \prod\_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( \AA-i\right) = 0
> \label{eq.t3.claim} \tag{1.4}
> \end{equation}
>  in the ring $\kk S\_n$. (The factors in this product commute, since
>  they are all polynomials in $\AA$.)
> 
> 
> **Corollary 4.** The element $\id + \AA$ of $\kk S\_n$ is invertible
>  if the numbers $1,2,\ldots,n-1,n+1$ are invertible in $\kk$.
> 
> 
> **Corollary 5.** All the $n+1$ elements $\BB\_0,\BB\_1,\ldots,\BB\_n$ are
>  polynomials (with integer coefficients) in $\AA$.
> 
> 
> **Corollary 6.** For each $a\in\left\{ 0,1,\ldots,n-1\right\} $, we have
>  \begin{equation}
> \AA \BB\_a = a \BB\_a + \BB\_{a+1} .
> \end{equation}
> 
> 
> 


Corollary 4 is your first claim, because $\id + \AA$ is exactly
your $\phi\_{n}$ (for $\kk =\mathbb{Q}$). Moreover, Theorem 3 shows that
(again for $\kk = \mathbb{Q}$) the operator "left multiplication by
$\AA$" on $\kk S\_n$ is diagonalizable with eigenvalues being
contained in the set $\left\{ 0,1,\ldots,n-2,n \right\}$ (indeed, it can
also be shown that the spectrum is *precisely* this set; see Garsia's preprint
for that and for the dimensions of the eigenspaces); therefore, the operator
"left multiplication by $\id + \AA$" has positive integer
eigenvalues. So this proves your second claim too.


Corollary 6 and Theorem 3 are the equations (3.1) and (3.5) from Garsia's
preprint, except that he uses $\BB\_1$ instead of $\AA$ (but
this is equivalent due to Theorem 1).


The element $\BB\_1$ of $\kk S\_n$ is best known by its action
on representations of $S\_n$; namely, it acts as a so-called "top-to-random
shuffle" or "random-to-top shuffle" (I don't remember precisely which one it
is). It is also known as the "Tsetlin library" to probability theorists.
Further references on the elements $\BB\_0,\BB\_1,\ldots,\BB\_n$ of $\kk S\_n$
include:


* the appendix of [Nolan R. Wallach, *Lie Algebra Cohomology and Holomorphic
Continuation of Generalized Jacquet Integrals*, Advanced Studies in Pure Math.
14 (1988) Representations of Lie Groups, Hiroshima, 1986, pp.
123--151](https://projecteuclid.org/euclid.aspm/1527733096).
(At a quick glance, it proves the above Theorem 3 too.)
* [Persi Diaconis, James Allen Fill and Jim Pitman, *Analysis of Top to Random
Shuffles*, Combinatorics, Probability and Computing 1 (1992), pp.
135--155](https://statweb.stanford.edu/~cgates/PERSI/papers/randomshuff92.pdf).
* [Manfred Schocker, *Idempotents for derangement numbers*, Discrete
Mathematics, vol. 269 (2003), pp. 239--248](https://doi.org/10.1016/S0012-365X(02)00757-4). (His
$\Xi\_{n,k}$ is our $\BB\_k$.)
* [F. Hivert, J.-G. Luque, J.-C. Novelli, J.-Y. Thibon, *The (1-E)-transform in
combinatorial Hopf algebras*, arXiv:0912.0184v2, Journal of Algebraic
Combinatorics, March 2011, Volume 33, Issue 2, pp.
277--312](https://doi.org/10.1007/s10801-010-0245-5). (The formula (125) in
this paper corresponds to our Theorem 3, but the notations aren't for the
faint of heart.)
* [A. B. Dieker, Franco Saliola, *Spectral analysis of random-to-random Markov
chains*, arXiv:1509.08580v3, Advances in Mathematics 323 (2018), pp.
427--485](https://doi.org/10.1016/j.aim.2017.10.034). (This analyzes the much
more complicated "random-to-random shuffle", which corresponds to the element
$\omega\left( \AA \right) \cdot \AA$ of $\kk S\_n$, where
$\omega$ is the $\kk$-algebra anti-automorphism of $\kk S\_n$
that sends each $g \in S\_n$ to $g^{-1}$.)
* [Darij Grinberg, *The signed random-to-top operator on tensor
space*](http://www.cip.ifi.lmu.de/~grinberg/algebra/r2t.pdf).
(Couldn't help mentioning this -- it studies the kernel of the action of
$\AA$ on the $n$-th tensor power of a vector space.)


There is probably plenty of probabilistic literature that I just don't know about.


2. Proof of Theorem 1
=====================


We warm ourselves up with proving the easy Theorem 1. Combinatorially, it
simply says that the set $B\_1$ contains the $n$ permutations
$\cyc\_{1,2,\ldots,i}$ for $i \in \left[ n \right]$ and
no others (and that these $n$ permutations are distinct). If you find this
obvious, move on to the next section; I'll do nothing to convince you otherwise.


*Proof of Theorem 1.* Let $i\in\left[ n\right] $. Then, the permutation
$\cyc\_{1,2,\ldots,i}$ has one-line notation $\left(
2,3,\ldots,i,1,i+1,i+2,\ldots,n\right) $. Thus, the numbers $2,3,\ldots,n$
occur *in this order* in the one-line notation of $\cyc\_{1,2,\ldots,i}$;
in other words, we have
\begin{equation}
\left( \cyc\_{1,2,\ldots,i}\right) ^{-1}\left(
2\right) <\left( \cyc\_{1,2,\ldots,i}\right)
^{-1}\left( 3\right) <\cdots
<\left( \cyc\_{1,2,\ldots,i}\right) ^{-1}\left( n\right) .
\end{equation}
In other words, $\cyc\_{1,2,\ldots,i}\in B\_1$
(because we have defined $B\_1$ to be the set of all permutations $\sigma\in
S\_n$ satisfying $\sigma^{-1}\left( 2\right) <\sigma^{-1}\left( 3\right)
<\cdots<\sigma^{-1}\left( n\right) $).


Now, forget that we fixed $i\in\left[ n\right] $. We thus have shown that
$\cyc\_{1,2,\ldots,i}\in B\_1$ for each $i\in\left[
n\right] $. Hence, we can define a map
\begin{align\*}
\mathbf{f}:\left[ n\right] & \to B\_1,\\
i & \mapsto\cyc\_{1,2,\ldots,i}.
\end{align\*}
Consider this map $\mathbf{f}$. On the other hand, define a map
\begin{align\*}
\mathbf{g}:B\_1 & \to\left[ n\right] ,\\
\sigma & \mapsto\sigma^{-1}\left( 1\right) .
\end{align\*}


If $i\in\left[ n\right] $, then
\begin{align\*}
\left( \mathbf{g}\circ\mathbf{f}\right) \left( i\right) & =\mathbf{g}
\left( \underbrace{\mathbf{f}\left( i\right) }\_{=\cyc\_{1,2,\ldots,i}}
\right) =\mathbf{g}\left( \cyc\_{1,2,\ldots,i}\right) \\
& =\left( \cyc\_{1,2,\ldots,i}\right) ^{-1}\left(
1\right) \qquad\left( \text{by the definition of }\mathbf{g}\right) \\
& =i=\id \left( i\right) .
\end{align\*}
Thus, $\mathbf{g}\circ\mathbf{f}=\id $.


On the other hand, let $\sigma\in B\_1$ be arbitrary. We shall show that
$\left( \mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right)
=\id \left( \sigma\right) $.


In fact, $\sigma\in B\_1$ and therefore $\sigma^{-1}\left( 2\right)
<\sigma^{-1}\left( 3\right) <\cdots<\sigma^{-1}\left( n\right) $ (by the
definition of $B\_1$). Let $i=\mathbf{g}\left( \sigma\right) $. Thus,
$i=\mathbf{g}\left( \sigma\right) =\sigma^{-1}\left( 1\right) $ (by the
definition of $\mathbf{g}$). But $\sigma^{-1}$ is a permutation of $\left[
n\right] $; thus, the numbers $\sigma^{-1}\left( 2\right) ,\sigma
^{-1}\left( 3\right) ,\ldots,\sigma^{-1}\left( n\right) $ are precisely
the elements of $\left[ n\right] $ distinct from $\sigma^{-1}\left(
1\right) $. In view of $\sigma^{-1}\left( 1\right) =i$, this rewrites as
follows: The numbers $\sigma^{-1}\left( 2\right) ,\sigma^{-1}\left(
3\right) ,\ldots,\sigma^{-1}\left( n\right) $ are precisely the elements of
$\left[ n\right] $ distinct from $i$. In other words, these numbers
$\sigma^{-1}\left( 2\right) ,\sigma^{-1}\left( 3\right) ,\ldots
,\sigma^{-1}\left( n\right) $ are precisely the numbers $1,2,\ldots
,i-1,i+1,i+2,\ldots,n$ in some order. Moreover, we know what this order is: it
is the increasing order (since $\sigma^{-1}\left( 2\right) <\sigma
^{-1}\left( 3\right) <\cdots<\sigma^{-1}\left( n\right) $). Thus, the
numbers $\sigma^{-1}\left( 2\right) ,\sigma^{-1}\left( 3\right)
,\ldots,\sigma^{-1}\left( n\right) $ are precisely the numbers
$1,2,\ldots,i-1,i+1,i+2,\ldots,n$ in this order. Combining this with
$\sigma^{-1}\left( 1\right) =i$, we conclude that
\begin{equation}
\left( \sigma^{-1}\left( 1\right) ,\sigma^{-1}\left( 2\right)
,\ldots,\sigma^{-1}\left( n\right) \right) =\left( i,1,2,\ldots
,i-1,i+1,i+2,\ldots,n\right) .
\end{equation}
Hence, $\sigma^{-1}=\cyc\_{i,i-1,\ldots,1}$. Therefore,
$\sigma=\left( \cyc\_{i,i-1,\ldots,1}\right)
^{-1}=\cyc\_{1,2,\ldots,i}$. Comparing this with
\begin{equation}
\left( \mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right)
=\mathbf{f}\left( \underbrace{\mathbf{g}\left( \sigma\right) }\_{=i}\right)
=\mathbf{f}\left( i\right) =\cyc\_{1,2,\ldots
,i}\qquad\left( \text{by the definition of }\mathbf{f}\right) ,
\end{equation}
we obtain $\left( \mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right)
=\sigma=\id \left( \sigma\right) $.


Now, forget that we fixed $\sigma$. We thus have shown that $\left(
\mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right) =\id 
\left( \sigma\right) $ for each $\sigma\in B\_1$. In other words,
$\mathbf{f}\circ\mathbf{g}=\id $. Combining this with
$\mathbf{g}\circ\mathbf{f}=\id $, we conclude that the maps
$\mathbf{f}$ and $\mathbf{g}$ are mutually inverse. Hence, the map
$\mathbf{f}:\left[ n\right] \to B\_1$ is a bijection. Now,
\begin{equation}
\AA=\underbrace{\sum\_{i=1}^{n}}\_{=\sum\_{i\in\left[ n\right] }
}\underbrace{\cyc\_{1,2,\ldots,i}}
\_{\substack{=\mathbf{f}\left( i\right) \\\text{(by the definition of
}\mathbf{f}\text{)}}}=\sum\_{i\in\left[ n\right] }\mathbf{f}\left( i\right)
=\sum\_{\sigma\in B\_1}\sigma
\end{equation}
(here, we have substituted $\sigma$ for $\mathbf{f}\left( i\right) $ in the
sum, since the map $\mathbf{f}:\left[ n\right] \to B\_1$ is a
bijection). Comparing this with
\begin{equation}
\BB\_1 = \sum\_{\sigma\in B\_1}\sigma\qquad\left( \text{by the
definition of }\BB\_1 \right) ,
\end{equation}
we obtain $\BB\_1 = \AA$. This proves Theorem 1. $\blacksquare$


