Completions of Alternating Sign Matrices

Abstract

We consider the problem of completing a $(0,-1)$-matrix to an alternating sign matrix (ASM) by replacing some $0$s with $-1$s. An algorithm can be given to determine a completion or show that one does not exist. We are concerned primarily with bordered-permutation $(0,-1)$ matrices, defined to be $n\times n$ $(0,-1)$-matrices with only $0$s in their first and last rows and columns where the $-1$s form an $(n-2)\times (n-2)$ permutation matrix. We show that any such matrix can be completed to an ASM and characterize those that have a unique completion.

1 Introduction

An alternating sign matrix, abbreviated ASM, is an $n\times n$ $(0,+1,-1)$-matrix such that, ignoring $0$s, in each row and column, the $+1$s and $-1$s alternate, beginning and ending with a $+1$. The history of ASMs and connections of ASMs to partitions, tilings, and statistical physics can be found in the book [1] by Bressoud. A connections between ASMs and polynomiography is described in [4]. A recent investigation of the zero-nonzero patterns of ASMs can be found in [2]. Some of the basic properties of ASMs, following immediately from definition, are that each row and column contains an odd number of nonzeros with the first and last rows and columns each containing exactly one nonzero and that nonzero is a $+1$. Also if an ASM (regarded as a square) is subjected to any of the symmetries of a square (the dihedral group), the result is also an ASM. Permutation matrices are ASMs. Other examples of ASMs are

$$\begin{aligned} \left[ \begin{array}{c|c|c|c|c|c} &{}&{}+1&{}&{}&{}\\ \hline &{}+1&{}-1&{}&{}+1&{}\\ \hline &{}&{}&{}+1&{}-1&{}+1\\ \hline +1&{}-1&{}&{}&{}+1&{}\\ \hline &{}+1&{}&{}&{}&{}\\ \hline &{}&{}+1&{}&{}&{}\end{array}\right] \hbox { and }\ \left[ \begin{array}{c|c|c|c|c|c} &{}&{}&{}+1&{}&{}\\ \hline &{}&{}+1&{}-1&{}+1&{}\\ \hline &{}+1&{}-1&{}+1&{}-1&{}+1\\ \hline +1&{}-1&{}+1&{}-1&{}+1&{}\\ \hline &{}+1&{}-1&{}+1&{}&{}\\ \hline &{}&{}+1&{}&{}&{}\end{array}\right] . \end{aligned}$$

(For visual clarity, we usually block off rows and columns and then suppress the 0s in $(0,+1,-1)$-matrices).

In this paper we are concerned with the completions of $n\times n$ $(0,+1,-1)$-matrices to ASMs. In general, by a completion we mean the following: Given an $n \times n$ $(0,+1,-1)$ matrix $A$, any matrix $B$ obtained from $A$ by replacing some $0$s (perhaps none) by $+1$s is a completion of $A$; if $B$ is an ASM, then $B$ is called a completion of $A$ to an ASM or an ASM completion of $A$. Specifically, we are primarily concerned with the completion of a certain class of $(0,-1)$-matrices to ASMs. To define this class, we first introduce some standard notation. Let $B$ be an $m\times n$ matrix, and let $K\subseteq \{1,2,\ldots ,m\}$ and $L\subseteq \{1,2,\ldots ,n\}$. Then $B[K|L]$ is the $|K|\times |L|$ submatrix of $A$ determined by the rows with indices in $K$ and the columns with indices in $L$. Let $n\ge 2$. By an $n\times n$ bordered-permutation $(0,-1)$-matrix $A$ we mean an $n\times n$ $(0,-1)$-matrix such that the first and last rows and columns contain only zeros, and $A[\{2,3,\ldots ,n-1\}|\{2,3,\ldots ,n-1\}]=-P$ where $P$ is a permutation matrix.

We show that every $n\times n$ bordered-permutation $(0,-1)$-matrix can be completed to an ASM and we characterize those $n\times n$ bordered-permutation $(0,-1)$-matrix which have a unique ASM completion. In general, the number of completions to an ASM equals the permanent of an easily constructed $(0,1)$-matrix and we investigate the $n\times n$ bordered-permutation $(0,-1)$-matrices with the largest number of completions, although we are not able to completely answer this.

2 Preliminaries

Let $A=[a_{ij}]$ be an $n\times n$ $(0,-1)$-matrix, Let ${\mathcal C}(A)$ be the set of completions of $A$ to an ASM. In order that ${\mathcal C}(A)$ be nonempty, it is obviously necessary that the following two properties hold: that

• (ASM1) $A$ does not have any $-1$s in its first and last row and column.

• (ASM2) There do not exist consecutive $-1$s in a row or column.

As noted in [2], if $R=(r_1,r_2,\ldots ,r_n)$ and $S=(s_1,s_2,\ldots ,s_n)$ record the number of nonzeros in the rows and columns of an $n\times n$ ASM, then

$$\begin{aligned} R,S\le (1,3,5,7,\ldots ,7,5,3,1)\quad \hbox {(entrywise).} \end{aligned}$$

It follows that if $U=(u_1,u_2,\ldots ,u_n)$ and $V=(v_1,v_2,\ldots ,v_n)$ record the number of $-1$s in the rows and columns of $A$, then, in order that ${\mathcal C}(A)\ne \emptyset$, it is also necessary that

• (ASM3) $U,V\le (0,1,2,3,\ldots ,3,2,1,0) \quad \hbox {(entrywise)}$.

Example 2.1

Let

$$\begin{aligned} A=\left[ \begin{array}{r|r|r|r|r|r|r} &{}&{}&{}&{}&{}&{}\\ \hline &{}&{}&{}-1&{}&{}&{} \\ \hline &{}&{}-1&{}&{}-1&{}&{} \\ \hline &{}-1&{}&{}&{}&{}-1&{} \\ \hline &{}&{}-1&{}&{}-1&{}&{} \\ \hline &{}&{}&{}-1&{}&{}&{} \\ \hline &{}&{}&{}&{}&{}&{} \end{array}\right] . \end{aligned}$$

Any completion of $A$ to an ASM must include $+1$s as shown in

$$\begin{aligned}A'=\left[ \begin{array}{r|r|r|r|r|r|r} &{}&{}&{}+1&{}&{}&{}\\ \hline &{}&{}+1&{}-1&{}+1&{}&{} \\ \hline &{}+1&{}-1&{}&{}-1&{}+1&{} \\ \hline +1&{}-1&{}&{}&{}&{}-1&{}+1 \\ \hline &{}+1&{}-1&{}&{}-1&{}+1&{} \\ \hline &{}&{}+1&{}-1&{}+1&{}&{} \\ \hline &{}&{}&{}+1&{}&{}&{} \end{array}\right] . \end{aligned}$$

Now $+1$s are required between four pairs of $-1$s, but the result is never an ASM. Note that if we put a $-1$ in the middle position of $A$, then there is a unique completion to an ASM. $\Box$

Example 2.1 illustrates the general fact that if in an $n\times n$ $(0,-1)$-matrix $A$ there exists $K\subseteq \{1,2,\ldots ,n\}$ with $|K|=3$ and an $L\subseteq \{1,2,\ldots ,n\}$ such that

$$\begin{aligned} A[K|L]\hbox { or } A[K|L]^t=\left[ \begin{array}{c|ccc|c} -1&{}*&{}\cdots &{}*&{}-1\\ \hline &{}&{}&{}&{}\\ \hline -1&{}*&{}\cdots &{}*&{}-1\end{array}\right] \end{aligned}$$

(where, according to our convention, the middle row shown is all 0s), then $A$ does not have a completion to an ASM.

Let $A$ be an $n\times n$ $(0,-1)$-matrix satisfying (ASM1–3), and let $\sigma (A)$ equal the number of $-1$s in $A$. Let $Z\subseteq \{1,2,\ldots ,n\}\times \{1,2,\ldots ,n\}$ be the set of zero positions of $A$. The $-1$s of $A$ partition $Z$ into two sets of cardinality $n+\sigma (A)$ called the horizontal partition ${\mathcal H}(A)$, consisting of the horizontal blocks, and the vertical partition ${\mathcal V}(A)$, consisting of the vertical blocks. For each $i=1,2,\ldots ,n$, if there are $c_i\ge 0$ $-1$s in row $i$ of $A$, then row $i$ gives $c_i+1$ horizontal blocks consisting of those positions occupied by $0$s to the left of the first $-1$, in-between two consecutive $-1$s, and to the right of the last $-1$. Included in ${\mathcal H}(A)$ is the set of $n$ positions in the first row and the set of $n$ positions in the last row. The vertical partition ${\mathcal V}(A)$ is defined in a similar way and it contains, in particular, the set of $n$ positions in column 1 and the set of $n$ positions in columns $n$. Each $H\in {\mathcal H}(A)$ and each $V\in {\mathcal V}(A)$ intersect in at most one element of $Z$. We define a bipartite graph $G(A)\subseteq K_{n+\sigma (A),n+\sigma (A)}$ with vertex bipartition ${\mathcal H}(A),{\mathcal V}(A)$ where there is an edge joining $H\in {\mathcal H}(A)$ and $V\in {\mathcal V}(A)$ if and only if $H\cap V\ne \emptyset$.

Example 2.2

Let $n=5$

$$\begin{aligned}A=\left[ \begin{array}{c|c|c|c|c} &{}&{}&{}&{}\\ \hline &{}&{}-1&{}&{}\\ \hline &{}-1&{}&{}-1&{}\\ \hline &{}&{}&{}&{}\\ \hline &{}&{}&{}&{}\end{array}\right] \end{aligned}$$

where $\sigma (A)=3$. Then the horizontal partition ${\mathcal H}(A)$ consists of 8 horizontal blocks: all the positions in row 1, all the positions in row 4, all the positions in row 5, and $\{(2,1), (2,2)\}$, $\{(2,4),(2,5)\}$, $\{(3,1)\}$, $\{(3,3)\}$, and $\{(3,5)\}$. The vertical partition ${\mathcal V}(A)$ consists of 8 vertical blocks computed in a similar way.

We have the following observation.

Lemma 2.3

There is a one-to-one correspondence between the set ${\mathcal C}(A)$ of completions of $A$ to an ASM and the set of perfect matchings of $G(A)$. In particular, $A$ has a completion to an ASM if and only if the bipartite graph $G(A)$ has a perfect matching.

It follows from (ASM3) that the number of $-1$s in an $n\times n$ ASM is at most

$$\begin{aligned} \left\lfloor \frac{n}{2}\right\rfloor \left\lfloor \frac{n-1}{2}\right\rfloor =O(n^2). \end{aligned}$$

There are well known polynomial algorithms with order of magnitude $O(m^{2.5})$ to determine a perfect matching in a bipartite graph $G^*\subseteq K_{m,m}$. It follows from Lemma 2.3 that there is a polynomial algorithm to determine a completion to an ASM of an $n\times n$ $(0,-1)$-matrix with order of magnitude $O(n^5)$.

Let $M$ be the $(n+\sigma (A))\times (n+\sigma (A))$ biadjacency matrix of $G(A)$. Then the number of completions of $A$ to an ASM, that is the number of perfect matchings of $G(A)$, equals the permanent of $M$. Thus $A$ has a completion to an ASM if and only if per $M>0$ and $A$ has a unique completion to an ASM if and only if per $M=1$. It is known (see e.g., [3]) that a square matrix has permanent equal to 1 if and only if its rows and columns can be permuted to obtain a triangular matrix with all 1s on the main diagonal.

3 Main Results

In this section we focus on $n\times n$ bordered-permutation $(0,-1)$-matrices $A$. Thus $\sigma (A)= n-2$ and $G(A)\subseteq K_{2n-2,2n-2}$.

Theorem 3.1

Let $n\ge 2$. An $n\times n$ bordered-permutation $(0,-1)$-matrix $A$ can be completed to an ASM.

Proof

If $n=2$, then $A$ is a zero matrix, and the identity matrix $I_2$ is a completion of $A$ to an ASM. If $n=3$, then $A$ has a unique $-1$ and this $-1$ is in the middle position. The matrix

$$\begin{aligned} \left[ \begin{array}{r|r|r} &{} +1&{}\\ \hline +1&{}-1&{}+1\\ \hline &{}+1&{}\end{array}\right] \end{aligned}$$

is a completion of $A$ to an ASM. We now assume that $n>3$ and proceed by induction on $n$. Let $A=[a_{ij}]$ be an $n\times n$ bordered-permutation $(0,-1)$-matrix. There exists a unique integer $q$ be such that $a_{2q}=-1$. In any completion $B=[b_{ij}]$ of $A$ to an ASM we must have $b_{1q}=+1$. Let $C=[c_{ij}]$ be the matrix obtained from $A$ by deleting row 2 and column $q$. Then $C$ is an $(n-1)\times (n-1)$ bordered-permutation $(0,-1)$-matrix and, by induction, has a completion $D$ to an ASM. Let $D'=[d_{ij}']$ be the $n\times n$ matrix obtained from $D$ by inserting as its top row a row of all $0$s and as its column $q$ the $q$th column of $A$. The $-1$s in $D'$ are in the same locations as the $-1$s in $A$. We now show how to use the ASM $D$ to obtain an ASM completion of $A$.

Without loss of generality we assume that the $+1$ in row 2 of $D'$ (corresponding to the unique $+1$ in the first row of $D$ is in column $r>q$). There are two cases to consider.

Case $q>2$: There is a $t>2$ such that $d'_{t,q-1} =+1$ and an $s>t$ such that $d'_{s,q-1}=-1$. We then replace $d'_{t,q-1}$ with a 0, and replace $d'_{t,q}=0$ and $d_{2,q-1}=0$ with $+1$s. Replacing $d'_{1,q}=0$ with a $+1$ results in an ASM completion of $A$.

Case $q=2$: Let the unique $-1$ in row 3 of $D'$ be in column $v$ and let the unique $-1$ in column 3 of $D'$ be in row $u$. It is possible that $u=v$. Then $d'_{u1}=+1$ and $d'_{2v}=+1$. We now replace $d'_{u1}$ and $d'_{2v}$ with $0$s, and replace $d'_{21}$ and $d'_{u2}$ with $+1$s, and also replace $d'_{12}$ and $d'_{2v}$ with $+1$s, and the resulting matrix is an ASM completion of $A$. $\square$

The inductive proof of Theorem 3.1 implicitly gives an algorithm for constructing a completion to an ASM of a bordered-permutation $(0,-1)$-matrix. We illustrate the proof with the first case of Theorem 3.1 in the next example.

Example 3.2

Consider the bordered-permutation $(0,-1)$-matrix

$$\begin{aligned}A=\left[ \begin{array}{r|r|r|r|r|r|r} &{}&{}&{}&{}&{}&{}\\ \hline &{}&{}-1&{}&{}&{}&{}\\ \hline &{}&{}&{}-1&{}&{}&{}\\ \hline &{}-1&{}&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}&{}-1&{}\\ \hline &{}&{}&{}&{}-1&{}&{}\\ \hline &{}&{}&{}&{}&{}&{}\end{array}\right] . \end{aligned}$$

The matrix obtained by deleting row 2 and column $q=3$ of $A$ is

$$\begin{aligned}C=\left[ \begin{array}{r|r|r|r|r|r} &{}&{}&{}&{}&{}\\ \hline &{}&{}-1&{}&{}&{}\\ \hline &{}-1&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}-1&{}\\ \hline &{}&{}&{}-1&{}&{}\\ \hline &{}&{}&{}&{}&{}\end{array}\right] , \end{aligned}$$

and an ASM completion of $C$ is

$$\begin{aligned}D=\left[ \begin{array}{r|r|r|r|r|r} &{}&{}+1&{}&{}&{}\\ \hline &{}+1&{}-1&{}+1&{}&{}\\ \hline +1&{}-1&{}&{}&{}+1&{}\\ \hline &{}+1&{}&{}&{}-1&{}+1\\ \hline &{}&{}+1&{}-1&{}+1&{}\\ \hline &{}&{}&{}+1&{}&{}\end{array}\right] . \end{aligned}$$

The matrix obtained from $D$ by inserting as its first row a row of all 0s and as its third column the third column of $A$ is

$$\begin{aligned}D'=\left[ \begin{array}{r|r|r|r|r|r|r} &{}&{}&{}&{}&{}&{}\\ \hline &{}&{}-1&{}+1&{}&{}&{}\\ \hline &{}+1&{}&{}-1&{}+1&{}&{}\\ \hline +1&{}-1&{}&{}&{}&{}+1&{}\\ \hline &{}+1&{}&{}&{}&{}-1&{}+1\\ \hline &{}&{}&{}+1&{}-1&{}+1&{}\\ \hline &{}&{}&{}&{}+1&{}&{}\end{array}\right] . \end{aligned}$$

Then with $r=4$ and $s=3$, an ASM completion of $A$ is

$$\begin{aligned}\left[ \begin{array}{r|r|r|r|r|r|r} &{}&{}+1&{}&{}&{}&{}\\ \hline &{}+1&{}-1&{}+1&{}&{}&{}\\ \hline &{}&{}+1&{}-1&{}+1&{}&{}\\ \hline +1&{}-1&{}&{}&{}&{}+1&{}\\ \hline &{}+1&{}&{}&{}&{}-1&{}+1\\ \hline &{}&{}&{}+1&{}-1&{}+1&{}\\ \hline &{}&{}&{}&{}+1&{}&{}\end{array}\right] .\end{aligned}$$

$\square$

Corollary 3.3

Let $A$ be an $n\times n$ $(0,-1)$-matrix such that the first and last rows and columns are zero rows and zero columns, respectively, and $A[\{2,3,\ldots ,n-1\}|\{2,3,\ldots ,n-1\}]$ has at most one $-1$ in each row and column. Then $A$ can be completed to an ASM.

Proof

Suppose that $A$ contains $k$ $-1$s. Then $k\le n-2$, and there exist $K,L\subseteq \{2,3,\ldots ,n-1\}$ such that $A[K|L]$ is a permutation $(0,-1)$-matrix. Thus $A_1=A[\{1,n\}\cup K|\{1,n\}\cup L]$ is a bordered-permutation $(0,-1)$-matrix. By Theorem 3.1, $A_1$ can be completed to an ASM. Let $B$ be an $n\times n$ matrix such that $B[\{1,n\}\cup K|\{1,n\}\cup L]=A_1$ and its complementary submatrix $B[\overline{\{1,n\}\cup K}|\overline{\{1,n\}\cup L}]=I_{n-k-2}$, with all other entries equal to zero. Then $B$ is a completion of $A$ to an ASM. $\square$

The following example shows that a bordered-permutation $(0,-1)$-matrix with an additional $-1$ in rows and columns $\{2,3,\ldots ,n-1\}$, satisfying the conditions (ASM1–3) need not be completable to an ASM.

Example 3.4

Let

$$\begin{aligned}A=\left[ \begin{array}{r|r|r|r|r|r|r} &{}&{}&{}&{}&{}&{}\\ \hline &{}-1&{}&{}&{}&{}&{}\\ \hline &{}&{}-1&{}&{}-1&{}&{}\\ \hline &{}&{}&{}-1&{}&{}&{}\\ \hline &{}&{}&{}&{}-1&{}&{}\\ \hline &{}&{}&{}&{}&{}-1&{}\\ \hline &{}&{}&{}&{}&{}&{}\end{array}\right] . \end{aligned}$$

Then any completion of $A$ to an ASM must include $+1$s as shown in

$$\begin{aligned}\left[ \begin{array}{r|r|r|r|r|r|r} &{}+1&{}&{}&{}&{}&{}\\ \hline +1&{}-1&{}+1&{}&{}&{}&{}\\ \hline &{}+1&{}-1&{}+1&{}-1&{}&{}\\ \hline &{}&{}+1&{}-1&{}+1&{}&{}\\ \hline &{}&{}&{}+1&{}-1&{}+1&{}\\ \hline &{}&{}&{}&{}+1&{}-1&{}+1\\ \hline &{}&{}&{}&{}&{}+1&{}\end{array}\right] , \end{aligned}$$

and this is not further completable to an ASM. $\square$

By Theorem 3.1, every bordered-permutation $(0,-1)$-matrix can be completed to an ASM in at least one way. Some bordered-permutation $(0,-1)$-matrices have a unique completion to an ASM. For example, the $n\times n$ bordered-permutation $(0,-1)$-matrix $A$ with $A[\{2,3,\ldots ,n-1\}|\{2,3,\ldots ,n-1\}]=-I_{n-2}$ has a unique completion to an ASM (see Example 3.4).

Let $A$ be an $n\times n$ bordered-permutation $(0,-1)$-matrix. Let $G(A)\subseteq K_{2n-2,2n-2}$ be the bipartite graph associated with $A$ having bipartition ${\mathcal H}(A), {\mathcal V}(A)$, and let $M$ be the biadjacency matrix of $G(A)$. By Lemma 2.3, $A$ has a unique completion to an ASM if and only if $G(A)$ has a unique perfect matching. Thus $A$ has a unique completion to an ASM if and only if per $M=1$, equivalently, after row and column permutations, $A$ becomes a triangular matrix with all 1s on its main diagonal. Thus in any $(0,1)$-matrix with a nonzero permanent, one can determine whether or not the permanent equals 1 by iteratively choosing a 1 in the matrix whose row contains no other 1 and then deleting its row and column until either (1) all rows and columns have been deleted (the permanent equals 1) or (2) at least one row (and one column) remains and all remaining rows contain at least two 1s (the permanent is $>$1). This implies the following algorithm to determine whether or not a bordered-permutation $(0,-1)$-matrix $A$ has a unique completion to an ASM (recall that $Z$ denotes those positions of $A$ not containing a $-1$):

• (1) Recursively locate a horizontal block $H$ of size 1 and put a $+1$ in its unique position $\beta$. Delete that horizontal block from ${\mathcal H}(A)$ and delete the unique vertical block $V$ containing $\beta$ from ${\mathcal V}(A)$. Also delete all the positions in the vertical block $V$ (including $\beta$ itself) from $Z$ and from all the remaining horizontal blocks containing a position in $V$.

• (2) Continue as in (1) until no positions remain in $Z$ ($A$ has a unique completion to an ASM), or $Z\ne \emptyset$ and no position in $Z$ is contained in a horizontal block of size 1 ($A$ has at least two completions to an ASM).

We now characterize those bordered-permutation $(0,-1)$-matrices that have a unique completion to an ASM. Let $B$ be a $(0,-1)$-matrix with at most one $-1$ in each row and column where these $-1$s occur in positions $(i_1,j_1),(i_2,j_2),\ldots ,(i_t,j_t)$ with $i_1<i_2<\cdots <i_t$. Then $B$ (specifically, referring to the $-1$s in $B$) is monotone decreasing provided that $j_1<j_2<\cdots <j_t$ and is monotone increasing provided that $j_1>j_2>\cdots >j_t$. Now let $A$ be an $n\times n$ bordered-permutation $(0,-1)$-matrix. Then $A$ has a monotone decomposition provided $A$ contains a $-1$ that partitions $A$ as

(1)

where $A_{11}$ and $A_{22}$ are monotone decreasing and $A_{12}$ and $A_{21}$ are monotone increasing. The displayed $-1$, respectively, its position, in (1) is called the central $-1$, respectively, the central position, of the monotone decomposition.

Example 3.5

The following is a monotone decomposition of a $9\times 9$ bordered-permutation $(0,-1)$-matrix:

The $-1$ in position $(5,6)$ is the central $-1$ of the monotone decomposition. The unique completion of $A$ to an ASM is easily determined to be

$\square$

Theorem 3.6

Let $n\ge 3$. An $n\times n$ bordered-permutation $(0,-1)$-matrix $A$ has a unique completion to an ASM if and only if $A$ has a monotone decomposition.

Proof

First assume that $A$ has a monotone decomposition as given in (1). For $i,j\in \{1,2\}$, let $X_{ij}$ denote the $-1$s (or their positions) in $A_{ij}$, and let $z$ denote the central $-1$ or its position in $A$. Then $X_{11}\cup X_{12}\cup \{z\}$ is ‘concave up’, $X_{21}\cup X_{22}\cup \{z\}$ is ‘concave down’, $X_{11}\cup X_{21}\cup \{z\}$ is ‘concave to the left’, and $X_{12}\cup X_{22}\cup \{z\}$ is ‘concave to the right’. These concave properties and the fact that each row of $X_{11}\cup X_{12}$ other than its first row contains exactly one $-1$ imply that the $+1$’s above each $-1$ in $X_{11}\cup X_{12}\cup \{z\}$ are uniquely determined in any ASM completion of $A$. Similarly, the $+1$s below each $-1$ in $X_{21}\cup X_{22}\cup \{z\}$, the $+1$s to the left of each $-1$ in $X_{11}\cup X_{21}\cup \{z\}$, and the $+1$s to the right of each $-1$ in $X_{12}\cup X_{22}\cup \{z\}$, are uniquely determined in any ASM completion of $A$. There are $(n-3)$ $-1$s different from the central $-1$, and each such $-1$ accounts for two of these $+1$s, while the central $-1$ accounts for four. Thus the number of $+1$s uniquely determined in any completion of $A$ to an ASM is

$$\begin{aligned} 2(n-3)+4=2n-2, \end{aligned}$$

the total number of $+1$s in a completion of $A$ to an ASM. We conclude that $A$ has a unique completion to an ASM.

We now prove, by induction on $n$, that if $A=[a_{ij}]$ has a unique completion to an ASM, then $A$ has a monotone decomposition. We first establish three preliminary facts.

(I): Choose $k$ such that $a_{2k}=-1$ is the $-1$ in row 2, and let $B=[b_{ij}]$ be the $(n-1)\times (n-1)$ bordered-permutation $(0,-1)$-matrix obtained from $A$ by deleting row 2 and column $k$, where the row and column indices of $B$ are chosen so that $i\in \{1,3,\ldots ,n\}$ and $j\in \{1,\ldots ,k-1,k+1,\ldots ,n\}$. Then the number of completions of $A$ to an ASM is at least as large as the number of completions of $B$ to an ASM. (Note that, because the set of ASMs is invariant under the symmetries of a square, a similar conclusion holds by choosing a $-1$ in row $n-1$, a $-1$ in column $2$, or a $-1$ in columns $n-1$.)

To prove this assertion, let $a_{3l}=-1$ where, without loss of generality, we assume that $k<l$. First assume that $k\ge 3$, and let $p\ge 3$ be such that $a_{p,k-1}=-1$. Let $B^*=[b_{ij}^*]$ be a completion of $B$ to an ASM. Then $b^*_{1l}=+1$ and $b^*_{q,k-1}=+1$ for some $q$ with $2<q<p$. We obtain a completion of $A^*=[a^*_{ij}]$ to an ASM from $B^*$ by replacing $b^*_{1l}$ with 0, and setting $a^*_{1k}$ and $a^*_{2l}$ equal to $+1$, and by replacing $b^*_{q,k-1}$ with $0$, and setting $a^*_{2,k-1}$ and $a^*_{qk}$ equal to $+1$. All remaining entries of $A^*$ not specified by $B^*$ are set equal to 0. This is illustrated below with $n=7$, $k=3$, $l=5$, $p=5$ and $q=4$ where we have indicated where the changes occur using shading:

If $k=2$, so that $a_{22}=-1$, we get a completion $A^*$ from a completion $B^*$ of $B$ in a similar way, the only difference being that we use the unique $+1$ in column 1 of $B^*$ which occurs in some row $q\ne 1$. Finally, we note that two different completions $B^*$ of $B$ to an ASM give two different completions $A^*$ of $A$ to an ASM. $\square$

(II): Let $k$ and $l$ be integers such that $a_{2k}=a_{3l}=-1$. Suppose that $A$ has a unique completion to an ASM. Then, if $k<l$ the submatrix $A[\{3,4,\ldots ,n\}|\{1,2,\ldots ,k\}]$ is monotone increasing, while if $k>l$, the submatrix $A[\{3,4,\ldots ,n\}|\{k, k+1,\ldots ,n\}]$ is monotone decreasing.

To prove this assertion, we first assume that $k>l$, and that $A[\{3,4,\ldots ,n\}|\{k, k+1,\ldots ,n\}]$ is not monotone decreasing. Let $s=k+1$ and $a_{ps}=-1$. Using row indexing and column indexing as in (I), let $B$ be the $(n-1)\times (n-1)$ bordered-permutation $(0,-1)$-matrix obtained from $A$ by deleting the second row and $k$th column, and let $B^*=[b^*_{ij}]$ be a completion of $B$ to an ASM where we must have $b^*_{1l}=+1$. There also exists $b^*_{js}=+1$ for some $j<p$. Since $A[\{3,4,\ldots ,n\}|\{k,k+1.\ldots ,n\}]$ is not monotone decreasing, there exists $b^*_{ir}=+1$ and $b^*_{qr}=-1$ where $b^*_{im}=0$ for $k+1\le m< r$ and $i<q$. We have that $b^*_{ir}=+1$ for some $i<q$ and $b^*_{js}=+1$ for some $j<p$. We obtain a completion $A^*=[a^*_{ij}]$ of $A$ to an ASM by replacing each of $b^*_{ir}$ and $b^*_{1l}$ with $0$, and setting each of $a^*_{1k}, a^*_{2l}, a^*_{2r}$ and $a^*_{ik}$ equal to $+1$. By using $b^*_{js}$ instead of $b^*_{ir}$ we obtain a different completion of $A$ to an ASM. A similar argument works if $k<l$ and $A[\{3,4,\ldots ,n\}|\{1,2,\ldots ,k\}]$ is not monotone increasing. $\square$

(III): If $A$ has a submatrix $A[\{i,j,k,l\}|\{p,q,q+1,r\}]$, with $i<j<k<l$ and $p<q<r-1$, which is equal to

$$\begin{aligned} \left[ \begin{array}{r|r|r|r} &{}&{}-1&{}\\ \hline -1&{}&{}&{}\\ \hline &{}&{}&{}-1\\ \hline &{}-1&{}&{}\end{array}\right] \hbox { or } \left[ \begin{array}{r|r|r|r} &{}&{}-1&{}\\ \hline &{}&{}&{}-1\\ \hline -1&{}&{}&{}\\ \hline &{}-1&{}&{}\end{array}\right] , \end{aligned}$$

(2)

then $A$ does not have a central position.

To verify this assertion, we observe that, because of the location of the $-1$s in this $4\times 4$ submatrix, the only possible central position of $A$ is a position between rows $j$ and $k$ of $A$ and between columns $q$ and $q+1$. But there is no such position since columns $q$ and $q+1$ are consecutive.$\Box$

If $n\le 6$, then since $A$ has at most four $-1$s, it is easily checked that $A$ has a unique completion to an ASM if and only if $A$ has a monotone decomposition. Now assume that $n\ge 7$ so that $A$ has at least five $-1$s. Let $k$ be an integer such that $a_{2k}=-1$. Let $B=[b_{ij}]$ be the matrix as in (I) where, as before, the row and column indices of $B$ are chosen so that $i\in \{1,3,\ldots ,n\}$ and $j\in \{1,\ldots ,k-1,k+1,\ldots ,n\}$ (thus $b_{ij}=a_{ij}$ for all such $i$ and $j$). Assertion (I) implies that $B$ has a unique completion to an ASM, and so by induction, $B$ has a monotone decomposition

(3)

where $b_{uv}=-1$ is the central $-1$ (shaded in (3)), $B_{11}$ and $B_{22}$ are monotone decreasing, and $B_{12}$ and $B_{21}$ are monotone increasing. If $u=3$, then $a_{uv}=-1$ is a central $-1$ of $A$ (since $u=3$, $B_{11}$ and $B_{12}$ do not have any $-1$s). Now assume that $u\ne 3$. We consider the situation in which $a_{3l}=-1$ where this $-1$ belongs to $B_{11}$, that is, $l<k$; a similar argument applies if $l>k$.

The monotone decomposition (3) of $B$ induces the following decomposition of $A$:

(4)

Since $B_{11}$ is monotone decreasing, there cannot be any $-1$s in $A_{11}$. It follows from (II) that the submatrix $A[\{3,4,\ldots ,n\}|\{k, k+1,\ldots ,n\}]$ is monotone decreasing and thus there also cannot be any $-1$s in $A_{14}$ and $A_{23}$. We consider four cases.

Case (i): $l=k-1$. In this case, $A_{12}$ and $A_{22}$ are empty and $a_{3.k-1}=-1$ is a central position of $A$.

Case (ii): $A_{22}$ does not contain any $-1$s. From the fact that (3) is a monotone decomposition of $B$, we now conclude that $a_{3l}=-1$ is a central position of $A$ (the $-1$s in $A_{12}$ and those of $A_{13}$ are monotone decreasing, and together with central $-1$ of $B$ and the $-1$s in $A_{24}$ are also monotone decreasing).

Case (iii): The $-1$ in column $(k-1)$ of $A$ occurs in $A_{12}$, that is, $a_{q,k-1}=-1$ falls in $A_{12}$ for some $q$. Since the $-1$s in $A_{12}$ are monotone decreasing, it follows that the submatrix of $A_{12}$ to the left and below $a_{q,k-1}$ is a zero matrix. With the monotone properties of $B$, this now implies that $a_{q,k-1}$ is a central position of $A$.

Case (iv): The $-1$ in column $(k-1)$ occurs in $A_{22}$, that is, $a_{q,k-1}=-1$ falls in $A_{22}$ for some $q$. We have

(5)

Suppose $A_{21}$ contains a $-1$ and so a $-1$ in its second column. Then, applying (I), we see that the $(n-1)\times (n-1)$ matrix obtained by deleting the row and column of this $-1$ in $A$ has a unique completion to an ASM and so, by induction, has a central position. But the diplayed $-1$s in (5) imply by (III) that there cannot be a central position. Thus $A_{21}$ does not contain any $-1$s, and so $A_{21}$ has only once column and hence $l=2$. A similar argument shows that $A_{24}$ does not contain any $-1$s, and so $A_{24}$ has only one column. Thus (5)

(6)

where we know that $A_{23}$ does not contain any $-1$s. Since $n\ge 7$, there is another $-1$ in $A$ other than the four displayed $-1$s in (6). If $A_{12}$ contains a $-1$, we delete row 3 and column 2; if $A_{13}$ contains a $-1$, we delete the row and column of the central $-1$ of $B$ (now row $u$ and column $n-1$); if $A_{22}$ contains another $-1$, we delete, the row and column of the $-1$ in the next-to-last row of $A_{22}$ (so row $n-1$ of $A$ and some column). In each case, the result is an $(n-1)\times (n-1)$ bordered-permutation $(0.-1)$-matrix $C$ , By (I) again it follows that $C$ has a unique completion to an ASM and by induction that $C$ has a central position. On the other hand, (III) implies that $C$ cannot have a central position. This contradiction completes the proof of the theorem. $\square$

4 Concluding Remarks

We also considered the problem of determining the $n\times n$ bordered-permutation $(0,-1)$-matrices with the largest number of completions to an ASM, but we were not able to satisfactorily determine the solution. This problem is equivalent to determining the $(0,1)$-matrices with the largest permanent among all $(0,1)$-matrices that result as biadjacency matrices of the bipartite graphs coming from $n\times n$ bordered-permutation $(0,-1)$-matrices. There is probably not a simple closed form for this largest permanent which makes it difficult to do a comparison. One has to compare permanents without knowing their values. We do, however, have a conjecture for an ASM with the largest number of completions to an ASM.

Let $E_m$ be the $m\times m$ $(0,-1)$-matrix with $-1$s in positions $(2,m), (3,m-1), \ldots , (m,2)$ and let $F_m$ be the $m\times m$ $(0,-1)$-matrix with $-1$s in positions $(1,m-1), (2,m-2), \ldots , (m-1,1)$.

Conjecture 4.1

If $n\ge 4$ is even, then

$$\begin{aligned} E_{n/2}\oplus F_{n/2} \end{aligned}$$

is the $n\times n$ bordered-permutation $(0,-1)$-matrix with the largest number of ASM completions. If $n\ge 5$ is odd, then

$$\begin{aligned} E_{(n-1)/2}\oplus (-I_1)\oplus F_{(n-1)/2} \end{aligned}$$

is the $n\times n$ bordered-permutation $(0,-1)$-matrix with the largest number of ASM completions.

The biadjacency matrices of the bipartite graphs coming from the matrices in the conjecture have a very special form. Consider the bordered-permutation $(0,-1)$-matrix $E_p\oplus F_q$ where $p+q=n$. Then the adjacency matrix of the bipartite graph $G(E_p\oplus F_q)$ is a Hankel matrix (or by permutations a Toeplitz matrix) with $p+q-1=n-1$ bands of $-1$s. For instance, with $n=10, p=6,\hbox { and }q=4$ we have

$$\begin{aligned}E_6\oplus F_4= \left[ \begin{array}{r|r|r|r|r|r|r|r|r|r} &{}&{}&{}&{}&{}&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}&{}-1&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}-1&{}&{}&{}&{}&{}\\ \hline &{}&{}&{}-1&{}&{}&{}&{}&{}&{}\\ \hline &{}&{}-1&{}&{}&{}&{}&{}&{}&{}\\ \hline &{}-1&{}&{}&{}&{}&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}&{}&{}&{}&{}-1&{}\\ \hline &{}&{}&{}&{}&{}&{}&{}-1&{}&{}\\ \hline &{}&{}&{}&{}&{}&{}-1&{}&{}&{}\\ \hline &{}&{}&{}&{}&{}&{}&{}&{}&{}\end{array}\right] . \end{aligned}$$

Every completion of $E_6\oplus F_4$ to an ASM must have $+1$s as shown in (7).

$$\begin{aligned} \left[ \begin{array}{r|r|r|r|r|r|r|r|r|r} &{}&{}&{}&{}&{}+1&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}+1&{}-1&{}&{}&{}&{}\\ \hline &{}&{}&{}+1&{}-1&{}&{}&{}&{}&{}\\ \hline &{}&{}+1&{}-1&{}&{}&{}&{}&{}&{}\\ \hline &{}+1&{}-1&{}&{}&{}&{}&{}&{}&{}\\ \hline +1&{}-1&{}&{}&{}&{}&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}&{}&{}&{}&{}-1&{}+1\\ \hline &{}&{}&{}&{}&{}&{}&{}-1&{}+1&{}\\ \hline &{}&{}&{}&{}&{}&{}-1&{}+1&{}&{}\\ \hline &{}&{}&{}&{}&{}&{}+1&{}&{}&{}\end{array}\right] . \end{aligned}$$

(7)

The number of completions of $E_6\oplus F_4$ to an ASM those equals the permanent of the $8\times 8$ $(0,1)$-Hankel matrix obtained from (7) by deleting the first and last rows and columns, replacing all $\pm 1$s with 0s, and putting $1$s in the positions of the bands ‘between’ the bands of $-1$s as shown in (8).

$$\begin{aligned} \left[ \begin{array}{c|c|c|c|c|c|c|c} &{}&{}&{}&{}&{}1&{}1&{}1\\ \hline &{}&{}&{}&{}1&{}1&{}1&{}1\\ \hline &{}&{}&{}1&{}1&{}1&{}1&{}1\\ \hline &{}&{}1&{}1&{}1&{}1&{}1&{}1\\ \hline &{}1&{}1&{}1&{}1&{}1&{}1&{}1\\ \hline 1 &{}1&{}1&{}1&{}1&{}1&{}1&{}\\ \hline 1&{}1&{}1&{}1&{}1&{}1&{}&{}\\ \hline 1 &{}1&{}1&{}1&{}1&{}&{}&{}\end{array}\right] . \end{aligned}$$

(8)

Our conjecture asserts that in this special case, the matrix

$$\begin{aligned}\left[ \begin{array}{c|c|c|c|c|c|c|c} &{}&{}&{}&{}1&{}1&{}1&{}1\\ \hline &{}&{}&{}1&{}1&{}1&{}1&{}1\\ \hline &{}&{}1&{}1&{}1&{}1&{}1&{}1\\ \hline &{}1&{}1&{}1&{}1&{}1&{}1&{}1\\ \hline 1&{}1&{}1&{}1&{}1&{}1&{}1&{}\\ \hline 1 &{}1&{}1&{}1&{}1&{}1&{}&{}\\ \hline 1&{}1&{}1&{}1&{}1&{}&{}&{}\\ \hline 1 &{}1&{}1&{}1&{}&{}&{}&{}\end{array}\right] \end{aligned}$$

has a larger permanent (it does!) and that its permanent is the largest among the permanents of all the adjacency matrices of graphs $G(A)$ where $A$ is a $10\times 10$ bordered-permutation $(0,-1)$-matrix. More generally, in the even case, it asserts that the largest permanent is obtained by the $(n-2)\times (n-2)$ $(0,1)$-Hankel matrix with an equal number of bands of $1$s to the left and below the upper right corner.