Plane Partitions and Their Connection to the Alternating Sign Matrix Conjecture

Robert Rostermundt

Date: November 28, 2001

Definition:



An alternating sign matrix(ASM) is a matrix of 0's, 1's, and -1's with constant row sums and column sums, both equal to 1. Additionally, the non-zero entries in each row or column alternate in sign.

example:

$$\bordermatrix{&&&&&\cr &0&0&0&1&0 \cr &0&1&0&-1&1 \cr &1&-1&0&1&0 \cr &0&0&1&0&0 \cr &0&1&0&0&0 \cr}$$

Theorem:

The total number of $n\times n$ alternating sign matrices, $A_n$, is given by

$$A_n=\displaystyle \prod^{n-1}_{j=0}\displaystyle \frac{(3j+1)!}{(n+j)!}$$

History of the ASM's:



The determinant of an $n\times n\;matrix\;(a_{i,j})$ is defined as

$$\vert a_{i,j}\vert=\displaystyle \sum_{\sigma}(-1)^{I(\sigma)} \displaystyle \prod^{n}_{i=1}a_{i,\sigma(j)}$$

where $\sigma\in S_n$ and $I(\sigma)$ is the inversion number of $\sigma$.

However, for matrices larger than $3\times 3$ this formula becomes inefficient. Most are familiar with Gaussian elimination as a more efficient technique to find the determinant of a larger matrix, but there is another technique developed by Charles Lutwidge Dodgeson known as Dodgeson condensation. This technique is as follows....

Starting with an $n\times n$ matrix, one successively computes an $(n-1)\times (n-1)$ matrix, an $(n-2)\times (n-2)$ matrix, and continues until reaching a $1\times 1$ matrix whose only entry is the determinant of the initial matrix.


The rule for determining the entries of the $k\times k$ matrix is to take the $k^2$, $2\times 2$ connected subdeterminants of the $(k+1)\times (k+1)$ matrix and divide them by the corresponding $k^2$ central entires of the $(k+2)\times (k+2)$ matrix. (In the case where $k=n-1$ no division is performed.)

Applying Dodgson Condensation to the 3-by-3 matrix

$$\bordermatrix{&&&\cr &a&b&c\cr &d&e&f\cr &g&h&i \cr}$$

we first get the 2-by-2 matrix

$$\bordermatrix{&&\cr &ae-bd&bf-ce\cr &dh-eg&ei-fh\cr}$$

and finally the 1-by-1 matrix with entry

$$\bigg((ae^2i-aefh-bdei+bdfh)-(bdfh-befg-cdeh+ce^2g)\bigg)/e$$

and then grouping terms we arrive at

$$-(aei)-(afh)-(bdi)+0(bde^{-1}fh)+(bfg)+(cdh)-(ceg)$$

Six of the previous terms correspond to permutation matrices. For example, $(ahf)$ is associated with the permutation matrix with a one in place of terms $a$, $f$, and $h$, and zeros everywhere else.

$$\bordermatrix{&&&\cr &1&0&0\cr &0&0&1\cr &0&1&0 \cr}$$

Additionally, the vanishing term $bde^{-1}fh$ can be associated with the matrix with 1's in the positions of $b$, $d$, $f$, and $h$ and $-1$ in place of $e$.

$$\bordermatrix{&&&\cr &0&1&0\cr &1&-1&1\cr &0&1&0 \cr}$$

Notice that these are all $ASM's$.

How many ASM's are there for a given $n$?

The seven alternating sign matrices of size three, grouped by the position of the one in the first column.

$$\bordermatrix{&&&\cr &1&0&0 \cr &0&1&0 \cr &0&0&1 \cr},\;\;\;\; \bordermatrix{&&&\cr &1&0&0 \cr &0&0&1 \cr &0&1&0 \cr}$$

$$\bordermatrix{&&&\cr &0&1&0 \cr &1&0&0 \cr &0&0&1 \cr},\;\;\;\; \... ...\cr &0&1&0 \cr},\;\;\;\; \bordermatrix{&&&\cr &0&1&0 \cr &0&0&1 \cr &1&0&0 \cr}$$

$$\bordermatrix{&&&\cr &0&0&1 \cr &1&0&0 \cr &0&1&0 \cr},\;\;\;\; \bordermatrix{&&&\cr &0&0&1 \cr &0&1&0 \cr &1&0&0 \cr}$$

Seperating the different counts of alternating sign matrices by the position of the one in the first row we can form a pascal-like triangle where the $k^{th}$ entry in the $n^{th}$ row is the number of $n\times n$ $ASM's$ with a one in the $k^{th}$ column of the first row.

Notice that both triangles are symmetric and that the numbers that run down the outer edge count the number of alternating sign matrices of the previous size. This gave a sequence for the first few values for $A_n$.

$$1,2,7,42,429,7436,...$$

Having never seen this sequence before, the surprise was that this same sequence appeared in George Andrew's formula for counting the number of descending plane partitions of order $n$. Stanley was then able to verify that their conjectured formula for the number of ASM's was essentially the same as his proven formula for the number of descending plane partitions.

What is a Plane Partition?

Definition: A plane partition is a semblage of cubes inside an octant such that every cube is ``supported'' on three sides toward the bounding planes of the octant; to be supported on a particular side, a cube must be adjacent to another cube on that side, or the cube shares that face with one of the bounding planes of the octant.

Essentially, it can be thought of as stacking cubes into a right corner, where for each stack the top face is marked with the number of cubes in the stack. When we look at the cubes from above, these numbers form a plane partition.

These correspond to partitions of a number arranged 2-dimensionally in a quadrant.

Plane partitions were first studied by Percy A. MacMahon in 1897. MacMahon produced a genereating function for plane partitions that are subsets of $B(r,s,t)$ where

$$B(r,s,t) =\{(i,j,k):1\le i\le r, 1\le,j\le s, 1\le k\le t\}$$

The generating function (proved in 1912) is as follows

$$\displaystyle \prod^{r}_{i=1}\displaystyle \prod^{s}_{j=1}\displaystyle \frac{1-q^{i+j+t+1}}{1-q^{i+j-1}}$$

where the coefficient on $q^n$ is the number of plane partitions of $n$.

Before we can prove this theorem we need to build some tools, starting with lattice paths.
Lattice paths

How many ways can one travel from the origin to the point $(6,5)$, assuming that each step is directly up or directly right?

$$\left( \begin{array}{c} m+n\\ m\\ \end{array}\right)$$

A lattice path from $(0,0)$ to $(n,m)$ corresponds to a partition with at most $m$ parts and no part bigger than $n$. For example, the lattice path

corresponds to the partition

$$5+3+3+2=13$$

Proposition: The total number of partitions into at most $m$ parts with each part less than or equal to $n$ is

$$\left( \begin{array}{c} m+n\\ m\\ \end{array}\right)$$

Before introducing ther generating function for these partitions, we should look at the Young diagrams of a partition.

Each part of the partition is represented by a row of unit squares and the rows are all left justified. In general, the number of partitions of numbers less than or equal to $mn$, in which there at most $m$ parts and each part is less than or eaual to $n$, corresponds to the number of Young diagrams that that fit into our $n\times m$ rectangle.

There is a unique lattice path that traces from the top-right to the bottom left of each Young diagram.

It should be clear that all Young diagrams for the partition of $n=4$ will fit into the $6\times 5$ rectangle.

When $m=5$, and $n=6$ we arrive at the following generating function

$$f_{6,5}(q) = 1+q+2q^2+3q^3+5q^4+7q^5+10q^6$$

$$+12q^7+16q^8+19q^9+23q^{10}+25q^{11}$$

$$+29q^{12}+30q^{13}+32q^{14}+32q^{15}$$

$$+32q^{16}+30q^{17}+29q^{18}+25q^{19}$$

$$+23q^{20}+19q^{21}+16q^{22}+12q^{23}$$

$$+10q^{24}+7q^{25}+5q^{26}+3q^{27}+2q^{28}$$

$$+q^{29}+q^{30}$$

where the coefficient on $q^{k}$ is the number of Young diagrams for $k$ that fit into the $m\times n$ rectangle.

Notice that

$$f_{6,5}(1)= \left( \begin{array}{c} m+n\\ m\\ \end{array}\right)$$

Notice that the number of Young diagrams for a certain $k$ that fit into the $6\times 5$ rectangle is less than or equal to the number of partitions of the number $k$. We know that the number of partitions of an integer $k$ is the coefficient on the term $q^k$ in the power series

$$\displaystyle \prod^{\infty}_{i=1}\displaystyle \frac{1}{1-q^i}=1+q+2q^2+3q^3+...$$

The coefficient on $q^7$ is 15. But only twelve of these partitions have Young diagrams that fit into our $6\times 5$ rectangle. The following do not fit...

This polynomial $f_{m,n}(q)$ is called the Gaussian polynomial. Because it is a generalization of the binomial coefficient we will use the notation

$$f_{m,n}(q)= \left[ \begin{array}{c} m+n\\ m\\ \end{array}\right]_{q}$$

Propsition: If $m$ and $n$ are positive integers, then

$$\left[ \begin{array}{c} m+n\\ m\\ \end{array}\right]_{q} = \displaystyle \frac{(1-q)....(1-q^{m+n})}{(1-q)...(1-q^m)(1-q)...(1-q^n)}$$

$$= \displaystyle \prod^{m}_{i=1}\displaystyle \frac{1-q^{n+i}}{1-q^i}$$

proof: We need to show that both sides of the equation satisfy the same recursive formula and the same boundary conditions.

Given a partition with at most $m$ parts and each part less than or equal to $n$ there are two distinct possibilities

1) All of the parts are strictly less than $n$, in which case we get the generating function

$$\left[ \begin{array}{c} m+n-1\\ m\\ \end{array}\right]_{q}$$

2) The largest part is exactly $n$; record this with $q^n$. Then what remains is a partition into at most $m-1$ parts each less that or equal to $n$. The generating function is

$$q^n\left[ \begin{array}{c} m+n-1\\ m-1\\ \end{array}\right]_{q}$$

We get the following recursion

$$\left[ \begin{array}{c} m+n\\ m\\ \end{array}\right]_{q}= \le... ...ght]_{q}+\; q^n\left[ \begin{array}{c} m+n-1\\ m-1\\ \end{array}\right]_{q}$$

The Gausssian polynomial, also called the q-binomial coefficient is thus uniquely defined by its boundary conditions. These are when $n=0$ and when $m=0$. In each case all steps are either to the right or all steps are up and the only thing we are left with is the empty partition. So

$$\left[ \begin{array}{c} m\\ 0\\ \end{array}\right]= \left[ \begin{array}{c} m\\ m\\ \end{array}\right]=1$$

So defining the product $$\prod^{0}_{i=1}\displaystyle \frac{1-q^{n+i}}{1-q^i}=1$$, and seeing that this product is also one when at the boundary $n=0$, we just need to show that it satisfies the following recursion

$$\displaystyle \prod^{m}_{i=1}\displaystyle \frac{1-q^{n+i}}{1-q^i... ...i}\;+\; q^n\displaystyle \prod^{m-1}_{i=1}\displaystyle \frac{1-q^{n+i}}{1-q^i}$$

Define

$$(*)\;=\displaystyle \prod^{m}_{i=1}\displaystyle \frac{1-q^{n-1+i}}{1-q^i} = \displaystyle \frac{(1-q^{n})...(1-q^{n+m-1})}{(1-q)...(1-q^{m})}$$

$$(\char93 )\;=\displaystyle \prod^{m-1}_{i=1}\displaystyle \frac{1-q^{n+i}}{1-q^i} = \displaystyle \frac{(1-q^{n+1})...(1-q^{n+m-1})}{(1-q)...(1-q^{m-1})}$$

Let $S=(*)+q^n(\char93 )$

$$S = \displaystyle \frac{(1-q^n)...(1-q^{n+m-1})}{(1-q)...(1-q^m)}$$

$$+ q^n\displaystyle \frac{(1-q^{n+1})...(1-q^{n+m-1})}{(1-q)...(1-q^{m-1})}$$

$$= \displaystyle \frac{(1-q^n)...(1-q^{n+m-1})}{(1-q)...(1-q^m)}$$

$$+ q^n\displaystyle \frac{(1-q^m)(1-q^{n+1})...(1-q^{n+m-1})}{(1-q)... (1-q^{m-1})(1-q^m)}$$

$$= \displaystyle \frac{(1-q^{n+1})...(1-q^{n+m-1})\bigg[1-q^n+q^n(1-q^m)\bigg]} {(1-q)...(1-q^m)}$$

$$= \displaystyle \frac{(1-q^{n+1})...(1-q^{n+m})}{(1-q)...(1-q^m)}= \displaystyle \prod^{m}_{i=1}\displaystyle \frac{1-q^{n+i}}{1-q^i}$$

Inversion Numbers:

There is a one-to-one correspondence between lattice paths from $(0,0)$ to $(n,m)$ and sequences that consist of $m$ zeros and $n$ ones. Each zero marks off a step to the north. The size of the step to the north is denoted by the number of ones to the left of the zero.

The inversion number of a sequence $I(s)$ is the sum of the parts of the partition.

We get the following corollary

$$\displaystyle \sum_{s\in S(n,m)}q^{I(s)}= \left[ \begin{array}{c}... ...ray}\right]= \displaystyle \prod^{m}_{i=1}\displaystyle \frac{1-q^{n+i}}{1-q^i}$$

We also have the following definition of the inversion number of a sequence of integers. We take each term in the sequence and count the number of terms to its left that are strictly larger. The sum of these numbers is the inversion number of the sequence.

For example,

$$I(36224153)=0+0+2+2+1+5+1=11$$

This can be extended to a definition of the q-multinomial coeffiecient.

$$\left[ \begin{array}{c} m_1+m_2+...+m_n\\ m_1,m_2,...,m_n\\ \end{array}\right]= \displaystyle \sum_{s\in S}q^{I(s)}$$

where $S$ is the set of all sequences with $m_1$ 1s, $m_2$ 2s,..., $m_n$ $n$s.

It can be shown that

$$\left[ \begin{array}{c} m_1+m_2+...+m_n\\ m_1,m_2,...,m_n\\ \... ...t]_{q}= \displaystyle \frac{(q;q)_{m_1+m_2+...m_n}}{(q;q)_{m_1}....(q;q)_{m_n}}$$

where $(q;q)_k=(1-q)....(1-q^k)$

Consider the permutation group $S_n$, where for a sequence of a given permutation $\sigma$, the $i^{th}$ entry is $\sigma(i)$. It is clear that $m_1=m_2=....=m_n=1$. Therefore, we get the following

Theorem: If we let $S_n$ denote the permutations on $n$ letters, then

$$\displaystyle \sum_{s\in S_n}q^{I(s)}=\displaystyle \frac{(1-q)(1-q^2)...(1-q^n)}{(1-q)^n}$$

Recall that the inversion number of a permuation appears in the definition of the determinant of a matrix

$$\vert a_{i,j}\vert=\displaystyle \sum_{\sigma}(-1)^{I(\sigma)} \displaystyle \prod^{n}_{i=1}a_{i,\sigma(j)}$$

We now have tools to prove MacMahon's Theorem on the number of plane partitions that fit into $B(r,s,t)$.

We use lattice paths to show that the generating function for plane partitions that fit inside $B(r,s,t)$ is given by the determinant

$$det\bigg(q^{i(i-j)} \left[ \begin{array}{c} s+t\\ s-i+j\\ \end{array}\right] \displaystyle \bigg)^{r}_{i,j=1}$$

Then an application of Krattentheler's formula proves that this determinant is expressed as the product

$$\displaystyle \prod_{(i,j,k)\in B(r,s,t)}\displaystyle \frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}$$

Start with a representation of a plane partition

The entries are weakly decreasing as we move to the right across any row or down any column. If this plane partition fits into $B(r,s,t)$ then it has at most $r$ rows, $s$ columns, and the largest part is less than or equal to $t$. This example fits inside th box $B(7,6,6)$.

Each row is itself a normal partition with at most $s$ parts and no part greater than $t$. So any plane partition in $B(r,s,t)$ is a sequence of $r$ ordinary partitions.

The first row in the plane partition can be seen as the following ordinary partition with no more than 6 parts and none of the parts is greater than 6.

$$6+5+5+4+3+3$$

These $r$ partitions can not be chosen independently. We need the condition that the $j^{th}$ part of the $i^{th}$ partition must be less than or equal to the $j^{th}$ part of the $i-1$ partition. So we build a $nest$ of lattice paths corresponding to each partition in the following way.

Starting in our lattice at $(0,0)$ we represent the first row of the plane partition its lattice path from $(0,0)$ to $(t,s)$. Then the next path above it (corresponding to the ordinary partition of the second row) starts at the point $(-1,1)$ and ends at the point $(t-1,s+1)$. Continue this pattern until each of the $r$ rows of the partition are accounted for.

Given our example of a plane partition we get the following nest.

Now starting at the top-most lattice path (which is the empty partition) number the paths from 1 to $r$. The condition that the $j^{th}$ part of the $i^{th}$ partition must be less than or equal to the $j^{th}$ part of the $i-1$ partition is accounted for by having a nest of non-intersecting lattice paths.

The question of counting plane partitions in $B(r,s,t)$ has become counting the number of non-intersecting nests of $r$ lattice paths (each with no more than $s$ parts and each part less than or equal to $t$.)

Counting non-intersecting lattice paths

Each nest defines a permutation of the integers 1 through $r$ as follows. Let the $i^{th}$ path be the path that ends at $(t-r+i,s+r-i)$. Then call the $j^{th}$ starting point $(-r+j,r-j)$. If the $i^{th}$ path starts at the $j^{th}$ starting point then we define $\sigma(i)=j$. The following ``tangled'' nest corresponds the the permutation

$$3517246$$

It should be clear that any non-intersecting path corresponds to the identity permutation.

Given a permutation, $\sigma$, the $i^{th}$ path in the nest must begin at the vertex $(-r+\sigma(i),r-\sigma(i))$ and end at the point $(t-r+i,s+r-i)$. So it takes $t+i-\sigma(i)$ steps to the right and $s-i+\sigma(i)$ steps up. The number of such lattice paths is

$$\left( \begin{array}{c} t+s\\ s-i+\sigma(i)\\ \end{array}\right)$$

Then the number of nests that correspond to the permutation $\sigma$ is

$$\displaystyle \prod^{k}_{i=1} \left( \begin{array}{c} t+s\\ s-i+\sigma(i)\\ \end{array}\right)$$

We arrive at the following

Theorem: The number of plane partition that fit inside $B(r,s,t)$ is

$$\displaystyle \sum_{s\in S_r}(-1)^{I(s)}\displaystyle \prod^{r}_{i=1} \left( \begin{array}{c} t+s\\ s-i+\sigma(i)\\ \end{array}\right)$$

which equals

$$\det\left( \left( \begin{array}{c} t+s\\ s-i+\sigma(i)\\ \end{array}\right) \displaystyle \right)^{r}_{i,j=1}$$

proof: The determinant is the sum over all possible nests where each nest is counted as +1 if the inversion number of $\sigma$ is even and as -1 if the inversion number of $\sigma$ is odd. Knowing that all non-intersecting nests correspond to the identity, each will be counted as +1. We need to show that all other counts cancel each other out.

Given a nest with at least one point of intersection, choose the point of intersection that is furthest right (and highest of two or more intersections occur in the same column). Now switch the paths at that point as seen below

The effect is to change the permutation

$$3517246$$

to the permutation

$$3517264$$

and this changes the inversion number of the permutation by one, turning an even permutation into an odd and vice-versa.

$$I(3517246)=0+0+2+0+3+2+1=8$$

$$I(3517264)=0+0+2+0+3+1+3=9$$

Because each intersecting nest corresponding to the permutation $\sigma$ has a ``tail-switched'' counterpart with the permutation $\tau$ that has a different sign inversion number, we can see that all counts of intersecting lattice path nests will cancel each other out.

BLAM!

There is however a problem with this ``tail-switching'' operation.

becomes

where the first two lattice paths sum to 32 and the second two sum to 30.

When creating our generating function, rather than assigning a one to each nest, we want to assign a power of $q$ which is the number that is being partitioned. So we need to adjust the power over $q$ by the difference in the partitions we are summing. Point is, we are not able to simply replace a binomial coefficient with a Gaussian polynomial.

By the way we have chosen the intersection point we will always be switching two lattice paths that are adjacent, call them the $i^{th}$ and the $i+1st$ path. Looking at the sum of the nest's partitions, when we switch the tails of the $i^{th}$ and the $i+1st$ paths the difference in the sum will be increased by $\sigma(i)-\sigma(i+1)$ of the original sum.

We can define the amount that is being partitioned as the sum of the amounts partitioned by the lattice paths, plus

$$i(i-\sigma(i))$$

We are adjusting the power over $q$ in the generating function by $i(i-j)$ and we arrive at the desired result

Theorem: The generating function for plane partitions that fit inside $B(r,s,t)$ is

$$\displaystyle \sum_{\sigma\in S_r}(-1)^{I(\sigma)} \displaystyle ... ...sigma(i))} \left[ \begin{array}{c} t+s\\ s-i+\sigma(i)\\ \end{array}\right]$$

$$=det\bigg(q^{i(i-\sigma(i))}\left[ \begin{array}{c} t+s\\ s-i+\sigma(i)\\ \end{array}\right] \bigg)^{r}_{i,j=1}$$

An application of Krattenthaler's forumla shows that this determinant can be written as the product

$$\displaystyle \prod^{r}_{i=1}\displaystyle \prod^{s}_{j=1}\displaystyle \frac{1-q^{i+j+t+1}}{1-q^{i+j-1}}$$

BOOM!

An application

Directed graph for ``square ice'' on square lattice