Representation Theory: A Combinatorial Viewpoint

Supplementary Material

Chapter 1: Basic Concepts of Representation Theory

Chapter 2: Permutation Representations

Additional Exercises:

1. Show that the number of permutations in $S_n$ that have no fixed points (or one-cycles) is given by: $$ n!\sum_{k=0}^n \frac{(-1)^k}{k!}. $$ Hint: Use the Principle of Inclusion and Exclusion.
2. Find the probability that a permutation in $S_n$ has exactly $k$ fixed points for each $1\leq k \leq n$.
3. (Fischer-Yates or Knuth shuffle) Consider the following randomized algorithm:
   1. Start with the word $w = 12\dotsb n$ and $i=1$
   2. choose $j$ from the set $\{i, i+1,\dotsc, n\}$ uniformly at random.
   3. if $j = i$, do nothing; otherwise interchange the $i$th and $j$th letters of $w$.
   4. incrementing $i$ by one each time, repeat the steps 2 and 3 above until $i=n-1$ and then stop.
   Show that any given permutation of $n$ occurs as the result of the above random algorithm with probability $1/n!$.
4. (Sattolo algorithm) Suppose that the algorithm of the previous problem is performed except that in Step 2, $j$ is chosen uniformly at random from the set $\{i+1,i+2,\dotsc,n\}$. Then clearly, the process never results in the identity permutation (because $1$ gets moved at the very first step. What permutations can be obtained by this process, and with what probabilities?
5. The rank of a permutation $w\in S_n$ is defined its position in the list of all permutations in $S_n$ when they are written in lexicographic order. What is the rank of the permutation 64312875? Mouseover for answer
   27605.

Chapter 3: The RSK correspondence

Additional Exercises:

1. Let $e_1,e_2,e_3$ denote the three coordinate vectors in $\RR^3$. Let $S = \{\pm e_1, \pm e_2, \pm e_3\}$. Let $H$ be the convex hull of $S$ ($H$ is a Platonic solid; the regular octahedron). Show that symmetric group $S_4$ is isomorphic to the group of linear maps with determinant $+1$ which map $H$ onto itself. Let $V$ denote the set of functions from the set of vertices of $H$ to $\CC$, whose values on the set of vertices in any face of $H$ is $0$: $$ V = \{f:S\to \CC \mid \sum_{s\in F} f(s) = 0 \text{ for every $F\subset S$ which is a face of $H$}\}. $$ Show that $V$ is the representation $V_{(2,2)}$ of $S_4$.
2. Let $A$ be an integer matrix, and let $(P, Q)$ be the pair of SSYT associated to $A$. If $A$ is symmetric, then $P=Q$. In this case show that $\mathrm{trace}(A)$ equals the number of columns in $P$ of odd length.
   Hint: Note that the number of odd columns in $P$ equals the number of entries in its first row minus the number of even columns in the shape that remains when the first row is removed from $P$. Now formulate a conservation law in terms of $\mathrm{trace(A)}$, $\mathrm{trace}(S(A))$ and the number of entries output to the first row of $P$. This result is due to Marcel Schützenberger, see La correspondence de Robinson, published in Combinatoire et Répresentation du Groupe Symmétrique (ed. by D. Foata), Lecture NOtes in Mathematics 579, Springer, 1977.

Chapter 5: Symmetric Functions

Additional Exercises:

1. For every partition $\lambda$ of $n > 2$, show that $$ \chi_\lambda(w_{(2, 1^{n-2})}) = \sum_{\mu\in \lambda^-} \chi_\mu(w_{(2, 1^{n-3})}). $$
2. For every partition $\lambda$ of $n > 2$, show that the value of $\chi_\lambda$ at $(w_{(2,1^{n-2})})$ is the number of SYT of shape $\lambda$ where $2$ appears in the first row, less the number of SYT of shape $\lambda$ where $2$ appears in the second row.