Fully packed loops

AUTHORS:

  • Vincent Knight, James Campbell, Kevin Dilks, Emily Gunawan (2015): Initial version
  • Vincent Delecroix (2017): cleaning and enhanced plotting function
sage.combinat.fully_packed_loop.FullyPackedLoop

A class for fully packed loops.

A fully packed loop is a collection of non-intersecting lattice paths on a square grid such that every vertex is part of some path, and the paths are either closed internal loops or have endpoints corresponding to alternate points on the boundary [Propp2001]. They are known to be in bijection with alternating sign matrices.

To each fully packed loop, we assign a link pattern, which is the non-crossing matching attained by seeing which points on the boundary are connected by open paths in the fully packed loop.

We can create a fully packed loop using the corresponding alternating sign matrix and also extract the link pattern:

sage: A = AlternatingSignMatrix([[0, 0, 1], [0, 1, 0], [1, 0, 0]])
sage: fpl = FullyPackedLoop(A)
sage: fpl.link_pattern()
[(1, 4), (2, 3), (5, 6)]
sage: fpl
        |         |
        |         |
        + -- +    +
             |    |
             |    |
     -- +    +    + --
        |    |
        |    |
        +    + -- +
        |         |
        |         |
sage: B = AlternatingSignMatrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
sage: fplb = FullyPackedLoop(B)
sage: fplb.link_pattern()
[(1, 6), (2, 5), (3, 4)]
sage: fplb
        |         |
        |         |
        +    + -- +
        |    |
        |    |
     -- +    +    + --
             |    |
             |    |
        + -- +    +
        |         |
        |         |

The class also has a plot method:

sage: fpl.plot()
Graphics object consisting of 3 graphics primitives

which gives:

../../_images/fully_packed_loop-1.png

Note that we can also create a fully packed loop from a six vertex model configuration:

sage: S = SixVertexModel(3, boundary_conditions='ice').from_alternating_sign_matrix(A)
sage: S
    ^    ^    ^
    |    |    |
--> # -> # -> # <--
    ^    ^    |
    |    |    V
--> # -> # <- # <--
    ^    |    |
    |    V    V
--> # <- # <- # <--
    |    |    |
    V    V    V
sage: fpl = FullyPackedLoop(S)
sage: fpl
    |         |
    |         |
    + -- +    +
         |    |
         |    |
 -- +    +    + --
    |    |
    |    |
    +    + -- +
    |         |
    |         |

Once we have a fully packed loop we can obtain the corresponding alternating sign matrix:

sage: fpl.to_alternating_sign_matrix()
[0 0 1]
[0 1 0]
[1 0 0]

Here are some more examples using bigger ASMs:

sage: A = AlternatingSignMatrix([[0,1,0,0],[0,0,1,0],[1,-1,0,1],[0,1,0,0]])
sage: S = SixVertexModel(4, boundary_conditions='ice').from_alternating_sign_matrix(A)
sage: fpl = FullyPackedLoop(S)
sage: fpl.link_pattern()
[(1, 2), (3, 6), (4, 5), (7, 8)]
sage: fpl
    |         |
    |         |
    + -- + -- +    + --
                   |
                   |
 -- +    + -- + -- +
    |    |
    |    |
    +    +    + -- + --
    |    |    |
    |    |    |
 -- +    +    + -- +
         |         |
         |         |

sage: m = AlternatingSignMatrix([[0,0,1,0,0,0],
....:                            [1,0,-1,0,1,0],
....:                            [0,0,0,1,0,0],
....:                            [0,1,0,0,-1,1],
....:                            [0,0,0,0,1,0],
....:                            [0,0,1,0,0,0]])
sage: fpl = FullyPackedLoop(m)
sage: fpl.link_pattern()
[(1, 12), (2, 7), (3, 4), (5, 6), (8, 9), (10, 11)]
sage: fpl
    |         |         |
    |         |         |
    + -- +    +    + -- +    + --
         |    |    |         |
         |    |    |         |
 -- + -- +    +    + -- + -- +
              |
              |
    + -- +    + -- + -- +    + --
    |    |              |    |
    |    |              |    |
 -- +    +    + -- +    +    +
         |    |    |    |    |
         |    |    |    |    |
    + -- +    + -- +    +    + --
    |                   |
    |                   |
 -- +    + -- + -- +    + -- +
         |         |         |
         |         |         |

sage: m = AlternatingSignMatrix([[0,1,0,0,0,0,0],
....:                            [1,-1,0,0,1,0,0],
....:                            [0,0,0,1,0,0,0],
....:                            [0,1,0,0,-1,1,0],
....:                            [0,0,0,0,1,0,0],
....:                            [0,0,1,0,-1,0,1],
....:                            [0,0,0,0,1,0,0]])
sage: fpl = FullyPackedLoop(m)
sage: fpl.link_pattern()
[(1, 2), (3, 4), (5, 6), (7, 8), (9, 14), (10, 11), (12, 13)]
sage: fpl
    |         |         |         |
    |         |         |         |
    + -- + -- +    + -- +    + -- +
                   |         |
                   |         |
 -- + -- + -- +    + -- + -- +    + --
              |                   |
              |                   |
    + -- +    + -- + -- +    + -- +
    |    |              |    |
    |    |              |    |
 -- +    +    + -- +    +    +    + --
         |    |    |    |    |    |
         |    |    |    |    |    |
    + -- +    + -- +    +    + -- +
    |                   |
    |                   |
 -- +    + -- + -- +    +    + -- + --
         |         |    |    |
         |         |    |    |
    + -- +    + -- +    +    + -- +
    |         |         |         |
    |         |         |         |

Gyration on an alternating sign matrix/fully packed loop fpl of the link pattern corresponding to fpl:

sage: ASMs = AlternatingSignMatrices(3).list()
sage: ncp = FullyPackedLoop(ASMs[1]).link_pattern() # fpl's gyration orbit size is 2
sage: rotated_ncp=[]
sage: for (a,b) in ncp:
....:     for i in range(0,5):
....:         a,b=a%6+1,b%6+1;
....:     rotated_ncp.append((a,b))
sage: PerfectMatching(ASMs[1].gyration().to_fully_packed_loop().link_pattern()) ==\
....:     PerfectMatching(rotated_ncp)
True

sage: fpl = FullyPackedLoop(ASMs[0])
sage: ncp = fpl.link_pattern() # fpl's gyration size is 3
sage: rotated_ncp=[]
sage: for (a,b) in ncp:
....:     for i in range(0,5):
....:         a,b=a%6+1,b%6+1;
....:     rotated_ncp.append((a,b))
sage: PerfectMatching(ASMs[0].gyration().to_fully_packed_loop().link_pattern()) ==\
....:     PerfectMatching(rotated_ncp)
True

sage: mat = AlternatingSignMatrix([[0,0,1,0,0,0,0],[1,0,-1,0,1,0,0],
....:     [0,0,1,0,0,0,0],[0,1,-1,0,0,1,0],[0,0,1,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,1]])
sage: fpl = FullyPackedLoop(mat) # n=7
sage: ncp = fpl.link_pattern()
sage: rotated_ncp=[]
sage: for (a,b) in ncp:
....:     for i in range(0,13):
....:         a,b=a%14+1,b%14+1;
....:     rotated_ncp.append((a,b))
sage: PerfectMatching(mat.gyration().to_fully_packed_loop().link_pattern()) ==\
....:     PerfectMatching(rotated_ncp)
True

sage: mat = AlternatingSignMatrix([[0,0,0,1,0,0], [0,0,1,-1,1,0],
....:     [0,1,0,0,-1,1], [1,0,-1,1,0,0], [0,0,1,0,0,0], [0,0,0,0,1,0]])
sage: fpl = FullyPackedLoop(mat) # n =6
sage: ncp = fpl.link_pattern()
sage: rotated_ncp=[]
sage: for (a,b) in ncp:
....:     for i in range(0,11):
....:         a,b=a%12+1,b%12+1;
....:     rotated_ncp.append((a,b))
sage: PerfectMatching(mat.gyration().to_fully_packed_loop().link_pattern()) ==\
....:     PerfectMatching(rotated_ncp)
True

More examples:

We can initiate a fully packed loop using an alternating sign matrix::

    sage: A = AlternatingSignMatrix([[0, 0, 1], [0, 1, 0], [1, 0, 0]])
    sage: fpl = FullyPackedLoop(A)
    sage: fpl
        |         |
        |         |
        + -- +    +
             |    |
             |    |
     -- +    +    + --
        |    |
        |    |
        +    + -- +
        |         |
        |         |
    sage: FullyPackedLoops(3)(A) == fpl
    True

We can also input a matrix::

    sage: FullyPackedLoop([[0, 0, 1], [0, 1, 0], [1, 0, 0]])
        |         |
        |         |
        + -- +    +
             |    |
             |    |
     -- +    +    + --
        |    |
        |    |
        +    + -- +
        |         |
        |         |
    sage: FullyPackedLoop([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) ==\
    ....: FullyPackedLoops(3)([[0, 0, 1], [0, 1, 0], [1, 0, 0]])
    True

Otherwise we initiate a fully packed loop using a six vertex model::

    sage: S = SixVertexModel(3, boundary_conditions='ice').from_alternating_sign_matrix(A)
    sage: fpl = FullyPackedLoop(S)
    sage: fpl
        |         |
        |         |
        + -- +    +
             |    |
             |    |
     -- +    +    + --
        |    |
        |    |
        +    + -- +
        |         |
        |         |

    sage: FullyPackedLoops(3)(S) == FullyPackedLoop(S)
    True

    sage: fpl.six_vertex_model().to_alternating_sign_matrix()
    [0 0 1]
    [0 1 0]
    [1 0 0]

We can also input the matrix associated to a six vertex model::

    sage: SixVertexModel(2)([[3,1],[5,3]])
        ^    ^
        |    |
    --> # <- # <--
        |    ^
        V    |
    --> # -> # <--
        |    |
        V    V

    sage: FullyPackedLoop([[3,1],[5,3]])
        |
        |
        +    + --
        |    |
        |    |
     -- +    +
             |
             |

    sage: FullyPackedLoops(2)([[3,1],[5,3]]) == FullyPackedLoop([[3,1],[5,3]])
    True

Note that the matrix corresponding to a six vertex model without
the ice boundary condition is not allowed::

    sage: SixVertexModel(2)([[3,1],[5,5]])
        ^    ^
        |    |
    --> # <- # <--
        |    ^
        V    V
    --> # -> # -->
        |    |
        V    V

    sage: FullyPackedLoop([[3,1],[5,5]])
    Traceback (most recent call last):
    ...
    ValueError: invalid alternating sign matrix

    sage: FullyPackedLoops(2)([[3,1],[5,5]])
    Traceback (most recent call last):
    ...
    ValueError: invalid alternating sign matrix

Note that if anything else is used to generate the fully packed loop an error will occur::

    sage: fpl = FullyPackedLoop(5)
    Traceback (most recent call last):
    ...
    ValueError: invalid alternating sign matrix

    sage: fpl = FullyPackedLoop((1, 2, 3))
    Traceback (most recent call last):
    ...
    ValueError: The alternating sign matrices must be square

    sage: SVM = SixVertexModel(3)[0]
    sage: FullyPackedLoop(SVM)
    Traceback (most recent call last):
    ...
    ValueError: invalid alternating sign matrix

REFERENCES:

[Propp2001]James Propp. The Many Faces of Alternating Sign Matrices, Discrete Mathematics and Theoretical Computer Science 43 (2001): 58 Arxiv math/0208125
[Striker2015]Jessica Striker. The toggle group, homomesy, and the Razumov-Stroganov correspondence, Electron. J. Combin. 22 (2015) no. 2 Arxiv 1503.08898
sage.combinat.fully_packed_loop.FullyPackedLoops

Class of all fully packed loops on an \(n \times n\) grid.

They are known to be in bijection with alternating sign matrices.

INPUT:

  • n – the number of row (and column) or grid

EXAMPLES:

This will create an instance to manipulate the fully packed loops of size 3:

sage: FPLs = FullyPackedLoops(3)
sage: FPLs
Fully packed loops on a 3x3 grid
sage: FPLs.cardinality()
7

When using the square ice model, it is known that the number of configurations is equal to the number of alternating sign matrices:

sage: M = FullyPackedLoops(1)
sage: len(M)
1
sage: M = FullyPackedLoops(4)
sage: len(M)
42
sage: all(len(SixVertexModel(n, boundary_conditions='ice'))
....:     == FullyPackedLoops(n).cardinality() for n in range(1, 7))
True