Transcript bYTEBoss ASM_powerpoint

Alternating Sign Matrices
and Symmetry
(or)
Generalized Q*bert Games:
An Introduction
(or)
The Problem With
Lewis Carroll
By Nickolas Chura
What to discuss…
•
•
•
•
What are Alternating Sign Matrices?
A counting problem
How are they symmetric?
Some faces of Alternating Sign Matrices
Matrices & Determinants
• A Matrix is a rectangular array of numbers.
• An example of a 3-by-3 matrix:
 3 1 5 


0 2
 2
 2.5 7 4 


Matrices & Determinants
• The determinant of a square matrix is a
number.
• The study of Matrices and Determinants has
been traced back to the 2nd century BC.
• Question: How are determinants computed?
Answer: Lots of ways. Here is a lesser-known
method…
Matrices & Determinants
• Charles Dodgson (a.k.a.
Lewis Carroll) developed a
method for computing
determinants called the
method of condensation.
• So how does it work?
Matrices & Determinants
The determinant of the 2-by-2 matrix
a b 


c d 
is defined to be the number
ad  bc.
Example: The determinant of
is equal to
3 1


5 4
(3)( 4)  (1)(5)  12  5  7
Matrices & Determinants
The Method of Condensation –
• Let A be an n-by-n matrix. Compute the
determinant of each connected 2-by-2 minor of
A and form an (n-1)-by-(n-1) matrix from these
numbers.
• Repeat this process until a 1-by-1 matrix results.
• After 2 iterations, each entry in resulting
matrices must be divided by the center entry of
the corresponding 3-by-3 submatrix 2 steps
prior.
Matrices & Determinants
The Method of Condensation –
Example:
 1 1  3 2 

  5 7  4   6
54    2 27 


2
3
2
0


 3
2 


8
10
2

 0

 2 1 4 1  
 40   0  10 

   8  10  6   1
4

 4 2  2  2


20

2
10
Matrices & Determinants
Why haven’t you heard of this method before?
Consider using condensation on our 1st example
of a matrix:
 3 1 5 


0 2
 2
 2.5 7 4 


Will condensation give the correct answer of 31?
Ans: No. We will end up with 0/0.
Matrices & Determinants
Ignoring the problem of division by zero, if we use
condensation on a general 3-by-3 matrix:
a b

d e
g h

c
  ae  bd bf  ce 

f   
dh  eg ei  fh 


i
 aei  afh  bdi  bdfhe1  bdfhe1  bfg  cdh  ceg
We get 7 distinct terms (up to sign)…
Matrices & Determinants
For each term, create a 3-by-3 matrix whose entries
are the exponents of the variables in their original
positions.
aei
afh
bdi
bdfhe1
bfg
cdh
ceg
 1 0 0 1 0 0  0 1 0  0 1 0  0 1 0  0 0 1  0 0 1

 
 
 
 
 
 

 0 1 0   0 0 1   1 0 0   1 1 1   0 0 1   1 0 0   0 1 0 
 0 0 1  0 1 0  0 0 1  0 1 0 1 0 0  0 1 0 1 0 0

 
 
 
 
 
 

Matrices & Determinants
 1 0 0 1 0 0  0 1 0  0 1 0  0 1 0  0 0 1  0 0 1

 
 
 
 
 
 

 0 1 0   0 0 1   1 0 0   1 1 1   0 0 1   1 0 0   0 1 0 
 0 0 1  0 1 0  0 0 1  0 1 0 1 0 0  0 1 0 1 0 0

 
 
 
 
 
 

Things to notice about these matrices:
• The entries are 0, 1, or -1
• The columns and rows each sum to 1
• The nonzero entries of rows and columns
alternate in sign
Definition: An Alternating Sign Matrix (or ASM) is
an n-by-n matrix whose entries are each 0, 1, or
-1 with the property that the sum of each row or
column is 1, and the non-zero entries in any row
or column alternate in sign.
Examples:
(1)
1 0


0 1
0 0 1 0

 0 1 1 1
 0 0 1 1

 1 1 0 1
0 1 0 0

0

0
1

0
0 
Any permutation matrix is an ASM.
Alternating Sign Matrices
David Robbins introduced
ASMs and studied them along
with Howard Rumsey and
William Mills in the 1980s.
They conjectured that the
number of n-by-n ASMs is
given by the formula:
(3 j  1)!
An  
j  0 ( n  j )!
n 1
Alternating Sign Matrices
Compare the growth of An and n!:
n
n!
An
1
1
1
2
2
2
3
6
7
4
24
42
5
120
429
6
720
7436
7
5040
218348
8
40320
10850216
9
362880
911835460
10
3628800
129534272700
Alternating Sign Matrices
• This is an important counting problem which
answers many interesting questions.
• Conjecture was proved in 1996 by Doron
Zeilberger.
• Also in 1996, Greg Kuperberg discovered a
connection to physics, leading to a simpler
proof.
Alternating Sign Matrices
What did Kuperberg discover?
Physicists had been studying ASMs under a
different name: Square Ice
Square ice?
It is a 2-dimensional square lattice of water
molecules.
Alternating Sign Matrices
An example of Square Ice:
Alternating Sign Matrices
Square Ice is really a connected directed
graph:
• Oxygen atoms are vertices
• Hydrogen atoms are edges
• An edge points toward the vertex which
it is bonded to
• Require* that Hydrogens are bonded all
along the sides and none top or bottom
Alternating Sign Matrices
Our example of Square Ice seen as a graph:
Alternating Sign Matrices
To change Square Ice into an ASM:
• There are 6 types of internal vertices
• Replace the vertices by 0, 1, or -1
according to their type
Alternating Sign Matrices
Our Square Ice graph and its ASM:
0 1

 1 1
0 0

0 1

0 0

1 0

0 1


0 0
Alternating Sign Matrices
To change an ASM into Square Ice:
• Replace the 1s and -1s by their vertex
types.
• Choose the 0-vertex type so orientations
along the horizontal and vertical paths
through that vertex are unchanged.
• Conclusion: ASMs and Square Ice
(with *) are in bijection.
Square Ice
• Impose coordinates on our graph.
• Define the parity of a vertex (x, y) to be
the parity of x + y.
• Color an edge blue if it points from an odd
to an even vertex, color green otherwise.
Square Ice
Our resulting graph becomes
Square Ice
Facts about the 2-colored graph:
• Exterior edges alternate in color.
• Monochromatic components are either
paths connecting exterior vertices or they
are cycles.
• The graph is determined by either the blue
or green subgraph.
Square Ice
The 7 3-by-3 ASMs and their Square Ice
blue subgraphs:
1 0 0
1 0 0
 0 1 0






0 1 0
0 0 1
1 0 0
0 0 1
0 1 0
0 0 1






0 0 1
0 0 1
0 1





1 0 0
 0 1 0
 1 1
0 1 0
1 0 0
0 1





 0 1 0


0 0 1
1 0 0


0

1
0 
Square Ice
Now number the external blue vertices…
and call vertices joined by a path paired.
Square Ice
Now rotate the numbers 60o anticlockwise…
and the pairing gets rotated clockwise.
Square Ice
The we
But
pairing
already
of these
had graphs
graphswith
is (2,3)(4,5)(6,1).
this pairing…
But
so there
after rotation,
were 2 before
it becomes
and 2 (1,2)(3,4)(5,6).
after rotating.
Square Ice
There is a more general property here:
Theorem.
Let A(pb,pg,L) be the set of ASMs with blue
pairing pb, green pairing pg, and total number
of cycles L. If p/b is pb rotated clockwise and
p/g is pg rotated anticlockwise, then the sets
A(pb,pg,L) and A(p/b,p/g,L) are in bijection.
We will construct this bijection in stages.
Square Ice
The parity of a square in the graph is the
parity of its lower left or upper right vertex.
We refer
Here
and
here
are to
the
area 1-squares…
the
square
0-squares.
of parity k as a
k-square.
Square Ice
Call a square alternating if its 4 sides
alternate in color around the square.
Here are the alternating squares.
Square Ice
Call a vertex k-fixed if its incident blue edges
are on different k-squares.
These are the 1-fixed vertices.
Square Ice
Call a vertex k-fixed if its incident blue edges
are on different k-squares.
These are the 0-fixed vertices.
Square Ice
Define functions Gk which switch the edgecolors of all alternating k-squares.
Then define Hk = Gk O R where R switches
the color of every edge in the graph.
Finally, define the function G = H0 O H1 which
is our desired bijection!
Square Ice
What needs to be shown?
• The functions Hk send paths to paths and
cycles to cycles.
Method: Show that k-fixed vertices are kfixed and connected before and after Hk.
Determine what happens on the edges of
the graph to paths after Hk. Characterize
paths and cycles by their k-fixed vertices.
Square Ice
What needs to be shown?
• Show that the total number of cycles is
unchanged.
• The blue pairing rotates clockwise and the
green pairing rotates anticlockwise.
• Show bijectivity of G.
Square Ice
• Finally, reflection over the line y = x
composed with either Hk will rotate pairings
and preserve the total number of cycles.
• Conclude that D2n is a symmetry group on
ASMs.
Now a large example…
0 0

0 0
0 0

0 0
0 1

0 0

0 0
 1 1

0 0
0 0

0 0
0 0

0 1

0 0
0 0

0
0 0

0
0
0
0
0
0
0
0
0
1 0 0
0
0
0
0
0
0
1
0
0
0 0 0

0
0
0
0
0
1 1 1
0 1 0 1 
0
0 1 1
0 1 1 1 0
1 0 0 
1
0
0
0
0
0 1 1
0
0 0 0

0
0
0
0
0
0
1
0
0
0 0 0
0
1 0
1 1 1
0
0
0
0 1 1 0

0
0
0
1
0
0
0
0
0
0 0 0
1
0
0
0 1 1
0 1 1
0 0 0

0
0
0
0
1
0
0
0 1 1 0 0
0
1
0
0
0 1 0
0
1
0 0 0

0 1 0
0
0
1 1 1
0
0 0 0

0
1
0
0 1 0
1
0
0
0 0 0
0
0
0
0
1
0
0
0
0
0 0 0 
0
0
1
0
0
0
0
0
0
0
• Take a 15-by-15
ASM and look at its blue
0
0
subgraph.
0
0
• Consider
a path and see how the functions
0
0
H1 and H
preserve the 1- and 0-vertices.
1
• Repeat 0for the green subgraph.
0
0
0
0
0
0
Blue subgraph after H01
The
1-vertices
0-vertices
Green subgraph after H01
The
1-vertices
0-vertices
Another problem…
Recall: An integer partition is a way to write
a positive integer as a sum of other positive
integers.
Example: The number 4 can be written as
4, 3+1, 2+2, 2+1+1, and 1+1+1+1.
This can be shown with a diagram…
Another problem…
One method is by using Young Tableaux.
Here are the partitions of the number 4.
Another problem…
Mathematicians Percival MacMahon, Basil
Gordon, Donald Knuth, and others researched
a 3-D generalization of integer partitions.
Enter: Plane partitions
A plane partition is an assemblage of unit
cubes pushed into a corner.
Another problem…
A plane partition of 11 cubes:
Another problem…
But the most famous plane partition of all:
Another problem…
A descending plane partition of order n is
a 2-dimensional array of positive integers
less than or equal to n such that the lefthand edges are successively indented, there
is weak decrease across rows and strict
decrease down columns, and the number of
entries in a row is strictly less than the
largest entry in that row.
Another problem…
An example of a descending plane partition:
66643
33
2
Another problem…
Theorem:
The number of descending plane partitions
with largest part less than or equal to r
equals the number of n-by-n ASMs.
Even more problems!
More counting problems are tied up in
counting ASMs.
Example: Jig saw puzzles
(see the poster)
Conclusion
For people who like to count, ASMs are
where it’s at.
References
• The book Proofs and Confirmations by
David Bressoud
• How the Alternating Sign Matrix Conjecture
Was Solved, by James Propp
• A Large Dihedral Symmetry of the Set of
Alternating Sign Matrices, by Benjamin
Wieland
Thank You