demo_tsscpp_tools.sagews

Demonstration of tsscpp_tools.sage

This notebook demonstrates various functions from the library tsscpp_tools.sage, which contains tools for:

1. Encoding a TSSCPP (written as a "bird's-eye-view" matrix) as a TSSCPP array, as desribed in Section 6.2 of David M. Bressoud's book "Proofs and Confirmations"

2. Reconstructing the bird's-eye view matrix of a TSSCPP from its TSSCPP array

3. Plotting a TSSCPP as a collection of boxes (formally, a lozenge tiling in two dimensions)

4. Plotting the nest of non-intersecting lattice paths (NILP's) corresponding to a TSSCPP

As an extra, this library also includes:

5. A tool for creating the power set $\mathscr P(S)$ of a set $S$

load('tsscpp_tools.sage')
print('Load successful')

Load successful

Conversion Between TSSCPP Arrays, Bird's-Eye-View Matrices, and NILP's

Functions included:

• array_to_tsscpp

• tsscpp_to_array

• plot_tsscpp

• array_to_nilp

A = Matrix(ZZ, [[13,5,1,0,0,0,0],
                [0,11,7,5,0,0,0],
                [0,0,9,5,0,0,0],
                [0,0,0,7,0,0,0],
                [0,0,0,0,5,0,0],
                [0,0,0,0,0,3,0],
                [0,0,0,0,0,0,1]])

print("The encoded TSSCPP is:")
show(A)

M = array_to_tsscpp(A)
print("The bird's-eye view of the TSSCPP encoded above is:")
show(M)

A_new = tsscpp_to_array(M)
print("Re-encoding the TSSCPP:")
show(A_new)

print("Illustration of the TSSCPP:")
plot_tsscpp(M)

N = array_to_nilp(A)
print("The corresponding nest of NILP's:")
show(N)

The encoded TSSCPP is:

$\displaystyle \left(\begin{array}{rrrrrrr} 13 & 5 & 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 7 & 5 & 0 & 0 & 0 \\ 0 & 0 & 9 & 5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 7 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$

The bird's-eye view of the TSSCPP encoded above is:

$\displaystyle \left(\begin{array}{rrrrrrrrrrrrrr} 14 & 14 & 14 & 14 & 14 & 14 & 14 & 13 & 13 & 13 & 12 & 11 & 10 & 7 \\ 14 & 14 & 14 & 14 & 13 & 13 & 13 & 12 & 10 & 10 & 8 & 8 & 7 & 4 \\ 14 & 14 & 14 & 13 & 13 & 13 & 12 & 11 & 10 & 10 & 8 & 7 & 6 & 3 \\ 14 & 14 & 13 & 13 & 13 & 13 & 11 & 10 & 10 & 10 & 7 & 6 & 6 & 2 \\ 14 & 13 & 13 & 13 & 10 & 10 & 10 & 9 & 9 & 7 & 4 & 4 & 4 & 1 \\ 14 & 13 & 13 & 13 & 10 & 9 & 9 & 8 & 7 & 5 & 4 & 4 & 4 & 1 \\ 14 & 13 & 12 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ 13 & 12 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ 13 & 10 & 10 & 10 & 9 & 7 & 6 & 5 & 5 & 4 & 1 & 1 & 1 & 0 \\ 13 & 10 & 10 & 10 & 7 & 5 & 5 & 4 & 4 & 4 & 1 & 1 & 1 & 0 \\ 12 & 8 & 8 & 7 & 4 & 4 & 4 & 3 & 1 & 1 & 1 & 1 & 0 & 0 \\ 11 & 8 & 7 & 6 & 4 & 4 & 3 & 2 & 1 & 1 & 1 & 0 & 0 & 0 \\ 10 & 7 & 6 & 6 & 4 & 4 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 7 & 4 & 3 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right)$

Re-encoding the TSSCPP:

$\displaystyle \left(\begin{array}{rrrrrrr} 13 & 5 & 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 7 & 5 & 0 & 0 & 0 \\ 0 & 0 & 9 & 5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 7 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$

Illustration of the TSSCPP:

The corresponding nest of NILP's:

Colors in Plotting Commands

The commands plot_tsscpp and array_to_nilp both contain optional arguments for colors. The former takes three optional arguments; the latter takes one.

A = Matrix([[5,3,0], [0,3,1], [0,0,1]])

plot_tsscpp(array_to_tsscpp(A), color_1='plum', color_2='khaki', color_3='mediumaquamarine')
array_to_nilp(A, line_color='red')

Extra Tool: powerset_ordered

Alternative implementation of powerset (see here for documentation) that orders the subsets of $\{ 1, 2, \dotsc, n \}$ first according to size, then according to the dictionary ordering among subsets of the same size. For example, the power set of $\{ 1, 2, 3 \}$ would be given by a list containing $$\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$$

P = powerset_ordered([1,2,3,4])
print(P)

P.reverse()
print(P)

[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]] [[1, 2, 3, 4], [2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3], [3, 4], [2, 4], [2, 3], [1, 4], [1, 3], [1, 2], [4], [3], [2], [1], []]

Creating All TSSCPP's of a Given Order

The function make_all_tsscpp_arrays creates a list containing all TSSCPP's of a given order $n$, encoded as TSSCPP arrays.

n = 4
L = make_all_tsscpp_arrays(n)
num_to_show = 10

print("There are {0} TSSCPP's of order {1}; here are the first {2}:".format(len(L), n, num_to_show))

for ii in [0 .. num_to_show - 1]:
    A = L[ii]
    M = array_to_tsscpp(A)
    plot_tsscpp(M)

    N = array_to_nilp(A)
    N.show()
    print('\n')

There are 42 TSSCPP's of order 4; here are the first 10: