# Sign-restricted matrices of $0$’s, $1$’s, and $-1$’s

Richard A. Brualdi111Department of Mathematics, University of Wisconsin,
Madison, WI 53706, USA<EMAIL_ADDRESS>
Geir Dahl222Department of Mathematics, University of Oslo, Norway.
<EMAIL_ADDRESS>Corresponding author.

(2 January 2021)

###### Abstract

We study sign-restricted matrices (SRMs), a class of rectangular $(0,\pm
1)$-matrices generalizing the alternating sign matrices (ASMs). In an SRM each
partial column sum, starting from row 1, equals 0 or 1, and each partial row
sum, starting from column 1, is nonnegative. We determine the maximum number
of nonzeros in SRMs and characterize the possible row and column sum vectors.
Moreover, a number of results on interchange operations are shown, both for
SRMs and, more generally, for $(0,\pm 1)$-matrices. The Bruhat order on ASMs
can be extended to SRMs with the result a distributive lattice. Also, we study
polytopes associated with SRMs and some relates decompositions.

Key words. Sign matrix, alternating sign matrix, sign-restricted matrix,
polytope, Bruhat order.

AMS subject classifications. 05A18, 05B20, 06A07, 15B35, 15B36.

##  1 Introduction

Let $m$ and $n$ be positive integers and let ${\Delta}_{m,n}$ be the set of
all $m\times n$ matrices each of whose entries is $0$, $+1$, or $-1$, that is,
$(0,\pm 1)$-matrices. Perhaps the best known class of $(0,\pm 1)$-matrices are
the $n\times n$ alternating sign matrices (ASMs) [5, 6, 7, 8, 14]. These are
square matrices in which the $\pm 1$’s in each row and column alternate
beginning and ending with a $+1$, and hence for which all row and column sums
equal 1. The set of $n\times n$ ASMs is denoted by ${\mathcal{A}}_{n}$. In [2,
13] a generalization of ASMs, called sign matrices, has been defined and these
matrices can be rectangular. We prefer to call these matrices “sign-restricted
matrices” to emphasize the restrictions on the signs, and they are defined
next.

A sign-restricted matrix (abbreviated here to SRM) is an $m\times n$ $(0,\pm
1)$-matrix $A$ such that each partial column sum, starting from row 1, equals
0 or 1, and each partial row sum, starting from column 1, is nonnegative. This
definition arose in [2] where they are shown to be in bijection with
combinatorial objects called semistandard Young tableaux, and they were
further investigated in [13]. Row 1 and column 1 of an SRM can only contain
0’s and $+1$’s and, in particular, column 1 can contain only one $+1$. Also
the $+1$’s and $-1$’s in a column alternate, where the corresponding full
column sum is $1$ or $0$ depending on whether its last nonzero entry, if any,
is a 1 or a $-1$. Note that the transpose of an SRM need not be an SRM. If the
rows of $A$ satisfied the same property as the columns and $A$ were a square
matrix, then $A$ would be an ASM. Any leading $r\times s$ submatrix of an ASM
is an SRM.333Of course, the rows of a leading submatrix of an ASM satisfy the
same properties as its columns, and this is not reflected in the definition of
a sign-restricted matrix, since a weaker condition, namely partial row sums
are non-negative, is used. Unlike ASMs, the last nonzero entry in each row and
column of an SRM may be a $-1$. We denote the set of $m\times n$ SRMs by
${\mathcal{S}}_{m,n}$. The subset of ${\mathcal{S}}_{m,n}$ consisting of those
matrices with no $-1$’s (so $(0,1)$-matrices) is denoted by
${\mathcal{S}}_{m,n}^{+}$.

A $1\times n$ SRM is just a $(0,1)$-vector. Since an $m\times n$ SRM has a
column sum vector which is a $(0,1)$-vector, an SRM can be considered as a
generalization of a $(0,1)$-vector.

######  Example 1.1.

Examples of SRMs are

$\left[\begin{array}[]{rrr}0&1&1\\\ 1&-1&0\\\
0&1&-1\end{array}\right],\left[\begin{array}[]{rrrr}0&1&0&1\\\ 1&-1&1&-1\\\
0&1&-1&1\end{array}\right],\mbox{ and }\left[\begin{array}[]{rrr}0&1&1\\\
1&-1&0\\\ 0&1&-1\\\ 0&0&1\end{array}\right].$

A zero matrix is a sign-restricted matrix as is every permutation matrix and
subpermutation matrix.  $\Box$

Let $A$ be an $m\times n$ SRM with row sum vector
$R=(r_{1},r_{2},\ldots,r_{m})$ and column sum vector
$S=(s_{1},s_{2},\ldots,s_{n})$. As remarked above, $S$ is a $(0,1)$-vector,
but $R$ may have integer entries larger than 1. If each partial row sum of $A$
equals $0$ or $1$, then $R$ is also a $(0,1)$-vector and the transpose of $A$
is also a sign-restricted matrix. In general, the number of $1$’s in $S$
equals $\sum_{i=1}^{m}r_{i}$. For instance, the row sum vectors of the SRMs in
Example 1.1 are $(2,0,0)$, $(2,0,1)$, and $(2,0,0,1)$, respectively. The
column sum vectors are $(1,1,0)$, $(1,1,0,1)$, and $(1,1,1)$, respectively.
The set of all SRMs with row sum vector $R$ and column sum vector $S$ is
denoted by ${\mathcal{S}}(R,S)$, or by ${\mathcal{S}}_{m,n}(R,S)$ if we want
to emphasize the dimensions of $R$ and $S$. Similarly we use the notations
${\mathcal{S}}^{+}(R,S)$ and ${\mathcal{S}}_{m,n}^{+}(R,S)$ to denote the SRMs
with nonnegative entries

Notation: We let $M_{m,n}$ denote the set of real $m\times n$ matrices, and
simply write $M_{n}$ when $m=n$.

The remaining paper is organized as follows. Section 2 considers the maximum
number of nonzeros in SRMs and characterizes the possible row and column sum
vectors of SRMs. Also, we study a connection to another class of $(0,\pm
1)$-matrices containing the incidence matrices of directed graphs. In Section
3 we consider the class of SRMs with specified row and column sum vectors, and
their connectivity properties under interchanges are investigated. Section 4
is devoted to the Bruhat order for the class $\mathcal{S}_{m,n}$; we show that
this determines a distributive lattice, and it is the Dedekind-MacNeille
completion of the Bruhat order restricted to $\mathcal{S}^{+}_{m,n}$. In
Section 5 we study a polytope associated with SRMs and some relates
decompositions.

##  2 Some basic properties of SRMs

First we consider the row and column sum vectors of an SRM.

######  Proposition 2.1.

Let $R=(r_{1},r_{2},\ldots,r_{m})$ and $S=(s_{1},s_{2},\ldots,s_{n})$ be
nonnegative integral vectors, respectively. Then $R$ and $S$ are the row sum
and column sum vectors, respectively, of an SRM $A$ of size $m\times n$ if and
only if $S$ is a $(0,1)$-vector and

$\sum_{i=1}^{m}r_{i}=\sum_{j=1}^{n}s_{j}.$ (1)

In fact, $A$ can be taken to be a matrix in ${\mathcal{S}}_{m,n}^{+}$.

Proof. The conditions are clearly necessary, as an SRM has column sums 0 or 1,
and (1) is trivial. Conversely, assume $S$ is a $(0,1)$-vector and (1) holds.
Let $k=\sum_{i=1}^{m}r_{i}=\sum_{j=1}^{n}s_{j}$. Then $k\leq n$ as $S$ is a
$(0,1)$-vector. Initially, let $A=[a_{ij}]$ be the $(0,1)$-matrix with a 1 in
the first row in those columns for which $s_{j}=1$, while all other entries
are zero. Thus $A$ has column sum vector $S$. Next, we modify $A$ by shifting
the ones in the first row to other rows so as to obtain the row sum vector
$R$; this may be done as $\sum_{i=1}^{m}r_{i}=k$. For instance, this may be
done so that the ones are in a “staircase” pattern in the sense that whenever
$a_{ij}=a_{kl}=1$ and $j<l$, then $i\leq k$. The resulting matrix is a
$(0,1)$-matrix, so a matrix in ${\mathcal{S}}_{m,n}^{+}$.

For $m$ and $n$ fixed, the maximum of $\sum_{i=1}^{n}r_{i}$ in an $m\times n$
SRM is $n$. This follows from Proposition 2.1 as each column sum is 0 or 1 so
that $\sum_{i}r_{i}=\sum_{j}s_{j}\leq n$. This bound is attained by taking $S$
be the all ones vector and $R=(n,0,\ldots,0)$.

The first column of an $m\times n$ SRM can contain only one nonzero and this
nonzero is a 1. The second column can then contain at most three nonzeros, the
third column at most five nonzeros, and so on, until we reach column
$\lceil\frac{m+1}{2}\rceil$ which can contain $m$ nonzeros. After that we can
alternate between columns containing $(m-1)$ and $m$ nonzeros. This
construction gives an $m\times n$ SRM with the maximum number $\zeta_{m,n}$ of
nonzeros.

######  Example 2.2.

We give two examples to illustrate how the maximum is obtained.

$(m=6,n=8):\left[\begin{array}[]{r|r|r|r|r|r|r|r}&&&1&&1&&1\\\
\hline\cr&&1&-1&1&-1&1&-1\\\ \hline\cr&1&-1&1&-1&1&-1&1\\\ \hline\cr
1&-1&1&-1&1&-1&1&-1\\\ \hline\cr&1&-1&1&-1&1&-1&1\\\
\hline\cr&&1&-1&1&-1&1&-1\end{array}\right]\;\;(\zeta_{6,8}=37),$

whose column sum vector is $(1,1,1,0,1,0,1,0)$, and

$(m=9,n=11):\left[\begin{array}[]{r|r|r|r|r|r|r|r|r|r|r}&&&&1&&1&&1&&1\\\
\hline\cr&&&1&-1&1&-1&1&-1&1&-1\\\ \hline\cr&&1&-1&1&-1&1&-1&1&-1&1\\\
\hline\cr&1&-1&1&-1&1&-1&1&-1&1&-1\\\ \hline\cr 1&-1&1&-1&1&-1&1&-1&1&-1&1\\\
\hline\cr&1&-1&1&-1&1&-1&1&-1&1&-1\\\ \hline\cr&&1&-1&1&-1&1&-1&1&-1&1\\\
\hline\cr&&&1&-1&1&-1&1&-1&1&-1\\\
\hline\cr&&&&1&-1&1&-1&1&-1&1\end{array}\right]\;(\zeta_{9,11}=76).$

$\Box$

The construction used in Example 2.2 can be used to give a formula for
$\zeta_{m,n}$ which, in the case of $m=n$, is very simple.

######  Theorem 2.3.

Let $m$ and $n$ be positive integers. Then

$\zeta_{m,n}=\left\\{\begin{array}[]{ll}mn-m^{2}/4-\lceil(1/2)(n-m/2-1)\rceil,&\mbox{
if $m$ is even},\\\ \\\ mn-(m^{2}-1)/4-\lceil(1/2)(n-(m+1)/2)\rceil,&\mbox{ if
$m$ is odd}.\\\ \end{array}\right.$ (2)

In particular, if $m=n$,

$\zeta_{n,n}=\left\\{\begin{array}[]{ll}\frac{3n^{2}-n}{4},&\mbox{ if $n\equiv
0\mbox{ or }3\bmod 4$},\\\ \\\ \frac{3n^{2}-n+2}{4},&\mbox{ if $n\equiv
1\mbox{ or }2\bmod 4$}.\\\ \end{array}\right.$ (3)

Proof. This is a straightforward computation using the above construction.

The maximum difference between the number of 1’s and the number of $-1$’s in
an $m\times n$ SRM is $n$. In fact, in each column, due to the alternating
property, the difference between the number of 1’s and the number of $-1$’s is
either 0 or 1. Thus, for a matrix in $\mathcal{S}_{m,n}$, the maximum
difference between the number of 1’s and the number of $-1$’s is $n$, and this
is attained for the matrix whose first row is the all ones vector, and all
other entries are 0.

The incidence matrices associated with directed graphs give a well-known class
of $(0,\pm 1)$-matrices. Let $D=(V,E)$ be a directed graph with at least one
(directed) edge and vertices $\\{1,2,\ldots,n\\}$. An edge from a vertex $i$
to a vertex $j$ is denoted by $(i,j)$; we assume that $D$ does not have any
loops so that $i\neq j$. The incidence matrix $M$ of $D$ then has rows
corresponding to its vertices (in some order) and columns corresponding to its
edges (again, in some order). The column corresponding to the edge $(i,j)$ has
a 1 in row $i$, a $-1$ in row $j$, and otherwise only zeros. In particular,
each column contains exactly two nonzeros. The first column of $M$ contains a
$-1$ no matter how the edges of $D$ are ordered, and so some row will begin
with a $-1$, and hence $M$ is never an SRM. We can remedy this by using loops.

Let a loop of a digraph at a vertex $i$ correspond to a column in the
incidence matrix with a 1 in row $i$ and otherwise all 0’s.444This is
justified as the loop meets only the vertex $i$ and it allows one to identify
from the incidence matrix which vertices have a loop. So putting loops at all
vertices and letting these loops correspond to the first columns of the
incidence matrix (so the incidence matrix begins with the identity matrix
$I_{n}$), then no row will begin with a $-1$. But this does not guarantee that
the incidence matrix is an SRM under some ordering of the other edges. We now
determine when including certain loops leads to an SRM.

Let $S\subseteq V$ and let $D(S)$ be the digraph obtained from $D$ by putting
a loop at each vertex in $S$. Let $M(S)$ be its incidence matrix obtained from
the incidence matrix $M$ of $D$ by augmenting $M$ by distinct unit vectors
corresponding to vertices in $S$ where these unit vectors come first. We call
$M(S)$ the generalized incidence matrix for $D=(V,E)$ and $S$. Let $d^{+}(v)$
(resp. $d^{-}(v)$) denote the number of edges of $D$ with $v$ as tail (resp.
head).

######  Example 2.4.

Let $D$ be the digraph with vertices $v_{i}$ ($i\leq 4$) and edges
$(v_{1},v_{2})$, $(v_{2},v_{3})$ and $(v_{2},v_{4})$. Let
$S=\\{v_{3},v_{4}\\}$. The generalized incidence matrix, using vertex order
according to their index and edge order $(v_{2},v_{3})$, $(v_{1},v_{2})$,
$(v_{2},v_{4})$ is

$\left[\begin{array}[]{rrrrr}0&0&0&1&0\\\ 0&0&1&-1&1\\\ 1&0&-1&0&0\\\
0&1&0&0&-1\end{array}\right].$

This is an SRM.

######  Theorem 2.5.

Let $M(S)$ be the generalized incidence matrix associated with $D=(V,E)$ and
$S\subseteq V$ where $D$ is a directed graph with at least one edge. Then the
rows and columns of $M$ can be reordered so that the resulting matrix is an
SRM if and only if the following holds

  * (i)

$D$ is acyclic,

  * (ii)

$d^{-}(v)-d^{+}(v)\leq 1$ for each vertex $v$, and if $d^{-}(v)=d^{+}(v)+1$
for some vertex $v$, then $v\in S$.

Proof. First assume that the rows and columns of $M$ are ordered so that
$M(S)$ is an SRM. Suppose to the contrary that $D$ contains a directed cycle
$C$, and let $i$ be the first row in $M$ such that the corresponding vertex
lies in $C$. Moreover, $C$ contains exactly two edges incident to vertex $i$,
one with $i$ as its head, and one with $i$ as its tail. For each of these two
edges, the other end vertex (different from $i$) corresponds to some row below
row $i$. Therefore, since each column of $M$ contains exactly two nonzero
entries, one of the columns of $M$ (and so of $M(S)$) corresponding to these
two edges must have its first nonzero equal to $-1$; contradicting that $M(S)$
is a SRM. This shows that $D$ must be acyclic.

Next, assume there is a vertex $v$ of $D$ with $d^{-}(v)-d^{+}(v)\geq 2$,
i.e., the indegree is at least 2 larger than the outdegree. But then the row
sum of $M$ in that row is at most $-2$ and hence the corresponding row sum of
$M(S)$ is negative. Therefore $d^{-}(v)-d^{+}(v)\leq 1$ for each vertex $v$.
Moreover, if $d^{-}(v)=d^{+}(v)+1$ for some vertex $v$, then $v\in S$;
otherwise the row sum would be negative. So, (ii) holds.

Conversely, assume conditions (i)–(ii) hold. As $D$ is acyclic, its vertices,
and the rows of $M$, may be ordered $v_{1},v_{2},\ldots,v_{n}$ such that each
edge has the form $(v_{i},v_{j})$ for some $i<j$. Next we describe a suitable
ordering of the columns of $M$ so that $M(S)$ is a SRM. Choose $v_{j}$ with
$d^{+}(v_{j})=0$, $d^{-}(v_{j})=1$ and $j$ maximal with this property; such a
vertex must exist. Choose a directed path $P$ in $D$ with a maximal number of
edges and with terminal vertex $v_{j}$. Order the edges consecutively along
the path $P$ with the edge having $v_{j}$ as its head as the first one. Then
order the corresponding columns of $M$ in a similar order. In the submatrix
defined by the columns corresponding to $P$ each row contains a $1$ and a
$-1$, in that order, except the row corresponding to $v_{j}$ where the only
nonzero is a $-1$. However, that row has a $1$ in an earlier column, as unit
elements in $S$ are first. Now, remove the edges of $P$ from $D$ and repeat
this procedure in the resulting graph, by choosing such a path and order the
corresponding columns accordingly. Then the resulting matrix is an SRM, as
desired.

Example 2.4 illustrates Theorem 2.5 and the vertex and edge orders used in the
proof. In summary, the theorem asserts that if a digraph $D$ satisfies (i) and
(ii) one may insert as the initial columns in its incidence matrix a set of
distinct unit columns so that the resulting matrix in a SRM. Moreover, the
unit columns needed are identified.

##  3 Interchanges

In this section we first consider certain connectivity properties of the class
$\mathcal{S}_{m,n}$. Define

$E=\left[\begin{array}[]{rr}1&-1\\\ -1&1\end{array}\right].$ (4)

Let $A$ be an SRM and let $B$ be obtained from $A$ by adding or subtracting
$E$ in some $2\times 2$ submatrix of $A$ (not necessarily with consecutive
rows and consecutive columns). We call this operation an interchange. Whether
or not $B$ is an SRM depends on $A$ and the chosen submatrix. In any case
$R(A)=R(B)$ and $S(A)=S(B)$, where $R(A)$ (resp., $S(A)$) is the row sum
(resp., column sum) vector of $A$, and similarly for $B$.

We now establish the following interchange result, the first conclusion of
which shows that by a sequence of interchanges every matrix in
${\mathcal{S}}_{m,n}(R,S)$ can be brought to a matrix in
${\mathcal{S}}_{m,n}^{+}(R,S)$. The result is related to the construction in
[2] of the “key” of an ASM.

######  Theorem 3.1.

Let $A,B\in\mathcal{S}_{m,n}$ with row sum vectors $R=R(A)=R(B)$ and column
sum vectors $S=S(A)=S(B)$.

  * (i)

There exist SRMs $A^{(i)}$ $(1\leq i\leq k)$ such that $A^{(1)}=A$ and
$A^{(k)}\in\mathcal{A}(R,S)$, and $A^{(i+1)}$ is obtained from $A^{(i)}$ by an
interchange $(1\leq i<k)$.

  * (ii)

There exist SRMs $A^{(i)}$ $(1\leq i\leq p)$ such that $A^{(1)}=A$,
$A^{(p)}=B$, and $A^{(i+1)}$ is obtained from $A^{(i)}$ by an interchange
$(1\leq i<p)$.

Proof. Assume first that $A=[a_{ij}]$ has at least one $-1$. Choose a position
$(i,j)$ with $a_{ij}=-1$ and $i+j$ minimal with this property; we then call
$(i,j)$ a top-left position of a $-1$. (Such a position may not be unique, but
this has no importance.) Since $A$ is an SRM there must exist a $k<i$ such
that $a_{kj}=1$ and there exists $l<j$ such that $a_{il}=1$ (as the first
nonzero in a row or column cannot be a $-1$). Now, we must have $a_{kl}=0$. In
fact, $a_{kl}$ cannot be $-1$ as $(i,j)$ is a top-left position of a $-1$.
Moreover, $a_{kl}$ cannot be $1$, because then column $l$ would have to
contain a $-1$ in some position $(i^{\prime},l)$ with $k<i^{\prime}<i$, again
contradicting that $(i,j)$ a top-left position of a $-1$.

Let the matrix $A^{\prime}$ be obtained from $A$ by adding the $2\times 2$
matrix $E$ (see (4)) to the submatrix of $A$ corresponding to rows $k,i$ and
columns $l,j$. Then, from the properties just mentioned, it follows that
$A^{\prime}$ is an SRM. Moreover, the number of $-1$’s in $A^{\prime}$ is one
less than the number in $A$. We can therefore repeat this procedure of
interchanges and find a sequence of SRMs, each obtained by an interchange
applied to the previous one, such that the final matrix $A^{*}$ does not have
any entries equal to $-1$, i.e., it is a $(0,1)$-matrix. As mentioned,
interchanges do not change any row or column sums, so $R(A^{*})=R(A)$ and
$S(A^{*})=S(A)$. This proves (i).

Similarly, we may find interchanges and intermediary SRMs connecting $B$ to a
$(0,1)$-matrix $B^{*}$. Then $R(B^{*})=R(B)=R(A)=R(A^{*})$ and
$S(B^{*})=S(B)=S(A)=S(A^{*})$, so $A^{*}$ and $B^{*}$ are both contained in
${\mathcal{A}}(R,S)$, and by the Ryser interchange theorem (see e.g., [3]),
one can use interchanges to go from $A^{*}$ to $B^{*}$ such that intermediary
matrices are $(0,1)$-matrices. In fact, the last interchange result is easy to
show directly, because $A^{*}$ and $B^{*}$ are $(0,1)$-SRMs, so each column
contains at most one 1. The theorem now follows.

The algorithm given in the previous proof is illustrated in the next example.

######  Example 3.2.

Consider the SRM $A$ below, and the transformation to an SRM which is a
$(0,1)$-matrix:

$A=\left[\begin{array}[]{rrr}0&1&1\\\ 1&-1&0\\\ 0&1&-1\\\
0&0&1\end{array}\right]\rightarrow\left[\begin{array}[]{rrr}\mbox{ }1&\mbox{
}0&1\\\ 0&0&0\\\ 0&1&-1\\\
0&0&1\end{array}\right]\rightarrow\left[\begin{array}[]{rrr}\mbox{ }1&\mbox{
}1&\mbox{ }0\\\ 0&0&0\\\ 0&0&0\\\ 0&0&1\end{array}\right].$

Here we first added the submatrix $E$ to the submatrix given by the first two
rows and columns, and then we added $E$ to the submatrix given by rows $1,3$
and columns $2,3$ to get the final matrix.

From the proof of Theorem 3.1 it follows that every matrix class
$\mathcal{S}(R,S)$, consisting of SRMs with row sum vector $R$ and column sum
vector $S$, contains a unique $(0,1)$-matrix $A=\bar{A}(R,S)$ with the
following structure: ignoring zero columns (where $s_{j}=0$) the first row has
ones in the first $r_{1}$ columns, the second has ones in the next $r_{2}$
columns etc. The example above shows the canonical matrix when $R=(2,0,0,1)$
and $S=(1,1,1)$.

We now turn to interchange properties of general $(0,\pm 1)$-matrices with a
prescribed row sum vector $R$ and column sum vectors $S$. Here again an
interchange is adding or subtracting the matrix $E$ in (4) to some $2\times 2$
submatrix in such a way that one obtains a new $(0,\pm 1)$-matrix, necessarily
with the same row sum vector $R$ and column sum vector $S$.

Let $R=(r_{1},r_{2},\ldots,r_{m})$ and $S=(s_{1},s_{2},\ldots,s_{n})$ be
nonnegative integral vectors with
$r_{1}+r_{2}+\cdots+r_{m}=s_{1}+s_{2}+\cdots+s_{n}$. Let ${\mathcal{A}}(R,S)$
denote the class of $(0,1)$-matrices with specified row sum vector $R$ and
specified column sum vector $S$. Also, let ${\mathcal{A}}^{\pm}(R,S)$ be the
set of all $(0,\pm 1)$-matrices with row sum vector $R$ and column sum vector
$S$. Let $J$ be the $m\times n$ matrix of all 1’s. Then the mapping
$A\rightarrow A+J$ is a bijection between ${\mathcal{A}}^{\pm}(R,S)$ and the
set ${\mathcal{A}}^{0,1,2}(R^{\prime},S^{\prime})$ of all $m\times n$
$(0,1,2)$-matrices with row sum vector $R^{\prime}=R+e_{(m)}$ and column sum
vector $S^{\prime}=S+e_{(n)}$ where $e_{(m)}$ (resp. $e_{(n)}$) is the all 1’s
vector of size $m$ (resp. size $n$). The special case of Theorem 6.2.4 in [3]
obtained by taking $p=2$ gives a necessary and sufficient condition for the
nonemptiness of ${\mathcal{A}}^{0,1,2}(R^{\prime},S^{\prime})$ and thus of
${\mathcal{A}}^{\pm}(R,S)$. Without loss of generality, $S$ can be assumed to
be non-increasing.

######  Lemma 3.3.

([3]) Let $R=(r_{1},r_{2},\ldots,r_{m})$ and $S=(s_{1},s_{2},\ldots,s_{n})$ be
nonnegative integral vectors with
$r_{1}+r_{2}+\cdots+r_{m}=s_{1}+s_{2}+\cdots+s_{n}$. Assume that $S$ is
nonincreasing. Then ${\mathcal{A}}^{0,1,2}(R,S)\neq\emptyset$ if and only if

$\sum_{j=1}^{k}s_{j}\leq\sum_{i=1}^{m}\min\\{r_{i},2k\\},\ (k=1,2,\ldots,n).$

By the bijection of the previous paragraph, we have the following as a
corollary of Lemma 3.3.

######  Corollary 3.4.

${\mathcal{A}}^{\pm}(R,S)\neq\emptyset$ if and only if

$\sum_{j=1}^{k}s_{j}\leq\sum_{i=1}^{m}\min\\{r_{i}+n,2k\\}-km\
(k=1,2,\ldots,n).$

######  Example 3.5.

Let $m=n=2$, and $R=S=(2,0)$. Then $\mathcal{A}^{\pm}(R,S)$ is nonempty and
contains the matrix

$A=\left[\begin{array}[]{rr}1&1\\\ 1&-1\end{array}\right].$

The condition in the theorem becomes:

$\begin{array}[]{ll}k=1:&2=s_{1}\leq\min\\{2,4\\}+\min\\{2,3\\}-1\cdot 2=2\\\
k=2:&2+0=s_{1}+s_{2}\leq\min\\{4,4\\}+\min\\{4,2\\}-2\cdot 2=2.\end{array}$

Note that in this example $\mathcal{A}(R,S)$ is empty.

In [1] (see also Theorem 4.4.6 and the paragraph following its proof in [4]),
the following result is established.

######  Lemma 3.6.

Any two matrices in ${\mathcal{A}}^{0,1,2}(R^{\prime},S^{\prime})$ can be
obtained from one another by a sequence of interchanges with all intermediary
matrices also in ${\mathcal{A}}^{0,1,2}(R^{\prime},S^{\prime})$.

As an immediate corollary we obtain the following.

######  Corollary 3.7.

Any two matrices in ${\mathcal{A}}^{\pm}(R,S)$ can be obtained from one
another by a sequence of interchanges with all intermediary matrices also in
${\mathcal{A}}^{\pm}(R,S)$.

Note that in order to get a matrix with a $-1$ from a matrix $A$ in
${\mathcal{A}}(R,S)$, $A$ needs to have a $2\times 2$ submatrix with at most
one 1. For instance,

$\left[\begin{array}[]{ccc}1&0&0\\\ 0&1&0\\\
1&0&1\end{array}\right]+\left[\begin{array}[]{rrr}0&1&-1\\\ 0&-1&1\\\
0&0&0\end{array}\right]=\left[\begin{array}[]{rrr}1&1&-1\\\ 0&0&1\\\
1&0&1\end{array}\right].$

It follows from Corollary 3.7 that if a nonempty class
${\mathcal{A}}^{\pm}(R,S)$ contains a $(0,1)$-matrix $A$, that is, a matrix in
${\mathcal{A}}(R,S)$, then $A$ can be obtained from any matrix in
${\mathcal{A}}^{\pm}(R,S)$ by a sequence of interchanges where all
intermediary matrices are in ${\mathcal{A}}^{\pm}(R,S)$. In particular, this
is the case when $m=n$ and $R=S=(1,1,\ldots,1)$, for then
${\mathcal{A}}^{\pm}(R,S)$ includes all permutation matrices. The next example
illustrates Corollary 3.7.

######  Example 3.8.

Consider $I_{5}$ and the following $(0,\pm 1)$-matrix with row and column sums
equal to 1:

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

Then by interchanges we get

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

$\Box$

The next theorem characterizes when $\mathcal{A}(R,S)=\mathcal{A}^{\pm}(R,S)$,
and shows (when the class is nonempty) the structure of a certain matrix in
that class.

######  Theorem 3.9.

Let $R$ and $S$ be such that $\mathcal{A}(R,S)\neq\emptyset$. Then
$\mathcal{A}(R,S)=\mathcal{A}^{\pm}(R,S)$ if and only if there are integers
$k,l,m_{i},n_{i}\geq 0$ $(i\leq 3)$ with $p_{i}\geq 2$ $(i\leq k+l)$ such that
$m=m_{1}+m_{2}+m_{3}$, $n=n_{1}+n_{2}+n_{3}$,

$k+\sum_{i=k+1}^{k+l}p_{i}=m_{3},\;\;\mbox{\rm
and}\;\;l+\sum_{i=1}^{k}p_{i}=n_{3}.$

and $R$ is a permutation of

$(\underbrace{n,\ldots,n}_{m_{1}},\underbrace{n-1,\ldots,n-1}_{m_{2}+m_{3}-k},\underbrace{n-p_{1},\ldots,n-p_{k}}_{k})$

and $S$ is a permutation of

$(\underbrace{m,\ldots,m}_{n_{1}},\underbrace{m-1,\ldots,m-1}_{n_{2}+n_{3}-l},\underbrace{m-p_{k+1},\ldots,m-p_{k+l}}_{l}).$

Proof. Let $A\in\mathcal{A}(R,S)$. Suppose there does not exist a matrix in
$\mathcal{A}^{\pm}(R,S)$ having a $-1$. Then every 0 in $A$ must either be (i)
the only 0 in its row, (ii) the only 0 in its column, or (iii) the only 0 in
its row and the only 0 in its column. Otherwise $A$ has a $2\times 2$
submatrix with at most one 1 and then an interchange creates a matrix in
$\mathcal{A}^{\pm}(R,S)$ with a $-1$. So for each $0$ of $A$, either it is the
only 0 in its row or the only 0 in its column, or it is the only 0 in its row
and the only 0 in its column. Thus the row and column sum vector of $A$ is of
the form given in the theorem. It is easy to see that if $R$ and $S$ are of
this form, then $\mathcal{A}(R,S)\neq\emptyset$ and
$\mathcal{A}^{\pm}(R,S)=\mathcal{A}(R,S)$.

######  Example 3.10.

The following $6\times 8$ matrix $A$ has row sum vector $R=(8,7,7,5,7,7)$ and
column sum vector $S=(6,6,5,5,5,5,5,4)$ satisfying the properties specified in
Theorem 3.9. A $6\times 8$ $(0,\pm 1)$-matrix with these row and column sum
vectors cannot contain a $-1$.

$A=\left[\begin{array}[]{rr|rr|rrrr}1&1&1&1&1&1&1&1\\\ \hline\cr
1&1&0&1&1&1&1&1\\\ 1&1&1&0&1&1&1&1\\\ \hline\cr 1&1&1&1&0&0&0&1\\\
1&1&1&1&1&1&1&0\\\ 1&1&1&1&1&1&1&0\end{array}\right].$

To conclude this section, we consider another kind of question for the class
$\mathcal{A}^{\pm}(R,S)$, i.e., the $(0,\pm 1)$-matrices with row sum vector
$R$ and column sum vector $S$. The following theorem determines the convex
hull of this class (in the space $M_{n}$ of all $n\times n$ real matrices).

######  Theorem 3.11.

Then the convex hull of ${\mathcal{A}}^{\pm}(R,S)$ equals the set of $n\times
n$ real matrices $A=[a_{ij}]$ satisfying

$\begin{array}[]{cl}\vspace{0.05cm}\sum_{j=1}^{n}a_{ij}=r_{i}&(1\leq i\leq
n),\\\ \vspace{0.05cm}\sum_{i=1}^{n}a_{ij}=s_{j}&(1\leq j\leq n),\\\
\vspace{0.05cm}-1\leq a_{ij}\leq 1&(1\leq i,j\leq n).\end{array}$ (5)

Proof. This follows from the fact that the vertex-edge incidence matrix of a
bipartite graph is totally unimodular, see [15] (Section 19.3). In fact, this
general fact implies that each extreme point $A=[a_{ij}]$ of the polyhedron
defined by (5) is integral, so $A$ is a $(0,\pm 1)$-matrix satisfying the
equations in (5). Therefore the set of extreme points is equal to
${\mathcal{A}}^{\pm}(R,S)$.

##  4 Bruhat order

We return to sign-restricted matrices. Recall that ${\mathcal{S}}^{+}_{m,n}$
denotes the set of $m\times n$ $(0,1)$-SRMs, equivalently, the set of $m\times
n$ SRMs without any $-1$’s. Thus the matrices in ${\mathcal{S}}^{+}_{m,n}$
have at most one 1 in each column and there is no restriction on the number of
1’s in each row. The matrices in ${\mathcal{S}}^{+}_{m,n}$ are the incidence
matrices of an ordered partition $(X_{1},X_{2},\ldots,X_{m})$ of a subset of
$\\{1,2,\ldots,n\\}$ in which, contrary to the usual definition of a
partition, some of the parts $X_{i}$ may be empty. Two extreme cases are
$(\emptyset,\emptyset,\ldots,\emptyset)$ corresponding to the zero matrix
$O_{m,n}$ in ${\mathcal{S}}^{+}_{m,n}$, and
$(\\{1,2,\ldots,n\\},\emptyset,\ldots,\emptyset)$ corresponding to the matrix
in ${\mathcal{S}}^{+}_{m,n}$ whose first row is all $1$’s and other rows are
all $0$’s. We can also think of ${\mathcal{S}}^{+}_{m,n}$ as a generalization
of the set ${\mathcal{P}}^{*}_{m,n}$ of $m\times n$ subpermutation matrices
(or, when $m=n$, the set of $n\times n$ permutation matrices
${\mathcal{P}}_{n}$) where the restriction of at most one $1$ in each row is
removed, but the restriction of at most one 1 in each column is retained.

Let $n$ be a positive integer. Consider the partially ordered set (actually a
distributive lattice) $(\mathcal{Q}_{n},\subseteq)$ of subsets of
$\\{1,2,\ldots,n\\}$ ordered by inclusion. We may identify the elements of
$(\mathcal{Q}_{n},\subseteq)$ with the partially ordered set of $2^{n}$
$n$-tuples of $0$’s and $1$’s where
$(a_{1},a_{2},\ldots,a_{n})\leq(b_{1},b_{2},\ldots,b_{n})$ if and only if
$a_{i}\leq b_{i}$ for $i=1,2,\ldots,n$. As is well known, the $n\times n$
permutation matrices are in bijective correspondence with the saturated chains
of $(\mathcal{Q}_{n},\subseteq)$ from $\emptyset$ to $\\{1,2,\ldots,n\\}$; for
instance, if $n=4$, then

$(0,0,0,0)<(0,0,1,0)<(1,0,1,0)<(1,0,1,1)<(1,1,1,1),$

equivalently,

$\emptyset\subset\\{3\\}\subset\\{1,3\\}\subset\\{1,3,4\\}\subset\\{1,2,3,4\\}$

and this corresponds to the permutation $(3,1,4,2)$ and the permutation matrix

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

There is a similar equivalence for the matrices in ${\mathcal{S}}^{+}_{m,n}$
which we now discuss. Consider as above the partially ordered set
$(\mathcal{Q}_{n},\subseteq)$. A multichain of length $m$ in
$(\mathcal{Q}_{n},\subseteq)$ is a sequence of subsets of $\\{1,2,\ldots,n\\}$
of the form

$\emptyset=X_{0}\subseteq X_{1}\subseteq X_{2}\subseteq\cdots\subseteq X_{m}.$

Notice that the definition of a multichain implies that it starts with
$\emptyset$. Since column sums may equal 0, a multichain need not end with
$X_{m}=\\{1,2,\ldots,n\\}$. Also in contrast to the usual notion of a chain in
a partially ordered set, in a multichain there may be repeats in the
chain.555If one thinks of a chain of length $m$ as a path of length $m$ of
edges in a graph, a multichain may have loops, perhaps more than 1, at any
vertex of that path. Let $\mathcal{C}_{m,n}$ be the set of all multichains of
$(\mathcal{Q}_{n},\subseteq)$ of length $m$. In terms of the identification of
$\mathcal{Q}_{n}$ as $n$-tuples of $0$’ s and $1$’s, a multichain allows for
the possibility that successive $n$-tuples are equal.

Generalizing the above, the matrices in ${\mathcal{S}}^{+}_{m,n}$ are in
bijective correspondence with the multichains in $\mathcal{C}_{m,n}$; for
instance, if $m=4$ and $n=6$, then

$(0,0,0,0,0,0)\leq(0,1,0,0,1,0)\leq(0,1,1,0,1,0)\leq(0,1,1,0,1,0)\leq(1,1,1,1,1,1),$

equivalently,

$\emptyset\subseteq\\{2,5\\}\subseteq\\{2,3,5\\}\subseteq\\{2,3,5\\}\subseteq\\{1,2,3,4,5,6\\}$

and this corresponds to the matrix in ${\mathcal{S}}^{+}_{4,6}$ given by

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

There is a partial order, denoted by $\leq_{B}$ and called the Bruhat-order,
on the set $\mathcal{P}_{n}$ of $n\times n$ permutation matrices (and other
classes of matrices as well including ASMs) which can be defined as follows:

For an $m\times n$ matrix $A=[a_{ij}]$, let the sum-matrix666Also called the
corner sum matrix in the literature on ASMs. of $A$ be
$\Sigma(A)=[\sigma_{ij}(A)]$ where

$\sigma_{ij}(A)=\sum_{1\leq p\leq i,\,1\leq q\leq j}a_{pq},\quad(1\leq i\leq
m,1\leq j\leq n),$

the sum of the entries of $A$ in its leading $i\times j$ submatrix. Then

$A_{1}\leq_{B}A_{2}\mbox{ provided that }\Sigma(A_{1})\geq\Sigma(A_{2})\mbox{
(entrywise).}$

The partially ordered set $(\mathcal{P}_{n},\leq_{B})$ is not a lattice if
$n\geq 3$. The Dedekind-MacNeille completion of $(\mathcal{P}_{n},\leq_{B})$,
the (unique up to isomorphism) smallest lattice extension of
$(\mathcal{P}_{n},\leq_{B})$, was shown by Lascoux and Schűtzenberger [11] to
be the Bruhat order on the set $\mathcal{A}_{n}$ of $n\times n$ ASMs:

$A_{1}\leq_{B}A_{2}\mbox{ if and only if
}\Sigma(A_{1})\geq\Sigma(A_{2}),\quad(A_{1},A_{2}\in\mathcal{A}_{n}).$

The minimum element of the lattice $(\mathcal{A}_{n},\leq_{B})$ is the
$n\times n$ identity matrix and the maximum element is the $n\times n$ anti-
identity matrix $L_{n}$. In [10] the Dedekind-MacNeille completion of the
poset of partial injective functions was determined. This is similar, but not
identical, to our result in Theorem 4.2, since the posets considered in [10]
are subposets of ours.

We can extend the Bruhat order, as defined above using the sum-matrix, to
${\mathcal{S}}^{+}_{m,n}$ and ${\mathcal{S}}_{m,n}$, thereby obtaining two
partially ordered sets $({\mathcal{S}}^{+}_{m,n},\leq_{B})$ and
$({\mathcal{S}}_{m,n},\leq_{B})$.

######  Example 4.1.

Let $m=n=2$. The set of matrices in $({\mathcal{S}}^{+}_{2,2},\leq_{B})$ along
with their sum-matrices, indicated by $\rightarrow$, is:

$(a)\ \left[\begin{array}[]{cc}0&0\\\
0&0\end{array}\right]\rightarrow\left[\begin{array}[]{cc}0&0\\\
0&0\end{array}\right],\quad(b)\ \left[\begin{array}[]{cc}1&0\\\
0&0\end{array}\right]\rightarrow\left[\begin{array}[]{cc}1&1\\\
1&1\end{array}\right],$ $(c)\ \left[\begin{array}[]{cc}0&1\\\
0&0\end{array}\right]\rightarrow\left[\begin{array}[]{cc}0&1\\\
0&1\end{array}\right],\quad(d)\ \left[\begin{array}[]{cc}0&0\\\
1&0\end{array}\right]\rightarrow\left[\begin{array}[]{cc}0&0\\\
1&1\end{array}\right],$ $(e)\ \left[\begin{array}[]{cc}0&0\\\
0&1\end{array}\right]\rightarrow\left[\begin{array}[]{cc}0&0\\\
0&1\end{array}\right],\quad(f)\ \left[\begin{array}[]{cc}1&0\\\
0&1\end{array}\right]\rightarrow\left[\begin{array}[]{cc}1&1\\\
1&2\end{array}\right],$ $(g)\ \left[\begin{array}[]{cc}0&1\\\
1&0\end{array}\right]\rightarrow\left[\begin{array}[]{cc}0&1\\\
1&2\end{array}\right],\quad(h)\ \left[\begin{array}[]{cc}1&1\\\
0&0\end{array}\right]\rightarrow\left[\begin{array}[]{cc}1&2\\\
1&2\end{array}\right],$ $(i)\ \left[\begin{array}[]{cc}0&0\\\
1&1\end{array}\right]\rightarrow\left[\begin{array}[]{cc}0&0\\\
1&2\end{array}\right].$

(h)(f)(b)(c)(e)(a)(g)(i)(d)

(h)(f)(b)(c)(e)(a)(g)(i)(d)(p)

Figure 1: Hasse diagram of $(\mathcal{S}^{+}_{2,2},\preceq_{B})$ and
$(\mathcal{S}_{2,2},\preceq_{B})$.

Examining Figure 1 we see that every pair of elements except $\\{b,g\\}$ has a
unique LUB (least upper bound in the Bruhat order), and every pair of elements
except $\\{c,d\\}$ has a unique GLB (greatest lower bound in the Bruhat
order). There is only one matrix in ${\mathcal{S}}_{2,2}$ that is not in
${\mathcal{S}}^{+}_{2,2}$, namely the matrix $(p)$ indicated below with its
sum-matrix:

$(p)\ \left[\begin{array}[]{cr}0&1\\\
1&-1\end{array}\right]\rightarrow\left[\begin{array}[]{cc}0&1\\\
1&1\end{array}\right].$

We see that $\Sigma(p)\geq\Sigma(c)$, $\Sigma(p)\geq\Sigma(d)$,
$\Sigma(p)\leq\Sigma(b)$, and $\Sigma(p)\leq\Sigma(g)$. We conclude that $(p)$
is the GLB of $(c)$ and $(d)$, and $(p)$ is the LUB of $(b)$ and $(g)$ in
$(\mathcal{S}_{2,2}),\leq_{B})$ and that $(\mathcal{S}_{2,2},\leq_{B})$ is a
lattice; indeed $(\mathcal{S}_{2,2},\leq_{B})$ is therefore the Dedekind-
MacNeille completion of $(\mathcal{S}^{+}_{2,2},\leq_{B})$; see Figure 1.
$\Box$

It follows that $(\mathcal{P}_{n},\leq_{B})$ is a subposet of
$(\mathcal{S}_{n,n},\leq_{B})$, and $(\mathcal{P}^{*}_{m,n},\leq_{B})$ is a
subposet of $(\mathcal{S}_{m,n},\leq_{B})$. Clearly, the maximal element of
both $(\mathcal{P}_{n},\leq_{B})$ and $(\mathcal{P}^{*}_{m,n},\leq_{B})$ is
$O_{m,n}$, and the minimal element is the $m\times n$ matrix $\Upsilon_{m,n}$
with all 1’s in row 1 and 0’s elsewhere. We have that $\Sigma(\Upsilon_{m,n})$
has all of its rows equal to $(1,2,\ldots,n)$ and hence the sum of the entries
of $\Sigma(\Upsilon_{m,n})$ equals $m{{n+1}\choose 2}$.

We use the notations $A\vee B={\rm LUB}\\{A,B\\}$ and $A\wedge B={\rm
GLB}\\{A,B\\}$ for $A$ and $B$ in a lattice. Also $a\vee b=\max\\{a,b\\}$ and
$a\wedge b=\min\\{a,b\\}$ for real numbers $a,b$.

######  Theorem 4.2.

$(\mathcal{S}_{m,n},\leq_{B})$ is a distributive lattice, and it is the
Dedekind-MacNeille completion of $(\mathcal{S}^{+}_{m,n},\leq_{B})$.

Proof. Let $A,A^{\prime}\in\mathcal{S}_{m,n}$ and let $S=\Sigma(A)=[s_{ij}]$,
$S^{\prime}=\Sigma(A^{\prime})=[s^{\prime}_{ij}]$. Since $f:M_{m,n}\rightarrow
M_{m,n}$ given by $C\rightarrow\Sigma(C)$ is an isomorphism, there is a unique
matrix $C=[c_{ij}]$ such that $\Sigma(C)=T$ where $T=\max\\{S,S^{\prime}\\}$.
Then $C$ is integral; this follows from the facts that $T$ is integral and
$f^{-1}$ maps integral matrices to integral matrices. We show further
properties of $C$.

Let $1<i\leq m$, $1<j\leq n$. Consider the leading $i\times j$ submatrix of
$A$ and partition it by the first $(j-1)$ columns and the last one, and
similar for the rows. The sum of the entries in each of the four blocks of
this submatrix are indicated in the following diagram

$s_{i-1,j-1}$ | $s_{1}$
---|---
$s_{2}$ | $a_{ij}$

where $s_{1}=\sum_{r=1}^{i-1}a_{rj}$ and $s_{2}=\sum_{s=1}^{j-1}a_{is}$.
Similarly, for $A^{\prime}$, we obtain the four sums $s^{\prime}_{i-1,j-1}$,
$a^{\prime}_{ij}$, $s^{\prime}_{1}=\sum_{r=1}^{i-1}a^{\prime}_{rj}$ and
$s^{\prime}_{2}=\sum_{s=1}^{j-1}a^{\prime}_{is}$. Here
$s_{1},s^{\prime}_{1}\in\\{0,1\\}$ as $A,A^{\prime}\in\mathcal{S}_{m,n}$.
Similarly, $s_{1}+a_{ij},s^{\prime}_{1}+a^{\prime}_{ij}\in\\{0,1\\}$ and each
of the four numbers
$s_{2},s_{2}+a_{ij},s^{\prime}_{2},s^{\prime}_{2}+a^{\prime}_{ij}$ are
nonnegative.

Consider the matrix $C=[c_{ij}]$ defined above. Then

$c_{ij}=t_{ij}-t_{i-1,j}-t_{i,j-1}+t_{i-1,j-1}$ (6)

where

$\begin{array}[]{ll}t_{i-1,j-1}&=s_{i-1,j-1}\vee
s^{\prime}_{i-1,j-1}\\\\[3.0pt]
t_{i-1,j}&=(s_{i-1,j-1}+s_{1})\vee(s^{\prime}_{i-1,j-1}+s^{\prime}_{1})\\\\[3.0pt]
t_{i,j-1}&=(s_{i-1,j-1}+s_{2})\vee(s^{\prime}_{i-1,j-1}+s^{\prime}_{2})\\\\[3.0pt]
t_{ij}&=(s_{i-1,j-1}+s_{1}+s_{2}+a_{ij})\vee(s^{\prime}_{i-1,j-1}+s^{\prime}_{1}+s^{\prime}_{2}+a^{\prime}_{ij}).\end{array}$

Observe that $t_{i-1,j}-t_{i-1,j-1}\in\\{0,1\\}$ as
$s_{1},s^{\prime}_{1}\in\\{0,1\\}$. Similarly, $t_{ij}-t_{i,j-1}\in\\{0,1\\}$
as $s_{1}+a_{ij},s^{\prime}_{1}+a^{\prime}_{ij}\in\\{0,1\\}$. Therefore

$c_{ij}=(t_{ij}-t_{i,j-1})-(t_{i-1,j}-t_{i-1,j-1})\in\\{-1,0,1\\}.$

Thus, $C$ is a $(0,\pm 1)$-matrix. This also shows that

$c_{ij}=\left\\{\begin{array}[]{rl}1&\mbox{\rm when $t_{ij}=t_{i,j-1}+1$ and
$t_{i-1,j}=t_{i-1,j-1}$},\\\ -1&\mbox{\rm when $t_{ij}=t_{i,j-1}$ and
$t_{i-1,j}=t_{i-1,j-1}+1$},\\\ 0&\mbox{\rm otherwise. }\end{array}\right.$ (7)

Here $t_{0j}=0$ for each $j$ and $t_{i0}=0$ for each $i$ (as for $A$ and
$A^{\prime}$).

We now prove that $C\in\mathcal{S}_{m,n}$. First, let $1<j\leq n$. Define
$I^{+}_{j}=\\{i:t_{ij}=t_{i,j-1}+1\\}$, and note that $0\not\in I^{+}_{j}$.
Assume $i-1\not\in I^{+}_{j},i\in I^{+}_{j},i+1\in I^{+}_{j},\ldots,k\in
I^{+}_{j},k+1\not\in I^{+}_{j}$. From (7) we get

$c_{ij}=1,\;c_{i+1,j}=c_{i+2,j}=\cdots=c_{kj}=0,\;c_{k+1,j}=-1.$

This implies that the nonzeros in column $j$ alternates between 1 and $-1$,
starting with a $1$ (if any) as $0\not\in I^{+}_{j}$. Also, the first column
of $T$ is the maximum of the first column in $A$ and the first column in
$A^{\prime}$, and therefore the first column in $C$ is either zero or it
contains a single 1.

Next, let $1\leq i\leq m$ and $1\leq k\leq n$. Then

$\begin{array}[]{rl}\sum_{j=1}^{k}c_{ij}&=t_{ik}-t_{i-1,k}\\\\[3.0pt]
&=(s_{ik}\vee s^{\prime}_{ik})-(s_{i-1,k}\vee s^{\prime}_{i-1,k})\\\\[3.0pt]
&\geq 0\end{array}$

as $s_{ik}\geq s_{i-1,k}$ and $s^{\prime}_{ik}\geq s^{\prime}_{i-1,k}$, again
due to $A,A^{\prime}\in\mathcal{S}_{m,n}$. This proves that
$C\in\mathcal{S}_{m,n}$.

Thus, we have that each pair $A,A^{\prime}$ of matrices in $\mathcal{S}_{m,n}$
has a unique greatest lower bound (meet) in the Bruhat order, given by the
matrix $C$ above. Since $(\mathcal{S}_{m,n},\leq_{B})$ is a finite partially
ordered set (or use a similar argument) the corresponding statement for least
upper bound (join) holds as well. Therefore $(\mathcal{S}_{m,n},\leq_{B})$ is
a lattice. In order that $(\mathcal{S}_{m,n},\leq_{B})$ be distributive, we
must have

$A_{1}\wedge(A_{2}\vee A_{3})=(A_{1}\wedge A_{2})\vee(A_{1}\wedge
A_{3})\quad(A_{1},A_{2},A_{3}\in\mathcal{S}_{m,n}).$

The corresponding property for the real numbers with the usual $\leq$ order
relation holds. Since the join and meet in $(\mathcal{S}_{m,n},\leq_{B})$ is
componentwise on the sum-matrices, it follows that
$(\mathcal{S}_{m,n},\leq_{B})$ is distributive.

It remains to prove that $(\mathcal{S}_{m,n},\leq_{B})$ is the Dedekind-
MacNeille completion of $(\mathcal{S}^{+}_{m,n},\leq_{B})$. This will follow
by showing that any given matrix $A\in\mathcal{S}_{m,n}$ is the meet of some
set of matrices in $\mathcal{S}^{+}_{m,n}$.

Let $S=\Sigma(A)=[s_{ij}]$. For $i=1,2,\ldots,m$, let $S^{(i)}$ be the
$m\times n$ matrix whose first $(i-1)$ rows are zero and each of the $(m-i+1)$
remaining rows are equal to row $i$ of $S$ (so these rows are equal). Then
clearly

$S=\max\\{S^{(1)},S^{(2)},\ldots,S^{(m)}\\}$

as $S$ has monotone columns. Now, $S^{(i)}=\Sigma(A^{(i)})$ where $A^{(i)}$ is
the $(0,1)$-matrix whose only nonzero row is row $i$, and it contains a 1 in
position $(i,j)$ precisely when row $i$ in $S$ has an increase in column $j$,
i.e., $s_{i,j-1}<s_{ij}$ $(j\leq n)$ (where we think of a zero’th row and
column of $S$ to contain only zeros). Note that every increase in $S$ is 1 as
the columns in $A$ have alternating signs, so
$A^{(i)}\in\mathcal{S}^{+}_{m,n}$. Therefore $A$ is the meet of
$\\{A^{(i)}:i\leq m\\}$ in the Bruhat order. Thus
$({\mathcal{S}}_{m,n},\leq_{B})$ is the Dedekind-MacNeille completion of
$({\mathcal{S}}_{m,n}^{+},\leq_{B})$.

The construction in the final part of the proof is illustrated by the next
example.

######  Example 4.3.

Consider the following matrix $A$ in ${\mathcal{S}}_{6,6}$ with its
$\Sigma(A)$:

$A=\left[\begin{array}[]{r|r|r|r|r|r}&1&&1&1&\\\ \hline\cr&&1&-1&&1\\\
\hline\cr 1&&-1&1&&-1\\\ \hline\cr&&1&&-1&1\\\ \hline\cr&&&&1&-1\\\
\hline\cr&&&&&1\end{array}\right]\rightarrow\Sigma(A)=\left[\begin{array}[]{c|c|c|c|c|c}0&1&1&2&3&3\\\
\hline\cr 0&1&2&2&3&4\\\ \hline\cr 1&2&2&3&4&4\\\ \hline\cr 1&2&3&4&4&5\\\
\hline\cr 1&2&3&4&5&5\\\ \hline\cr 1&2&3&4&5&6\end{array}\right].$

Then $A$ is the meet of six matrices $A^{(1)},A^{(2)},\ldots,A^{(6)}$ in
${\mathcal{S}}_{6,6}^{+}$: These matrices have only one nonzero row, with a
different row number in each case, as specified below:

row 1: $[0,1,0,1,1,0]$

row 2: $[0,1,1,0,1,1]$

row 3: $[1,1,0,1,1,0]$

row 4: $[1,1,1,1,0,1]$

row 5: $[1,1,1,1,1,0]$

row 6: $[1,1,1,1,1,1]$.

These rows are obtained from the increases in the corresponding rows of
$\Sigma(A)$ where one has to imagine a zeroth column of all 0’s. So for
instance,

$\Sigma(A^{(3)})=\left[\begin{array}[]{c|c|c|c|c|c}0&0&0&0&0&0\\\ \hline\cr
0&0&0&0&0&0\\\ \hline\cr 1&2&2&3&4&4\\\ \hline\cr 1&2&2&3&4&4\\\ \hline\cr
1&2&2&3&4&4\\\ \hline\cr 1&2&2&3&4&4\end{array}\right].$

Then

$\max\\{\Sigma(A^{(1)}),\Sigma(A^{(2)}),\ldots,\Sigma(A^{(6)})\\}=\Sigma(A)$

and in $({\mathcal{S}},\leq_{B})$, the matrix $A$ is the meet of
$A^{(1)},A^{(2)},\ldots,A^{(6)}$.

A finite lattice has a unique smallest element called its zero element. A
join-irreducible element of a finite lattice is a nonzero element of the
lattice which cannot be expressed as the join of two elements different from
it. A nonzero element is join-irreducible if and only if it covers exactly one
element in the lattice. A meet-irreducible element is defined analogously.
These and other properties can be found in [9]. It is straightforward to
verify that the set of meet-irreducible elements of ${\mathcal{S}}_{m,n}$ are
the matrices in ${\mathcal{S}}_{m,n}^{+}$ with exactly one nonzero row. This
follows as in Example 4.3, and using the observation that two distinct
$(0,1)$-vectors of the same size have different sum-matrices.

By Birkhoff’s representation theorem for finite distributive lattices (Theorem
8.17 in [9]), the lattice $({\mathcal{S}}_{m,n},\leq_{B})$ can be respresented
as the lattice $({\mathcal{J}}_{m,n},\subseteq)$ whose elements are the set
${\mathcal{J}}_{m,n}$ of join-irreducible elements of
$({\mathcal{S}}_{m,n},\leq_{B})$ where we identify each element $x$ with the
set $\\{u\leq_{B}x:u\in{\mathcal{J}}_{m,n}\\}$ of join-irreducibles below $x$,
and the partial order is that of set-containment. Equivalently, we represent
$({\mathcal{S}}_{m,n},\leq_{B})$ as the lattice whose elements are the set
${\mathcal{M}}_{m,n}$ of meet-irreducible elements of
$({\mathcal{S}}_{m,n},\leq_{B})$ where we identify each element $x$ with the
set $\\{u\geq_{B}x:u\in{\mathcal{M}}_{m,n}\\}$ of meet-irreducibles above $x$,
and the partial order is that of reverse set-containment.

######  Example 4.4.

We continue with the Example 4.1 and show the two representations described
above, using $(0,1)$-vectors instead of sets, where we omit the $0$’s for
clarity:

$({\mathcal{J}}_{m,n},\subseteq):\quad\begin{array}[]{c||c|c|c|c|c|c}&(a)&(b)&(c)&(f)&(g)&(i)\\\
\hline\cr\hline\cr(a)&1&1&1&1&1&1\\\ \hline\cr(b)&&1&&1&&\\\
\hline\cr(c)&&1&1&1&1&\\\ \hline\cr(d)&&1&&1&1&1\\\ \hline\cr(e)&&1&1&1&1&1\\\
\hline\cr(f)&&&&1&&\\\ \hline\cr(g)&&&&1&1&\\\ \hline\cr(h)&&&&&&\\\
\hline\cr(i)&&&&1&1&1\\\ \hline\cr(p)&&1&1&1&&\end{array}$

$({\mathcal{M}}_{m,n},\supseteq):\quad\begin{array}[]{c||c|c|c|c|c|c}&(b)&(c)&(d)&(e)&(h)&(i)\\\
\hline\cr\hline\cr(a)&&&&&&\\\ \hline\cr(b)&1&1&1&1&&\\\
\hline\cr(c)&&1&&1&&\\\ \hline\cr(d)&&&1&1&&\\\ \hline\cr(e)&1&&&&&\\\
\hline\cr(f)&1&1&1&1&&1\\\ \hline\cr(g)&&1&1&1&&1\\\
\hline\cr(h)&1&1&1&1&1&1\\\ \hline\cr(i)&&&1&1&&1\\\
\hline\cr(p)&&1&1&1&&\end{array}$

$\Box$

Next, we characterize the sum-matrices for the class $\mathcal{S}^{+}_{m,n}$.

######  Lemma 4.5.

Let $S=[s_{ij}]$ be a nonnegative integral $m\times n$ matrix. Then $S$ is the
sum-matrix of a matrix in $\mathcal{S}^{+}_{m,n}$ if and only if

$\begin{array}[]{rll}s_{i,j-1}+s_{i-1,j}-s_{i-1,j-1}&\leq s_{ij}&(i\leq
m,j\leq n),\\\\[3.0pt] s_{mj}&\leq s_{m,j-1}+1&(j\leq n),\end{array}$ (8)

where we define $s_{0j}=s_{i0}=0$ for each $i$ and $j$.

Proof. Let $A\in\mathcal{S}^{+}_{m,n}$ and let $S=\Sigma(A)$, $S=[s_{ij}]$.
Then the first set of constraints in (8) holds as $A$ is nonnegative and
$a_{ij}=s_{ij}-s_{i-1,j}-s_{i,j-1}+s_{i-1,j-1}$ for each $i,j$. The other
constraints hold as each column of $A$ has at most one 1.

Conversely, assume $S$ satisfies (8). As mentioned, the linear map
$T:M_{m,n}\rightarrow M_{m,n}$ given by $T(A)=\Sigma(A)$ is an isomorphism,
there is a unique matrix $A\in M_{m,n}$ such that $T(A)=S$, and this
$A=[a_{ij}]$ is given by $a_{ij}=s_{ij}-s_{i-1,j}-s_{i,j-1}+s_{i-1,j-1}$ for
each $i,j$. This matrix $A$ is integral. Also, the first set of constraints in
(8) implies $a_{ij}\geq 0$ for each $i,j$. Moreover, the second set of
constraints in (8) gives

$\sum_{i=1}^{m}a_{ij}=s_{mj}-s_{m,j-1}\leq 1$

which (as $A$ is nonnegative and integral) means that $A$ is a $(0,1)$-matrix
with at most one 1 in every column, so $A\in\mathcal{S}^{+}_{m,n}$, as
desired.

Let $A\in{\mathcal{A}}(R,S)$. A Bruhat interchange (applied to $A$) is to
replace a submatrix

$\left[\begin{array}[]{rr}0&1\\\ 1&0\end{array}\right]$

by the identity matrix of order 2.

######  Lemma 4.6.

Let $R$ be an $m$-vector of nonnegative integers with sum $n$, and let
$S=(1,1,\ldots,1)\in\mathbb{R}^{n}$. Let $A,C\in{\mathcal{A}}(R,S)$. Then
$\Sigma(A)\geq\Sigma(C)$ if and only if $C$ can be transformed into $A$ by
Bruhat interchanges.

Proof. The assumptions on $R$ and $S$ assure that $\mathcal{A}(R,S)$ is
nonempty. If $A$ can be transformed into $C$ by Bruhat interchanges, then
clearly $\Sigma(A)\geq\Sigma(C)$. Now suppose that $\Sigma(A)\geq\Sigma(C)$.
Let the $k$’th row be the first row where $\Sigma(A)$ and $\Sigma(C)$ differ,
and let $l$ be the first position in row $k$ where they differ. Thus
$a_{kl}=1$ and $c_{kl}=0$. Since $A$ and $C$ have the same row sum, let $t>l$
be the first position where $a_{kt}=0$ and $c_{kt}=1$. Consider the
submatrices of $A$ and $C$ in the region determined by rows $k+1,\ldots,m$ and
columns $l+1,\ldots,t$. Note that column $t$ of $A$ has a 1 in this region,
since $A$ and $C$ agree in column $t$ above row $k$ and so both have only 0’s
in columns $t$ above row $k$. Thus $A$ has a 1 in this region. Consider the
uppermost 1, say it is in position $(k^{\prime},l^{\prime})$. Let
$A^{\prime}=[a^{\prime}_{ij}]$ be obtained from $A$ by interchanging columns
$l$ and $l^{\prime}$, so, as each column has exactly one 1, this is the
inverse of a Bruhat interchange. Therefore $A\leq_{B}A^{\prime}$ and
$A^{\prime}\not=A$. We prove that $\Sigma(A^{\prime})\geq\Sigma(C)$. Note that

$\Sigma(A^{\prime})_{ij}=\left\\{\begin{array}[]{ll}\Sigma(A)_{ij}-1&\mbox{\rm
for $k\leq i<k^{\prime},\,l\leq j<l^{\prime}$}\\\ \Sigma(A)_{ij}&\mbox{\rm
otherwise}.\end{array}\right.$

So, if $k\leq i<k^{\prime},\,l\leq j<l^{\prime}$, then
$\Sigma(A)_{ij}=\Sigma(A)_{il^{\prime}}=0$ and

$\Sigma(A^{\prime})_{ij}=\Sigma(A)_{ij}-1=\Sigma(A)_{il^{\prime}}-1\geq\Sigma(C)_{il^{\prime}}-1\geq\Sigma(C)_{ij}.$

So $\Sigma(A^{\prime})\geq\Sigma(C)$, and $A\leq_{B}A^{\prime}\leq_{B}C$, as
desired. Also, $A^{\prime}$ and $C$ agree in one more position in row $k$,
namely, $(k,l)$. The desired result now follows by induction.

######  Theorem 4.7.

Consider the partially ordered set $(\mathcal{S}^{+}_{m,n},\leq_{B})$, and let
$A,C\in\mathcal{S}^{+}_{m,n}$. Then $A\leq_{B}C$ if and only if $A$ can be
obtained from $C$ by a sequence of operations of the form

$(i)$ a Bruhat interchange, or

$(ii)$ replacing a zero column by a coordinate vector, or

$(iii)$ replacing a column equal to $e_{k}$ by $e_{i}$ where $i<k$, or

$(iv)$ interchanging a nonzero column $j$ with a zero column $k$, where $k<j$.

Proof. We first extend $A$ and $A^{\prime}$ and $C$ to $C^{\prime}$ by
appending a new row of $0$’s and $1$’s so that all column sums of $A^{\prime}$
and $C^{\prime}$ are now equal to 1. Let the row sums of $A^{\prime}$ be
$p_{1},p_{2},\ldots,p_{m+1}$ and the row sums of $C^{\prime}$ be
$q_{1},q_{2},\ldots,q_{m+1}$. Since $A^{\prime}$ and $C^{\prime}$ have exactly
one 1 in each column, we have

$p_{1}+p_{2}+\cdots+p_{m+1}=q_{1}+q_{2}+\cdots+q_{m+1}$ $\
(p_{1}-q_{1})+(p_{2}-q_{2})+\cdots+(p_{m+1}-q_{m+1})=0$
$\sum_{i=1}^{m+1}(p_{i}-q_{i})^{+}=\sum_{i=1}^{m+1}(q_{i}-p_{i})^{+}.$

Let this common value in the last equation be $t$. We extend $A^{\prime}$ and
$C^{\prime}$ to $(m+1)\times(n+t)$ $(0,1)$-matrices by including columns with
exactly one 1 so that the resulting matrices $A^{\prime\prime}$ and
$C^{\prime\prime}$ have the same row sum vector $R$. In each case we use the
earliest column as we go down the rows. Thus $A^{\prime\prime}$ and
$C^{\prime\prime}$ belong to the class ${\mathcal{A}}(R,S)$ where $S$ is a
vector of all 1’s. Moreover, as $\Sigma(A)\geq\Sigma(C)$, it follows that
$\Sigma(A^{\prime\prime})\geq\Sigma(C^{\prime\prime})$. In fact,
$\Sigma(A)_{m+1,j}=\Sigma(C)_{m+1,j}=j$ for each $j$. Also, by the
construction,

$\Sigma(A^{\prime\prime})_{ij}\geq\Sigma(C^{\prime\prime})_{ij}\;\;(i\leq
m+1,\,n\leq j\leq n+t).$

Thus by Lemma 4.6, $A^{\prime\prime}$ can be transformed to $C^{\prime\prime}$
by a sequence of inverse Bruhat interchanges. There are four types of
interchanges depending on where the corresponding $2\times 2$ matrix lies in

$\left[\begin{array}[]{c|c}X_{1}&X_{2}\\\ \hline\cr
X_{3}&X_{4}\end{array}\right].$

Here $X_{3}$ and $X_{4}$ have only one row. The relation between the position
of the interchange and the type of operation in the theorem is now as follows:

  * •

Wholly in $X_{1}$, and so (i).

  * •

In $X_{1},X_{2},X_{3},X_{4}$, and so (ii).

  * •

In $X_{1}$ and $X_{2}$, and so (iii).

  * •

In $X_{1}$ and $X_{3}$ and so (iv).

Hence if $\Sigma(A)\geq\Sigma(C)$, we can get from $A$ to $C$ by a sequence of
inverse of the operations (i), (ii), (iii), and (iv).

We remark that the proof of Theorem 4.7 actually contains an efficient
algorithm which, for given matrices $A,C\in\mathcal{S}^{+}_{m,n}$ with
$A\leq_{B}C$, constructs matrices $K^{(i)}$ with

$A=K^{(p)}\leq_{B}K^{(p-1)}\leq_{B}\cdots\leq_{B}K^{(1)}=C$

such that $K^{(i+1)}$ is constructed from $K^{(i)}$ ($1\leq i<p$) by one of
the four operations given in the theorem.

######  Corollary 4.8.

Consider the partially ordered set $(\mathcal{S}^{+}_{m,n},\leq_{B})$, and let
$A,C\in\mathcal{S}^{+}_{m,n}$. Then $A$ covers $C$ in
$(\mathcal{S}^{+}_{m,n},\leq_{B})$ if and only if $C$ can be obtained from $A$
by one of operations of the form

  * (i)

a Bruhat interchange $\left[\begin{array}[]{cc}0&1\\\
1&0\end{array}\right]\rightarrow\left[\begin{array}[]{cc}1&0\\\
0&1\end{array}\right]$ within consecutive rows and consecutive columns.

  * (ii)

replacing a zero column $n$ with a column with exactly one $1$ where this $1$
is in the last position or, more generally, replacing column $n$ which has a
$1$ in row $j$ with a column which has a $1$ in row $(j-1)$,

  * (iii)

interchanging column $j$ with columns $(j-1)$ where the $1$ in column $j$ is
in the last position and column $(j-1)$ is a zero column.

Proof. This follows from Theorem 4.7 as these are the operations in that
theorem which increase the sum of the entries of $\Sigma(C)$ by exactly 1.

##  5 Polytope and decomposition

In [13] the sign matrix polytope ${\mathcal{P}}_{m,n}$ is defined as the
convex hull of the matrices in ${\mathcal{S}}_{m,n}$ (the SRMs of size
$m\times n$). It is stated in [13] that “all $mn$ entries contribute to the
dimension” and thus that the dimension of ${\mathcal{P}}_{m,n}$ is $mn$ for
$m>1$. In fact, every $m\times n$ $(0,1)$-matrix $E_{ij}$ with all 0’s except
for a 1 in position $(i,j)$ is in ${\mathcal{S}}_{m,n}$ and so these $mn$
matrices are linearly independent. Thus ${\mathcal{P}}_{m,n}$ contains the
standard simplex in $M_{m,n}$. In [13] the following theorem is proved:

######  Theorem 5.1.

The set of extreme points of ${\mathcal{P}}_{m,n}$ is ${\mathcal{S}}_{m,n}$.

This theorem admits a simple proof based on the proof in [6] that the extreme
points of the convex hull of the $n\times n$ ASMs are precisely the $n\times
n$ ASMs. We formulate the following lemma which is essentially the proof given
in [6].

######  Lemma 5.2.

Let $\mathcal{X}_{n}$ be the set of nonzero vectors
$x=(x_{1},x_{2},\ldots,x_{n})$ in which, ignoring $0$’s, the $1$’s and $-1$’s
alternate, and the first nonzero is $1$. Then each vector in $\mathcal{X}_{n}$
is an extreme point of the convex hull of $\mathcal{X}_{n}$.

Proof. Suppose that $x\in\mathcal{X}_{n}$ and

$x=\lambda_{1}x^{(1)}+\lambda_{2}x^{(2)}+\cdots+\lambda_{k}x^{(k)}$

where $x^{(i)}\in\mathcal{X}_{n}$, $\lambda_{i}>0$ $(1\leq i\leq k)$ and
$\sum_{i=1}^{k}\lambda_{i}=1$. If $x$ is a unit vector then, since the $\pm
1$’s in the $x^{(i)}$ alternate, then $x^{(j)}=x$ for some $j$ with
$\lambda_{j}=1$. Now suppose that $x$ is not a unit vector and that $k\geq 2$.
Then $x$ contains both a 1 and a $-1$, so there exists $p$ and $q$ such that
$p+1<q$ and $x_{p}=1$, $x_{p+1}=\cdots=x_{q-1}=0,x_{q}=-1$. It follows that
all $x^{(i)}$ have a 1 in position $p$ and a $-1$ in position $q$. But then
all $x^{(i)}$ have either $0$ or $-1$ in position $p+1$ with at least one $-1$
and hence position $p+1$ of
$\lambda_{1}x^{(1)}+\lambda_{2}x^{(2)}+\cdots+\lambda_{k}x^{(k)}$ does not
equal 0, a contradiction.

Theorem 5.1 follows immediately from Lemma 5.2 by considering any nonzero
column of a matrix in ${\mathcal{S}}_{m,n}$.

In [6] the following notion was introduced. Let $B=[b_{ij}]$ be an $n\times n$
nonnegative matrix. An $n\times n$ matrix $A=[a_{ij}]$ is sum-majorized by $B$
if

$\begin{array}[]{rl}0\leq\sum_{j^{\prime}=1}^{j}a_{ij^{\prime}}\leq
b_{ij}&(1\leq i,j\leq n),\\\\[4.5pt]
0\leq\sum_{i^{\prime}=1}^{i}a_{i^{\prime}j}\leq b_{ij}&(1\leq i,j\leq
n),\\\\[4.5pt] \sum_{j=1}^{n}a_{ij}=b_{in}&(1\leq i\leq n),\\\\[4.5pt]
\sum_{i=1}^{n}a_{ij}=b_{nj}&(1\leq j\leq n).\end{array}$ (9)

Letting $B=J$, the all ones matrix, we see that an integral matrix $A$ is sum-
majorized by $J$ if and only if $A$ is an ASM. Another special case is $B=rJ$,
for some positive integer $r$, and this corresponds to the notion of higher
spin ASMs that was studied in [5]. The following polyhedral result was shown
in [6].

######  Theorem 5.3.

Let $B=[b_{ij}]$ be an $n\times n$ nonnegative matrix. The convex hull of all
integral matrices that are sum-majorized by $B$ equals the set of real
matrices $A=[a_{ij}]$ satisfying the linear system in $(\ref{eq:B-maj_0})$.

Now, we connect this to SRMs, and consider the following variation of (9) for
a given $m\times n$ matrix $A=[a_{ij}]$ and a nonnegative integer $c$

$\begin{array}[]{rl}0\leq\sum_{l=1}^{j}a_{il}&(1\leq i,j\leq n),\\\\[4.5pt]
0\leq\sum_{k=1}^{i}a_{kj}\leq 1&(1\leq i,j\leq n),\\\\[4.5pt]
\sum_{j=1}^{n}a_{ij}\leq c&(1\leq i\leq n).\end{array}$ (10)

We call an integral matrix $A$ satisfying (10) a $c$-SRM. Such a matrix must
be a $(0,\pm 1)$-matrix with its nonzeros alternating in every column. When
$c\geq n$, a $c$-SRM is precisely an SRM (since an SRM has each row sum at
most $n$, and then the third set of constrains in (10) are redundant). In
general, the parameter $c$ bounds the row sums of the matrix. Let
$\mathcal{S}^{c}_{m,n}$ denote the class of $c$-SRMs of size $m\times n$, and
let the $c$-SRM polytope $\mathcal{P}^{c}_{m,n}$ be defined as the convex hull
of the matrices in $\mathcal{S}^{c}_{m,n}$. So, when $c\geq n$, we have
$\mathcal{S}^{c}_{m,n}=\mathcal{S}_{m,n}$ and
$\mathcal{P}^{c}_{m,n}=\mathcal{P}_{m,n}$.

The following result generalizes the linear inequality description of
$\mathcal{P}_{m,n}$ given in [13], and the proof is different and short.

######  Theorem 5.4.

Let $c$ be a nonnegative integer. Then the polytope $\mathcal{P}^{c}_{m,n}$ is
equal to the set of real matrices $A=[a_{ij}]$ satisfying $(\ref{eq:B-maj})$.

Proof. The proof is a slight variation of our proof of Theorem 5.3 in [6]. Let
$D=(V,E)$ denote the directed graph with vertices $v_{ij}$ ($1\leq i\leq m$,
$1\leq j\leq n$) and arcs $(v_{ij},v_{i+1,j})$ and $(v_{ij},v_{i,j+1})$ for
all $i,j$ where the indices are defined. Thus, the vertices correspond to the
positions of an $m\times n$ matrix, and arcs from a position go to the
neighbor below or to the right. Let $\mathcal{P}^{*}\subseteq M_{m,n}$ be the
polyhedron consisting of all real matrices $A=[a_{ij}]\in M_{m,n}$ satisfying
the linear system in $(\ref{eq:B-maj})$. The map $T:A\rightarrow\Sigma(A)$,
where $\Sigma(A)$ denotes the sum-matrix, is an isomorphism on $M_{m,n}$, and
therefore $\mathcal{P}^{*}$ and its image
$\Sigma(\mathcal{P}^{*})=\\{\Sigma(A):A\in\mathcal{P}^{*}\\}$ are isomorphic.
Let $A=[a_{ij}]$ and $S=[s_{ij}]=T(A)$. Then $A=T^{-1}(S)$ is given by

$a_{ij}=s_{ij}+s_{i-1,j-1}-s_{i-1,j}-s_{i,j-1}\;\;\;(1\leq i,j\leq n)$

where we define $s_{0j}=0$ ($1\leq j\leq n$) and $s_{i0}=0$ ($1\leq i\leq n$).
Moreover

$\begin{array}[]{cl}\sum_{l=1}^{j}a_{il}=s_{ij}-s_{i-1,j}&(1\leq i,j\leq
n),\\\\[4.5pt] \sum_{k=1}^{i}a_{kj}=s_{ij}-s_{i,j-1}&(1\leq i,j\leq
n),\\\\[4.5pt] \sum_{1\leq k\leq i,1\leq j\leq n}a_{kj}=s_{in}&(1\leq i\leq
n),\\\\[4.5pt] \sum_{1\leq i\leq n,1\leq l\leq j}a_{il}=s_{nj}&(1\leq j\leq
n).\end{array}$ (11)

Note that this isomorphism $T$ and its inverse $T^{-1}$ preserve integrality,
that is, an integral matrix is mapped by $T$ and $T^{-1}$ into an integral
matrix.

Now, we claim that $\Sigma(\mathcal{P}^{*})$ is the set of matrices
$S=[s_{ij}]$ satisfying

$\begin{array}[]{cl}0\leq s_{ij}-s_{i-1,j}&(1\leq i,j\leq n),\\\\[4.5pt] 0\leq
s_{ij}-s_{i,j-1}\leq 1&(1\leq i,j\leq n),\\\\[4.5pt] s_{in}-s_{i-1,n}\leq
c&(1\leq i\leq n).\end{array}$ (12)

If fact, if $A$ satisfies (10), then, due to (11), $S=\Sigma(A)$ satisfies
(12). Conversely, assume $S=[s_{ij}]$ satisfies (12) and let $A=T^{-1}(S)$.
Then $A=[a_{ij}]$ satisfies $T(A)=S$, so due to (11), $A$ satisfies (10), as
claimed.

The coefficient matrix of the linear system in (12) is totally unimodular, in
fact, it is arc-vertex incidence matrix of the directed graph $D$ introduced
above (with some repeated arcs/columns). Moreover, all the constants in the
system are integers as $c$ is integral. A standard result from polyhedral
theory (see [15]) then implies that $\Sigma(\mathcal{P}^{*})$ is an integral
polyhedron, so all extreme points are integral. From the properties of the
isomorphism, $\mathcal{P}^{*}$ is integral, and this shows the theorem.

######  Theorem 5.5.

Let $A$ be an $m\times n$ SRM. Then there exist disjoint subpermutation
matrices $P_{1},P_{2},\ldots,P_{N}$ and $\lambda_{i}\in\\{1,-1\\}$ $(1\leq
i\leq N)$ such that

$A=\lambda_{1}P_{1}+\lambda_{2}P_{2}+\cdots+\lambda_{N}P_{N}.$

Proof. As already remarked, we may assume that all column sums are equal. If
$m<n$, then we can include $n-m$ zero rows on the bottom of $A$ and this keeps
all column sums equal to 1. If $m>n$, then we can include $m-n$ columns on the
right of $A$ each with a single 1 and this keeps all column sums equal to 1.
Thus we may also assume that $m=n$, that is, that $A$ is a square matrix with
all column sums equal to 1 and hence its row sum vector
$R=(r_{1},r_{2},\ldots,r_{m})$ satisfies $\sum_{i=1}^{n}r_{i}=n$. Let $p$ be
the maximum row sum of $A$. Then we attach to $A$ on the right an $n\times
n(p-1)$ matrix $A_{1}$ with exactly one 1 in each column so that all row sums
now equal $p$. (Note that the arithmetic is correct here: to get all row sums
equal to $p$ we need to attach $np-\sum_{i=1}^{n}r_{i}=np-n=n(p-1)$ columns
with a single 1.) We may attach on the bottom of $A$ an $n(p-1)\times n$
matrix $A_{2}$ with $(p-1)$ 1’s in each column and one 1 in each row in order
to make each column sum equal to $p$. Let $A_{3}$ be a $n(p-1)\times n(p-1)$
$(0,1)$-matrix with $(p-1)$ $1$’s in each row and column. Then the matrix

$B=\left[\begin{array}[]{c|c}A&A_{1}\\\ \hline\cr
A_{2}&A_{3}\end{array}\right]$

is an $np\times np$ $(0,\pm 1)$-matrix, whose row and column sums all equal
$p$ and whose only $-1$’s are in $A$, and hence $B+J_{np}$ is a
$(0,1,2)$-matrix with all row and column sums equal to $p+1$. Hence $B+J_{np}$
is a sum of $(p+1)$ permutation matrices, and since $J_{np}$ is a sum of
permutation matrices, $B$ is a sum of permutation matrices and the negatives
of permutation matrices. Restricting this sum to $A$ completes the proof.

##  6 Coda

In this final section we discuss a connection with an unsolved problem
concerning disjoint realization of $(0,1)$-matrices with specified row and
column sums.

Consider the class $\mathcal{A}(R,S)$ of $m\times n$ $(0,1)$-matrices where
$R=R_{1}+R_{2}$ and $S=S_{1}+S_{2}$, and $R_{1},R_{2},S_{1},S_{2}$ are
nonnegative integral vectors. If there are matrices
$B_{1}\in{\mathcal{A}}(R_{1},S_{1})$ and $B_{2}\in{\mathcal{A}}(R_{2},S_{2})$
such that $B=B_{1}+B_{2}$ is a matrix in $\mathcal{A}(R,S)$, then
$\mathcal{A}(R,S)$ has a $(R_{1},S_{1};R_{2},S_{2})$ joint realization and
$(B_{1},B_{2})$ is a joint realization of $B$ (and of $\mathcal{A}(R,S)$); see
e.g. pages 188–190 in [3]. For a joint realization the matrices $B_{1}$ and
$B_{2}$ cannot have 1’s in common positions and we denote this by $B_{1}\sqcap
B_{2}=\emptyset$.

Let $A\in{\mathcal{A}}^{\pm}(R,S)$. Then $A$ can be uniquely expressed in the
form $A=A_{1}-A_{2}$ where $A_{1}$ and $A_{2}$ are $(0,1)$-matrices such that
$A_{1}\sqcap A_{2}=\emptyset$. Let the row and column sum vectors of $A_{1}$
and $A_{2}$ be, respectively, $R_{1},S_{1}$ and $R_{2},S_{2}$, and let
$R^{\prime}=R_{1}+R_{2}$ and $S^{\prime}=S_{1}+S_{2}$. Then
$A^{\prime}=A_{1}+A_{2}$ is an $(R_{1},S_{1};R_{2},S_{2})$ joint realization
of ${\mathcal{A}}(R^{\prime},S^{\prime})$ and $(A_{1},A_{2})$ is a joint
realization of $A^{\prime}$. Thus, every matrix in ${\mathcal{A}}^{\pm}(R,S)$
with at least one $1$ and at least one $-1$ gives some joint realization of
$\mathcal{A}(R,S)$, and every joint realization of $R,S$ gives a matrix in
${\mathcal{A}}^{\pm}(R,S)$.

Given $R_{1},S_{1}$ and $R_{2},S_{2}$ such that both
${\mathcal{A}}(R_{1},S_{1})$ and ${\mathcal{A}}(R_{1},S_{1})$ are nonempty, it
is an unsolved problem to determine whether or not
${\mathcal{A}}(R_{1}+R_{2},S_{1}+S_{2})$ has an $(R_{1},S_{1};R_{2},S_{2})$
joint realization. A necessary condition is that
${\mathcal{A}}(R_{1}+R_{2},S_{1}+S_{2})$ is nonempty, but this is not
sufficient in general. The following sufficient condition is due to Anstee as
a generalization of a theorem of Brualdi and Ross (see Theorem 4.4.14 of [4]).

######  Theorem 6.1.

Let $R=(r_{1},r_{2},\ldots,r_{m})$ and $S=(s_{1},s_{2},\ldots,s_{n})$ be
nonnegative integral vectors. Let $R_{1}=(k_{1},k_{2},\ldots,k_{m})$ where for
some nonnegative integer $k$, $k\leq k_{i}\leq k+1$ for $i=1,2,\ldots,m$, and
let $S_{1}=(s^{\prime}_{1},s^{\prime}_{2},\ldots,s^{\prime}_{n})$. Let
$R_{2}=R-R_{1}$ and $S_{2}=S-S_{1}$. Then $\mathcal{A}(R,S)$ has an
$(R_{1},S_{1};R_{2},S_{2})$ joint realization if and only if both
$\mathcal{A}(R,S)\neq\emptyset$ and $\mathcal{A}(R_{2},S_{2})\neq\emptyset$.

An immediate corollary of this theorem is the following.

######  Corollary 6.2.

Let $R=(r_{1},r_{2},\ldots,r_{n})$ and $S=(s_{1},s_{2},\ldots,s_{n})$ be
nonnegative integral vectors. Let $e=(1,1,\ldots,1)$ where there are $n$
$1$’s. Let $R^{\prime}=R-e$ and $S^{\prime}=S-e$. Then there exists a matrix
$A=A_{1}-A_{2}$ in $\mathcal{A}^{\pm}(e,e)$ where $A_{1}\in\mathcal{A}(R,S)$
if and only if $\mathcal{A}(R,S)\neq\emptyset$ and
$\mathcal{A}(R^{\prime},S^{\prime})\neq\emptyset$.

Acknowledgment. The authors thank a referee for giving a number of useful
comments and suggestions that improved the paper.

## References

  * [1] R.P. Anstee, The network flows approach for matrices with given row and column sums, Discrete Math., 44 (1983), 125–138.
  * [2] J.C. Aval, 2007/10. Keys and alternating sign matrices, Sém. Lothar, Combin. 59, Art. B59F, 13.
  * [3] R.A. Brualdi, H.J. Ryser,  Combinatorial Matrix Theory,  Cambridge University Press, Cambridge, 1991.
  * [4] R.A. Brualdi, Combinatorial Matrix Classes, Cambridge University Press, Cambridge, 2006.
  * [5] R.E. Behrend, V.A. Knight, Higher spin alternating sign matrices, Electron. J. Combin. 14 (2007), $\\#$1\.
  * [6] R.A. Brualdi, G. Dahl, Alternating sign matrices, extensions and related cones, Adv. in Appl. Math., 86 (2017), 19–49.
  * [7] R.A. Brualdi, G. Dahl, Alternating sign matrices and hypermatrices, and a generalization of Latin squares, Adv. in Appl. Math., 95 (2018), 116–151.
  * [8] D. Bressoud, Proofs and Confirmations. The Story of the Alternating Sign Matrix Conjecture, MAA Spectrum, Math. Assoc. America, Washington, DC, Cambridge Univ. Press, 1994.
  * [9] B.A. Davey, H.A. Priestly, Introduction to Lattices and Order, Cambridge Univ. Press, 1990.
  * [10] M. Fortin, The MacNeille completion of of the poset of partial injective functions, Electron. J. Combin. 15 (2008), $\\#$R62.
  * [11] A. Lascoux, M.-P. Schűtzenberger, Treillis et bases des groupes de Coxeter, Electron. J. Combin. 3 (1996), $\\#$R27.
  * [12] A.W. Marshall, I. Olkin, B.C. Arnold, Inequalities: Theory of Majorization and Its Applications. Second edition. Springer Series in Statistics. Springer, New York, 2011. xxviii+909 pp.
  * [13] S. Solhjem, J. Striker, Sign matrix polytopes from Young tableaux, Linear Algebra Appl., 574 (2019), 84–122.
  * [14] J. Striker, The alternating sign matrix polytope. Electron. J. Combin., 16 (2009), no. 1, Research paper 41, 15 pp.
  * [15] A. Schrijver,  Theory of Linear and Integer Programming,  Wiley-Interscience, Chichester, 1986.