### The Waldspurger Transform of Permutations and Alternating Sign Matrices

#### University of Miami James McKeown

Joint with Drew Armstrong

FPSAC 2017 London

Finite Reflection Groups

An element $g \in O(n)$ is a reflection if it sends some nonzero vector $\alpha \in \mathbb{R}^n$ to its negative and fixes the hyperplane orthogonal to $\alpha$ pointwise.

Let $G \subset O(n)$ be a finite group generated by reflections.

Theorem (Coxeter): Let $\mathcal{A}$ be an arrangement in $\mathbb{R}^n$ of reflecting hyperplanes for the reflection group $G$. Then $G \curvearrowright \mathbb{R}^n \backslash (\displaystyle \bigcup_{H∈\mathcal{A}}H)$ freely and transitively on the chambers.

We pick one such chamber and call it the “weight cone” denoted $C_W$. The cone dual to $C_W$ we call the “root cone” and denote $C_R$.

Fact (Coxeter): $C_w$ is a simplicial cone.

Let $w_1,w_2,\dots,w_n$ be vectors generating the rays of $C_W$.
[Jargon: called the "fundamental weights"]

Then the dual cone is defined as $$C_R:=\{x \in \mathbb{R}^n: (x,y)\leq 0 \space \space \forall y \in C_W\}$$ Let $\alpha_1,\alpha_2,\dots,\alpha_n$ be vectors which generate rays of $C_R$.
[Jargon: called the "simple roots"]

In type $A$, it is conventional to let $\alpha_i=e_i-e_{i+1}$ so $(\alpha_i,\alpha_i)=2$ $\forall i.$

Lengths of weights are then normalized so that \begin{equation*} - \begin{pmatrix} | &| & | & | \\ | &| & | & | \\ \alpha_1 &\alpha_2 & \dots & \alpha_n\\ | &| & | & | \\ | &| & | & | \end{pmatrix}= \begin{pmatrix} | &| & | & | \\ | &| & | & | \\ w_1 &w_2 & \dots & w_n\\ | &| & | & | \\ | &| & | & | \end{pmatrix}^{-1} \end{equation*}

The matrix of $\alpha$'s is called the Cartan Matrix. It gives the coordinates of the simple roots in the basis of fundamental weights.

Waldspurger's Theorem
Waldspurger’s Theorem (2005):

For $G$ a finite reflection group acting on a Euclidean vector space $V$, $C_R$ the (closed) cone over the positive roots, and $C_W \subset V$ the interior of a fundamental domain for the action of $G$ (sometimes called the weight cone), one has the following decomposition:

###### $$C_R = \bigsqcup_{g \in G}(1-g)C_W$$
Meinrenken's Theorem (2007):

For $G$ an affine reflection group acting on a Euclidean vector space $V$, and $\mathring{A}_W\subset V$ the interior of a fundamental domain for the action of $G$ (sometimes called a fundamental alcove) one has the following decomposition:

###### $$V=\displaystyle \bigsqcup_{g\in G} (1-g) \mathring{A}_W$$
Permutations

Can we view this map in a more combinatorial way?

Waldspurger Matrices

Consider the reflection representation of the symmetric group $$\phi:\mathfrak{S}_n \longrightarrow GL_{n-1}(\mathbb{R})$$ Let $D$ be the matrix with columns the fundamental weights in basis of the simple roots (i.e. the $(n-1) \times (n-1)$ inverse of the Cartan matrix).
$$\mathbf{WT}(g):=[\phi(1)-\phi(g)]D$$ expressed in the coordinates of simple roots we will call the
Waldspurger Matrix of $g$.

Consider the permutation $456213 \in \mathfrak{S}_6$

that is, $456213 \mapsto \left\{a_1\left(\begin{array}{c}1\\1\\1\\0\\0\end{array}\right)+ a_2\left(\begin{array}{c}1\\2\\2\\1\\0\end{array}\right)+ a_3\left(\begin{array}{c}1\\2\\3\\2\\1\end{array}\right)+ a_4\left(\begin{array}{c}1\\1\\2\\2\\1\end{array}\right)+ a_5\left(\begin{array}{c}0\\0\\1\\1\\1\end{array}\right) \middle| a_i \in \mathbb{R}_{\geq 0} \right\}=:C_{\pi}$

Geometry
###### $A_3$ Waldspurger Decomposition

Not convex?

Not simplicial or CW?

If they're not "vertices," then what are these vectors?

UM vectors

The rows and columns of Waldspurger Matrices

A UM vector is a vector $v=\{v_1,v_2\dots,v_n \}$ with $v_i \in \mathbb{Z}$ and $v_1,v_n \in \{0,1\}$ such that

entries weakly increasing by one's up to some entry (the diagonal), weakly decreasing by one's after.

"UM" for Unimodal Motzkin paths. There are $2^n$ UM vectors of length $n$.

Interpretations as:
1. Young diagrams with hooklength less than $n$
2. Abelian ideals in the nilradical of $\mathfrak{sl}_n(\mathbb{C})$
3. Elements of the root lattice inside a certain polytope

To be the Waldspurger Transform of a permutation, is it sufficient to have UM vectors as rows and columns (with maximums on the diagonal)?

No. Stay tuned...

Alternating Sign Matrices

An alternating sign matrix (or ASM) is a square matrix of $0$'s, $1$'s, and $−1$'s such that the sum of each row and column is $1$ and the nonzero entries in each row and column alternate in sign.

Theorem (Zeilberger '92): The number of $n \times n$ ASMs is $\prod _{{k=0}}^{{n-1}}{\frac {(3k+1)!}{(n+k)!}}={\frac {1!4!7!\cdots (3n-2)!}{n!(n+1)!\cdots (2n-1)!}}$.

These matrices generalize permutation matrices and arise naturally when using Dodgson condensation to compute a determinant.

ASMs, Monotone Triangles, Reduced Monotone Triangles

$$\left[\begin{matrix} 0&0&1&0&0&0\\ 0&1&-1&1&0&0\\ 0&0&0&0&1&0\\ 0&0&1&0&-1&1\\ 1&0&0&0&0&0\\ 0&0&0&0&1&0\\ \end{matrix}\right] \leftrightarrow \begin{matrix} 3&&&&\\ 2&4&&&\\ 2&4&5&&\\ 2&3&4&6\\ 1&2&3&4&6\\ 1&2&3&4&5&6\\ \end{matrix} \leftrightarrow \begin{matrix} 2&&&&\\ 1&2&&&\\ 1&2&2\\ 1&1&1&2\\ 0&0&0&0&1 \end{matrix}$$

Theorem (Lascoux and Schützenberger, '96): Componentwise comparison of monotone triangles is the Dedekind-MacNeille lattice completion of Bruhat order.

The rank of a permutation in this lattice is the sum of the entries in the corresponding reduced monotone triangle $$\frac{1}{2}\displaystyle\sum_{i=1}^n(g(i)-i)^2$$

$$\displaystyle\sum_{1\leq i,j \leq n-1}\mathbf{WT}(g)=\frac{1}{2}\displaystyle\sum_{i=1}^n(g(i)-i)^2$$
Given an $n \times n$ matrix $M$, define the $(n-1) \times (n-1)$ matrix, $\mathbf{WT}(M)$ where $$\mathbf{WT}(M)_{i,j}:=\begin{cases} \displaystyle\sum_{\substack{a\leq i\\b>j}}M_{a,b} & i\leq j \\ \displaystyle\sum_{\substack{a> i\\b\leq j}}M_{a,b} & i\geq j\\ \end{cases}.$$

Proposition1: The diagonal will only be well defined if $M$ is sum symmetric.

Theorem: $\mathbf{WT}(M)$ will have UM vectors for rows and columns with maxes on the diagonal iff $M$ is an alternating sign matrix.

Theorem: The Waldspurger Transform of ASMs is isomorphic to the lattice of Monotone Triangles.

Paint and Peel

$$\left[\begin{matrix} 0&0&1&0&0&0\\ 0&1&-1&1&0&0\\ 0&0&0&0&1&0\\ 0&0&1&0&-1&1\\ 1&0&0&0&0&0\\ 0&0&0&0&1&0\\ \end{matrix}\right] \leftrightarrow \begin{matrix} 3&&&&\\ 2&4&&&\\ 2&4&5&&\\ 2&3&4&6\\ 1&2&3&4&6\\ 1&2&3&4&5&6\\ \end{matrix} \leftrightarrow \begin{matrix} 2&&&&\\ 1&2&&&\\ 1&2&2\\ 1&1&1&2\\ 0&0&0&0&1 \end{matrix}$$

This lattice is distributive!
###### $\pi$ is Join-Irreducible iff $\pi$ is Bigrassmannian.

The number of bigrassmannian perutations is a tetrahedral number. $$\frac{1}{(1-z)^4}=1+4z+10z^2+20z^3+35z^4+\dots.$$

$\begin{matrix} 1&1&1&1&1\\1&2&2&2&1\\1&2&3&2&1\\1&2&2&2&1\\1&1&1&1&1 \end{matrix}$

###### The height statistic is geometric
Types B and C

Theorem (Lascoux and Schützenberger, '96): The lattice completion of type B Bruhat order is distributive.

###### $g$ Join Irreducible $\Rightarrow$ $g$ bigrassmannian.

# of Bigrassmannian elements is $$\frac{1}{(1-z)^5}+\frac{1}{(1-z)^4}=1+6z+19z^2+45z^3+161z^4+\dots$$

# of Join Irreducibles (elements of the "base") is an octahedral number $$\frac{(1+z)^2}{(1-z)^4}=1+6z+19z^2+44z^3+146z^4+\dots$$

Waldspurger & Meinrenken theorems still hold
###### $$V=\displaystyle \bigsqcup_{g\in G} (1-g) \mathring{A}_W$$
$B_n\subset\mathfrak{S}_{2n}$
$B_n\subset\mathfrak{S}_{2n}$

"Fold" centrally symmetric type A Waldspurger matrices to get type C Waldspurger matrices

$\left[\begin{matrix} 1&1&1&1&1&0&0\\ 1&2&2&2&2&1&0\\ 1&2&3&3&3&2&1\\ 1&2&3&3&3&2&1\\ 1&2&3&3&3&2&1\\ 0&1&2&2&2&2&1\\ 0&0&1&1&1&1&1 \end{matrix}\right] \mapsto \left[ \begin{matrix} 1&1&2&1\\ 1&3&4&2\\ 2&4&6&3\\ 1&2&3&3 \end{matrix} \right]$

$2 \cdot 3^{n-1}$ column vectors

Can we fold centrally symmetric ASM Waldspurger Matrices to get a lattice?

'

$$\frac{1}{(1-z)^5}+\frac{1}{(1-z)^4}=1+6z+19z^2+45z^3+161z^4+\dots$$ vs $$\frac{(1+z)^2}{(1-z)^4}=1+6z+19z^2+44z^3+146z^4+\dots$$

$$\left[ \begin{matrix} 1&1&0&0\\ 1&\colorbox{green}{2}&1&0\\ 0&1&1&0\\ 0&0&0&0 \end{matrix} \right] \textrm{ vs } \left[ \begin{matrix} 0&0&0&0\\ 0&\colorbox{green}{2}&2&1\\ 0&2&2&1\\ 0&2&2&1 \end{matrix} \right].$$

$$\left[ \begin{matrix} 1&1&0&0\\ 1&\colorbox{green}{2}&1&0\\ 0&1&1&0\\ 0&0&0&0 \end{matrix} \right] \textrm{ vs } \left[ \begin{matrix} 0&0&0&0\\ 0&\colorbox{green}{2}&2&1\\ 0&2&2&1\\ 0&2&2&1 \end{matrix} \right].$$

$$\left[\begin{matrix} 1&1&0&0&0&0&0\\ 1&\colorbox{green}{2}&1&0&0&\colorbox{green}{0}&0\\ 0&1&1&0&0&0&0\\ 0&0&0&0&0&0&0\\ 0&0&0&0&1&1&0\\ 0&\colorbox{green}{0}&0&0&1&\colorbox{green}{2}&1\\ 0&0&0&0&0&1&1 \end{matrix} \right] \textrm{ vs } \left[\begin{matrix} 0&0&0&0&0&0&0\\ 0&\colorbox{green}{1}&1&1&1&\colorbox{green}{1}&0\\ 0&1&1&1&1&1&0\\ 0&1&1&1&1&1&0\\ 0&1&1&1&1&1&0\\ 0&\colorbox{green}{1}&1&1&1&\colorbox{green}{1}&0\\ 0&0&0&0&0&0&0 \end{matrix} \right].$$

Waldspurger Order $\neq$ Bruhat Order?

$$\left[ \begin{matrix} 1&1&0&0\\ 1&2&1&0\\ 0&1&1&0\\ 0&0&0&0 \end{matrix} \right]< \left[ \begin{matrix} 2&2&2&1\\ 2&2&2&1\\ 2&2&2&1\\ 2&2&2&1 \end{matrix} \right] \textrm{ and } \left[ \begin{matrix} 0&0&0&0\\ 0&2&2&1\\ 0&2&2&1\\ 0&2&2&1 \end{matrix} \right]< \left[ \begin{matrix} 1&1&1&0\\ 1&2&3&1\\ 1&3&5&2\\ 0&2&4&2 \end{matrix} \right].$$

Future Exploration

Theorem (Meinrenken): For $W^a$ an affine Weyl group, given $S \in \textrm{End}(V)$ with sufficiently small determinant, and $V_w^{(S)}:=(S-w)A$ where $A$ is the fundamental alcove, the $V_w^{(s)}$ are all disjoint and their closures cover the entire vector space $V$.