Alternating Sign Matrices through X-Rays

Martin Rubey^{1} Fakultät für Mathematik und Geoinformation TU Wien Austria

                   martin.rubey@tuwien.ac.at

Abstract

We exhibit a bijection between Dyck paths and alternating sign matrices which are determined by their antidiagonal sums.

1 Introduction

A fundamental question in discrete tomography is whether a binary image can be reconstructed from a small number of projections. As a special case, one might restrict attention to permutation matrices and try to determine which vectors of antidiagonal sums appear only once. This problem, considered by Bebeacua, Mansour, Postnikov, and Severini [1], is apparently still open. The number of such vectors is recorded in the sequence \underline{A289971} in the On-Line Encyclopedia of Integer Sequences [3].

In this note, we consider the analogous problem for alternating sign matrices. An alternating sign matrix is a square matrix of 0s, 1s and −1s such that the sum of the entries in each row and each column is 1, and the nonzero entries in each row and in each column alternate in sign. For an n × n-alternating sign matrix A, the k-th (antidiagonal) sum is x_{k} = ∑_{i+j=k+1} A_{i,j} and the (antidiagonal) X-ray is the vector (x_{1}, …, x_{2n−1}). For example, the alternating sign matrices of size three together with their X-rays are as follows:

\begin{matrix}(\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) & (\begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) & (\begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) & (\begin{matrix}0 & 1 & 0 \\ 1 & −1 & 1 \\ 0 & 1 & 0 \end{matrix}) & (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}) & (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) & (\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) \\ (1, 0, 1, 0, 1) & (0, 2, 0, 0, 1) & (1, 0, 0, 2, 0) & (0, 2, −1, 2, 0) & (0, 0, 3, 0, 0) & (0, 1, 1, 1, 0) & (0, 1, 1, 1, 0) \end{matrix}

1Supported by the Austrian Science Fund (FWF): P 29275.

Note that all X-rays except (0, 1, 1, 1, 0) occur precisely once. Thus, there are five alternating sign matrices determined by their X-rays. We can now state our main result:

Theorem 1. There is an explicit bijection between Dyck paths of semilength n and n × nalternating sign matrices which are determined by their X-rays.

We recall that the number of Dyck paths of semilength n equals the n-th Catalan number \frac{1}{n+1} \binom{2n}{n}, recorded as \underline{A000108}. We note that, although there is also a nice formula for the total number of size n alternating sign matrices, ∏_{k=0}^{n−1} \frac{(3k+1)!}{(n+k)!}, recorded as \underline{A005130}, it is much harder to prove this.

The coincidence described by the theorem was observed when submitting the statistic www.findstat.org/St000889, which counts the number of alternating sign matrices with the same X-rays, to the online database of combinatorial statistics FindStat [2], and looking at the linear terms of the first few generating functions automatically produced there. We currently have no explanation for any of the other terms in the distribution.

2 The bijection

We define an injective map A from Dyck paths to alternating sign matrices as follows, see Figure 1 for an example. For more visual clarity in the pictures, we sometimes use (+)s and (−)s instead of 1s and −1s and omit 0s.

• Draw the Dyck path in an n × n square, beginning in the top left corner, taking unit east and unit south steps and terminating in the bottom right corner, never going below the main diagonal of the matrix.

• Add the reflection through the main diagonal of the Dyck path to the picture.

• For each peak of the Dyck path, fill the cells lying between the peak and its mirror image on the antidiagonal with 1s.

• For each valley of the Dyck path, fill the cells lying between the valley and its mirror image on the antidiagonal with −1s.

• Fill the remaining cells with 0s.

In the remaining two sections we show that the image of the map A consists precisely of those alternating sign matrices which are determined by their X-ray, thus proving Theorem 1.

3 A map on diagonally symmetric alternating sign matrices

In this section we show that any alternating sign matrix which is uniquely determined by its X-ray is in the image of A.

\begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}  \begin{matrix}+ \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ − \\ − \\ − \\ − \\ − \\ − \\ − \\ − \\ − \end{matrix}

Figure 1: The image of a Dyck path

Because transposing a matrix preserves the X-ray, only diagonally symmetric alternating sign matrices may be reconstructible from their X-ray. We now present a map M on diagonally symmetric alternating sign matrices that preserves the X-ray and is the identity precisely on the matrices in the image of the map A from the previous section.

These two properties lead to the desired result: suppose that A is determined by its X-ray. Since the X-rays of A and M(A) are the same, M(A) is also determined by its X-ray, and equals A.

Let A be a diagonally symmetric alternating sign matrix. Then the matrix M(A) is obtained as follows. See Figure 2 for an example.

• Imagine a sun in the north-east, such that the 1s in A cast shadows, and trace out a Dyck path by following the shadow line. This path is indicated in solid black in Figure 2.

• Consider the entries of A which are strictly south-west of the entries just below the Dyck path. In Figure 2, these are the entries in the shaded region. Reflect these entries through the subdiagonal of the matrix.

• Into each cell just south-west of a valley of the Dyck path which is not on the subdiagonal and which contains a 0, place a −1, and place a 1 in the cell reflected through the subdiagonal.

Although not used subsequently, we note that the Dyck path constructed in the first step returns to the main diagonal exactly once for each direct summand of A, when regarding A as a block diagonal matrix. Thus, the map M is such that it can be applied to each direct summand of A individually.

Lemma 2. The map M, applied to a diagonally symmetric alternating sign matrix, produces an alternating sign matrix.

Proof. Let A be a diagonally symmetric alternating sign matrix. Let us call the region in A which is symmetric with respect to the subdiagonal and whose south-west border is the reflected Dyck path, the shade of A. This is the shaded region in Figure 2. Consider a column

\begin{matrix}+ \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ − \\ − \\ − \\ − \\ − \end{matrix}  ↦ \begin{matrix}+ \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ − \\ − \\ − \\ − \\ − \end{matrix}  ↦ \begin{matrix}+ \\ − \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ + \\ − \\ − \\ − \\ − \\ − \end{matrix}

Figure 2: A diagonally symmetric alternating sign matrix and its image

c of A, and its reflection r through the subdiagonal. Thus, when c is the first column, r is the second row of A.

Suppose first that the topmost nonzero entry of c and the rightmost nonzero entry of r within the shade of A are both 1. This is the case when c (or r) does not contain a peak of the Dyck path, or the valley below (or to the left of) the peak contains a −1. In this case, column c and row r of M(A) satisfy the alternating sign matrix conditions, since the bottommost nonzero entry of any column and the leftmost nonzero entry of any row of A is within the shade and equals 1.

Let us now consider the second scenario, where the topmost nonzero entry of c within the shade of the original matrix A is −1. In the example of Figure 2 this happens in the sixth column. In this case, the Dyck path must have a peak in this column. Let v be the cell just south-west of the valley below the peak. Note that v must contain a 0. The cell v must be strictly above the diagonal, because otherwise the reflection of the −1 below it through the main diagonal would lie on or above the Dyck path. Thus, by definition of M, we place a −1 into the cell v. The effect of this is that column c of M(A) is alternating.

Furthermore, we place a 1 in the cell v′ corresponding to v reflected through the subdiagonal. This satisfies the alternating sign matrix conditions, because after reflecting through the subdiagonal the row containing v′ has a −1 as its leftmost nonzero entry.

Lemma 3. The map M, applied to a diagonally symmetric alternating sign matrix A, is the identity if and only if A is in the image of A.

Proof. If A is in the image of A, the shade of A is symmetric. Moreover, the cells just southwest of the valleys which are above the subdiagonal all contain −1s. Thus, M(A) = A.

Otherwise, since A is symmetric, and the shade of A is reflected through the subdiagonal, M(A) cannot be symmetric.

4 Reconstructing the alternating sign matrix

To complete the proof of Theorem 1, we have to show the following:

Lemma 4. The X-ray corresponding to an alternating sign matrix in the image of A determines the matrix unambiguously.

Proof. Consider the antidiagonal sums beginning at the north-west corner. Suppose that the entries of the first k antidiagonals are uniquely determined by the first k entries x_{1}, x_{2}, …, x_{k} of the X-ray, and suppose that x_{k} ≠ 0, x_{k+1} = ⋯ = x_{ℓ−1} = 0 and x_{ℓ} ≠ 0.

For simplicity, assume that x_{k} > 0. By hypothesis, the alternating sign matrix then has the following form:

\begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ −1 \\ −1 \\ −1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}

Let us first note that there cannot be any nonzero entries on the antidiagonals k + 1, …, ℓ − 1. According to our assumption, all these have sum zero. Suppose for the sake of contradiction that there is such an antidiagonal and consider the first of these. Because every row and every column of an alternating sign matrix must begin with a 1, this antidiagonal can have −1s only in the triangular region south-east of the sequence of 1s in the k-th antidiagonal - shaded grey in the example above. However, there cannot be any 1s on the same antidiagonal, necessarily outside of this triangular region: any such 1 below the main diagonal would be followed by another 1 in the same column above it.

We now distinguish two cases: if x_{ℓ} < 0, since the matrix is in the image of A, the ℓ-th antidiagonal intersects the triangular region defined above and all cells of the antidiagonal within this region are filled with −1s. Thus, in this case the entries on the ℓ-th antidiagonal are also uniquely determined by the antidiagonal sum.

On the other hand, if x_{ℓ} > 0, since the matrix is in the image of A, the ℓ-th antidiagonal intersects the triangular region which is dotted and shaded red in the example. In this case, all cells of the antidiagonal within this region are filled with 1s. Since there cannot be any 1s on the same antidiagonal outside of the red triangular region, also in this case the entries of the ℓ-th antidiagonal are uniquely determined by their sum.

References

[1] C. Bebeacua, T. Mansour, A. Postnikov, and S. Severini, On the X-rays of permutations, in Proceedings of the Workshop on Discrete Tomography and its Applications, Electron. Notes Discrete Math. 20 (2005), 193–203. Available at

   https://arxiv.org/abs/math/0506334.

[2] M. Rubey, C. Stump, et al., FindStat—The combinatorial statistics database,

   https://www.FindStat.org.

[3] N. J. A. Sloane et al. The On-Line Encyclopedia of Integer Sequences, 2021. Available

   at https://oeis.org.

2010 Mathematics Subject Classification: Primary 05A19. Keywords: bijective combinatorics, combinatorial statistic, Dyck path, alternating sign matrix.

(Concerned with sequences \underline{A000108}, \underline{A005130}, and \underline{A289971}.)

Received December 14 2020; revised versions received April 22 2021; April 28 2021. Published in Journal of Integer Sequences, May 19 2021.

Return to Journal of Integer Sequences home page.