Tutorial

We will consider the following problem.

Problem

An Alternating Sign Matrix (ASM) of size \(n\) is a square matrix with entries: \(0, 1\) or \(-1\) such that:

• The sum of all rows and columns is 1.

• The non zero entries in each row and column alternate in sign.

For example there are 7 alternating sign matrices of size \(n=3\)

\[\begin{split} \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{pmatrix} \qquad \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0\\ \end{pmatrix} \end{split}\]

\[\begin{split} \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0\\ \end{pmatrix} \qquad \begin{pmatrix} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{pmatrix} \end{split}\]

\[\begin{split} \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\\ \end{pmatrix} \qquad \begin{pmatrix} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\ \end{pmatrix} \end{split}\]

\[\begin{split} \begin{pmatrix} 0 & 1 & 0\\ 1 & -1 & 1\\ 0 & 1 & 0\\ \end{pmatrix} \end{split}\]

The number of Alternating Sign Matrices of size \(n\) is given by the following formula [Bressoud, 1999]:

\[ A_n = \prod_{i=0}^{n-1}\frac{(3i+1)!}{(n + i)!} \]

The file available at 10.5281/zenodo.11121413 is believed to contain the number \(A_n\) for \(1\leq n\leq 20\).

1. Confirm that the values in the file are correct.

2. Create a new file with the values of \(A_n\) for \(1\leq n \leq 500\).

First let us write a function to generate \(A_n\) from the formula:

import sympy as sym

def get_A_n(n):
    """
    Return the number of Alternating Sign Matrices of size n as given by

    A_n = \prod_{i=0}^{n-1}\frac{(3i+1)!}{(n + i)!}

    Parameters
    ----------
    n : int
        The size

    Returns
    -------
    int
        The number of Alternating Sign Matrices
    """
    return sym.prod(sym.factorial(3 * i + 1) / sym.factorial(n + i) for i in range(n))

Note that we choose to use sympy here to handle the integer division without any numeric approximation.

Let us confirm the number of \(n=3\):

get_A_n(n=3)

\[\displaystyle 7\]

Next, let us read the data file after downloading it:

with open("main.txt", "r") as f:
    data_as_string = f.read()

This reads the contents of the data file as a string:

data_as_string

'1\n2\n7\n42\n429\n7436\n218348\n10850216\n911835460\n129534272700\n31095744852375\n12611311859677500\n8639383518297652500\n9995541355448167482000\n19529076234661277104897200\n64427185703425689356896743840\n358869201916137601447486156417296\n3374860639258750562269514491522925456\n53580350833984348888878646149709092313244\n1436038934715538200913155682637051204376827212'

Note the \n character which indicates a line break. We can create a list from this string by splitting on that character:

data_as_strings_as_list = data_as_string.split("\n")
data_as_strings_as_list

['1',
 '2',
 '7',
 '42',
 '429',
 '7436',
 '218348',
 '10850216',
 '911835460',
 '129534272700',
 '31095744852375',
 '12611311859677500',
 '8639383518297652500',
 '9995541355448167482000',
 '19529076234661277104897200',
 '64427185703425689356896743840',
 '358869201916137601447486156417296',
 '3374860639258750562269514491522925456',
 '53580350833984348888878646149709092313244',
 '1436038934715538200913155682637051204376827212']

Finally we create a list by converting each substring to an int.

data = [int(item) for item in data_as_strings_as_list]
data

[1,
 2,
 7,
 42,
 429,
 7436,
 218348,
 10850216,
 911835460,
 129534272700,
 31095744852375,
 12611311859677500,
 8639383518297652500,
 9995541355448167482000,
 19529076234661277104897200,
 64427185703425689356896743840,
 358869201916137601447486156417296,
 3374860639258750562269514491522925456,
 53580350833984348888878646149709092313244,
 1436038934715538200913155682637051204376827212]

First let us confirm that the data is correct.

check = all(get_A_n(n=i + 1) == value for i, value in enumerate(data))
check

True

Now, let us write a new file with \(A_n\) for \(1\leq n \leq 200\):

with open("data.txt", "w") as f:
    for n in range(1, 101):
        A_n = get_A_n(n=n)
        f.write(f"{A_n}\n")

Important

In this chapter we have:

• Read information stored in a file.

• Write information to a file.