<!doctype html>
<html lang="en">
 <head>
 <meta charset="utf-8">
 <meta http-equiv="x-ua-compatible" content="ie=edge">
 <meta name="viewport" content="width=device-width, initial-scale=1">
 <title>Math190-Tufts University - Representations and the symmetric group</title>
	<script>
	 window.MathJax = {
	 options: {
	 ignoreHtmlClass: 'tex2jax_ignore',
	 processHtmlClass: 'tex2jax_process'
	 },
	 tex: {
	 autoload: {
		color: [],
		colorv2: ['color']
	 },
	 packages: {'[+]': ['noerrors']}
	 },
	 loader: {
	 load: ['input/asciimath', '[tex]/noerrors']
	 }
	 };
	</script>
	<script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js" id="MathJax-script"></script>
 <link rel="stylesheet" href="../css/default.css" />
	<link rel="stylesheet" href="../css/haddock.css" />
	
	<link href="https://fonts.googleapis.com/css?family=Lato:400,700" type="text/css" rel="stylesheet" media="screen" />
	<link href="https://fonts.googleapis.com/css?family=Arimo:400,700" type="text/css" rel="stylesheet" media="screen" />
	<link href="https://fonts.googleapis.com/css?family=Roboto:400,700" type="text/css" rel="stylesheet" media="screen" />
	<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700" type="text/css" rel="stylesheet" media="screen" />
	<link href="https://use.fontawesome.com/releases/v5.6.3/css/all.css" type="text/css" rel="stylesheet" media="screen" integrity="sha384-UHRtZLI+pbxtHCWp1t77Bi1L4ZtiqrqD80Kn4Z8NTSRyMA2Fd33n5dQ8lWUE00s/" crossorigin="anonymous" />			
 </head>
 <body>
 <header>
 <div class="logo">
 <a href="../">
	 Math190 - Spring 2024 - Tufts Univ</a>
 </div>
 <nav>
 <a href="../about.html">About</a>
	 <a href="../course-pages/Math190--course-info.html">Info</a>	 
 <a href="../archive.html">Archive</a>
 </nav>
 </header>

 <main role="main">
 <h1>Representations and the symmetric group</h1>
 <article>
 <section class="header">
 Posted on 2024-02-07
 
 </section>
 <section>
 <h1 id="irreducible-representations-of-finite-abelian-groups">Irreducible representations of finite abelian groups</h1>
Let $A$ be a finite abelian group, written additively.
We set $\widehat A = \operatorname{Hom}(A,\mathbb{C}^\times)$ for the
set of all group homomorphisms $A \to \mathbb{C}^\times$. We can make
$\widehat A$ into a group by declaring for $\phi,\psi \in \widehat A$
that \[\phi\cdot \psi :A \to \mathbb{C}^\times\] is the mapping $a \mapsto \phi(a)\psi(a)$.
<dl>
<dt>Proposition:</dt>
<dd>
$\widehat A$ is an abelian group, and $\widehat A \simeq A$.
</dd>
<dt>Sketch:</dt>
<dd>
When $A = \mathbb{Z}/n\mathbb{Z}$ is cyclic let $\zeta = \exp(2 \pi i /n)$ be primitive $n$th root of unity.
For $j \in \mathbb{Z}/n\mathbb{Z}$, define
$\phi_j \in \widehat {\mathbb{Z}/n\mathbb{Z}}$ by
\[\phi_j(i + n \mathbb{Z}_) = \zeta^{ij}.\]
One checks that $j \mapsto \phi_j$ defines an isomorphism of groups
\[\mathbb{Z}/n\mathbb{Z} \to \widehat {\mathbb{Z}/n\mathbb{Z}}.\]
Now the Proposition follows by using that
\[\widehat{A \times B} \simeq \widehat{A} \times \widehat{B}\]
for abelian group $A$ and $B$.
</dd>
</dl>
Observe that elements of $\widehat A$ determine 1-dimensional
representations, which are necessarily irreducible. Since a
1-dimensional representation coincides with its trace, our results on
the characters of irreducible representations imply that the
functions $\mathbb{C}$-valued functions $\widehat{A}$ form an orthonormal
basis for $\mathbb{C}[A]$.
Let us write $\widehat{A} = \{\phi_1,\phi_2,\cdots,\phi_n\}$ where $n = |A|$.
Given a function $f: A \to \mathbb{C}$, i.e. an element $f \in \mathbb{C}[A]$, we may write
\[f = \sum_{i=1}^n \langle f,\phi_i \rangle \phi_i.\]
The Fourier transform of $f$ is the function
\[\widehat{f}:\widehat{A} \to \mathbb{C}\]
given by \[\widehat{f}(\phi) = \langle f, \phi \rangle.\]
<dl>
<dt>Remark:</dt>
<dd>
When $A = \mathbb{Z}/n\mathbb{Z}$, one often views the values
$f(i)$ for $i + n\mathbb{Z}$ as samples of some periodic
function of (say) a real variable $t$, viewed as time.
In that case, the domain of $\widehat{f}$ is viewed as
frequency.
</dd>
<dt>Remark:</dt>
<dd>
In any event, for abelian $A$ we have two natural bases for $\mathbb{C}[A]$:
the functions $\delta_a$ for $a \in A$, and the functions $\widehat{A}$.
</dd>
</dl>
<h1 id="how-to-study-mathbbcg-for-non-abelian-g">How to study $\mathbb{C}[G]$ for non-abelian $G$?</h1>
Idea: the matrix coefficients of linear representations define functions on $G$.
If $\rho:G \to \operatorname{GL}(V)$ is a linear representation, let
$b_1,\dots,b_n$ be a basis of $V$ and let $b_1^\vee,\cdots,b_n^\vee$ be the dual basis.
For $1 \le i,j \le n$ we get a function \[\rho_{i,j}:G \to
\mathbb{C}\] by the rule \[\rho_{i,j}(g) = b_i^\vee(\rho(g)b_j).\]
<dl>
<dt>Claim:</dt>
<dd>
Let $L$ be an irreducible representation and let
$\mathbb{C}[G]_{(L)}$ be the isotypic component of the regular
representation. Then the functions $\rho_{i,j}$ provide a basis
for $\mathbb{C}[G]_{(L)}$ where $\rho$ defines the irreducible
representation dual to $L$.
We omit the proof, and refer the reader
e.g.(James and Liebeck 2001) for the notion of
the dual of a representation.
But recall that we know that $[\mathbb{C}[G]_{(L)}:L] = \dim L$ so
that $\dim \mathbb{C}[G]_{(L)} = (\dim L)^2 = \dim \operatorname{End}(L).$
</dd>
</dl>
<h1 id="irreducible-representations-of-the-symmetric-group">Irreducible representations of the symmetric group</h1>
Recall that two elements $\sigma,\tau \in S_n$ are conjugate $\iff$
they have the same cycle structure. We state this in the following form:
<dl>
<dt>Lemma:</dt>
<dd>
Conjugacy classes in $S_n$ are in bijection with
partitions $\lambda \vdash n$.
</dd>
</dl>
For example, there are $5$ partitions of $4$; they are $\lambda = (1,1,1,1)$, $\lambda = (2,2)$, $\lambda = (2,1,1)$, $\lambda = (3,1)$,
and $\lambda=(4)$.
As a consequence, we know:
<dl>
<dt>Proposition:</dt>
<dd>
Isomorphism classes of irreducible representations of $S_n$ on
complex vector spaces are in bijection with partitions $\lambda \vdash n$.
</dd>
</dl>
Here is a quick overview of some facts about the representations of $S_n$,
without proofs:
In fact, for each partition $\lambda \vdash n$, there is a
construction of an irreducible representation $V_\lambda$ for
$S_n$. To begin the construction, associate with $\lambda$ the
subgroup \[S_\lambda = S_{\lambda_1} \times S_{\lambda_2} \times
\cdots \times S_{\lambda_r}\] let $\Omega_\lambda = S_n / S_\lambda$ be the set of left cosets of $S_\lambda$ in $S_n$.
Thus $\Omega_\lambda$ is a set on which the symmetric group $S_n$
acts, and we may consider the permutation representation
$\mathbb{C}[\Omega_\lambda]$, and for brevity we write $M^\lambda = \mathbb{C}[\Omega_\lambda]$.
One defines the dominance ordering on partitions of $n$ by the rule
\[\lambda \trianglelefteq \mu\] if and only if for each $\ell$
\[\sum_{i=1}^\ell \lambda_i \le \sum_{i=1}^\ell \mu_i.\]
There is a labeling of irreducible representations of $S_n$ by
partition; let us write $S^\lambda$ for the irreducible representation
corresponding to $\lambda$. It is known as a Specht representation.
<dl>
<dt>Theorem:</dt>
<dd>
$[M^\lambda:S^\lambda] =1$ and $[M^\lambda:S^\mu] &gt; 0 \implies \lambda \trianglelefteq \mu$.
</dd>
</dl>
As stated, the Theorem appears to depend on our knowledge of the irreducible
representations, but in fact it gives us a way to define them.
For a fixed $\lambda$, consider all homomorphisms of
$S_n$-representations \[M^\mu \to M^\lambda \quad \text{ for $\lambda
\trianglelefteq \mu$};\] lets write $R^\lambda \subset M^\lambda$ for
the sum of the image of all of these homomorphisms.
The Theorem implies that $M^\lambda / R^\lambda = S^\lambda$ is irreducible.
Here are some special cases:
<ul>
<li>if $\lambda = (n)$ then $M^\lambda = S^\lambda = \mathbf{1}$ is
the trivial representation.</li>
<li>if $\lambda = (1,1,\cdots,1)$ them $S^\lambda = \operatorname{sgn}$ is the (1-dimensional) sign representation.</li>
<li>if $\lambda = (n-1,1)$ then $M^\lambda$ is the permutation
representation $\mathbb{C}[\{1,2,\cdots,n\}]$, and \[M^\lambda =
S^\lambda \oplus \mathbf{1}\] so that $\dim S^\lambda = n-1$.
Observe that indeed $(n-1,1) \trianglelefteq (n)$.</li>
<li>when $n=3$, we saw previously that $S_3$ has 3 irreducible
representations. They can be described as
<ul>
<li>$S^{(3)} = \mathbf{1}$ the trivial representation</li>
<li>$S^{(1,1,1)} = \operatorname{sgn}$ the sign representation</li>
<li>$S^{(2,1)}$, an irreducible representation of dimension 2</li>
</ul></li>
</ul>
<h1 id="rank-preferences">Rank preferences</h1>
I want to describe in brief the ideas investigated in
(Diaconis 1989), which amounts as an application of
representation theory on the symmetric group to statistics.
<h2 id="first-an-example">First, an example</h2>
Suppose we were to ask people to rank their preferred ice cream
flavors from the following ordered list:
<ul>
<li>[ <code>pistachio</code>, <code>chocolate</code>, <code>strawberry</code>, <code>vanilla</code>, <code>neopolitan</code> ]</li>
</ul>
Numbering the flavors [ <code>0</code>, <code>1</code>, <code>2</code>, <code>3</code>, <code>4</code> ] in order, we can
represent an individual’s preference using a permutation $\sigma \in S_5$.
For example the preference list
<ul>
<li>[ <code>neopolitan</code>, <code>strawberry</code>, <code>chocolate</code>, <code>vanilla</code>, <code>pistachio</code> ]</li>
</ul>
corresponds to the product of transposition $(04)(12)$.
So our survey data amounts to a list of elements
$\sigma_1,\sigma_2,\dots,\sigma_N \in S_5$.
<h2 id="ranking-in-more-generality">Ranking in more generality</h2>
In general, $n$ will denote the number of items to be ranked,
and we assume given a list of ranking data:
\[\Sigma: \sigma_1, \sigma_2, \cdots, \sigma_m\]
The main statistic of interest is the frequency function
\[f = f_\Sigma:S_n \to \mathbb{C}\]
given for $\sigma \in S_n$ by the rule $f(\sigma) = \#\{\sigma_i \mid \sigma = \sigma_i\}$.
Idea: View $f$ as a vector in the regular representation
$\mathbb{C}[S_n]$. We want to understand how $f$ decomposes
in some natural descriptions of $\mathbb{C}[S_n]$.
<h1 id="bibliography">Bibliography</h1>
<div class="refs">

</div>
<div id="refs" class="references csl-bib-body hanging-indent" role="list">
<div id="ref-diaconisGeneralizationSpectralAnalysis1989" class="csl-entry" role="listitem">
Diaconis, Persi. 1989. “A Generalization of Spectral Analysis with Application to Ranked Data.” The Annals of Statistics 17 (3): 949–79. <a href="https://www.jstor.org/stable/2241705">https://www.jstor.org/stable/2241705</a>.
</div>
<div id="ref-jamesRepresentationsCharactersGroups2001" class="csl-entry" role="listitem">
James, Gordon, and Martin Liebeck. 2001. Representations and Characters of Groups. 2nd ed. Cambridge: Cambridge University Press. <a href="https://doi.org/10.1017/CBO9780511814532">https://doi.org/10.1017/CBO9780511814532</a>.
</div>
</div>
 </section>
</article>

 </main>

 <footer>
	 <nav>
	 <a href="http://www.tufts.edu">
	 
	 Tufts
	 </a>	 
	 <a href="http://math.tufts.edu">
	 
	 Tufts Math
	 </a>
	 <a href="https://gmcninch-tufts.github.io/math">
	 
	 G McNinch
	 </a>
	 <a href="https://github.com/gmcninch-tufts">
	 
	 GitHub
	 </a>	 
	 </nav>
 </footer>
 </body>
</html>

Collaborative Calculation and Data Science

colby

sagemath

Product

Resources

Company