# Convex $(0,1)$-Matrices and Their Epitopes

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.

(12 August 2020)

###### Abstract

We investigate $(0,1)$-matrices that are convex, which means that the ones are
consecutive in every row and column. These matrices occur in discrete
tomography. The notion of ranked essential sets, known for permutation
matrices, is extended to convex sets. We show a number of results for the
class $\mathcal{C}(R,S)$ of convex matrices with given row and column sum
vectors $R$ and $S$. Also, it is shown that the ranked essential set uniquely
determines a matrix in $\mathcal{C}(R,S)$.

Key words. Zero-one matrix, permutation matrix, convexity, essential set,
polyomino.

AMS subject classifications. 05A05, 05B20, 15B36, 52A37.

##  1 Introduction

Mathematical reconstruction problems arise in the area of image analysis, and
discrete tomography ([1, 2, 4, 5]) is such a field where combinatorics plays a
major role. A $(0,1)$-matrix then represents an image with black-white pixels,
and the row and column sums count the number of black pixels in that line.
Within this framework convex matrices, i.e., those with consecutive ones, are
interesting. In this paper we study several questions for such convex
matrices. In particular, we study so-called ranked essential sets for convex
matrices.

A $(0,1)$-matrix $A$ is row convex provided the 1’s in each row occur
consecutively; column convex is defined analogously. The matrix $A$ is convex
provided it is both row and column convex. Permutation matrices are trivially
convex. Let $R=(r_{1},r_{2},\ldots,r_{m})$ and $S=(s_{1},s_{2},\ldots,s_{n})$
be nonnegative integral vectors with
$\sum_{i=1}^{m}r_{i}=\sum_{j=1}^{n}s_{j}$. Let ${\mathcal{A}}(R,S)$ be the set
of all $m\times n$ (0,1)-matrices with row sum vector $R$ and column sum
vector $S$. The class of $m\times n$ convex $(0,1)$-matrices in
${\mathcal{A}}(R,S)$ is denoted by ${\mathcal{C}}_{m,n}(R,S)$ or, more simply
as ${\mathcal{C}}(R,S)$. It is an NP-complete problem to determine whether a
class ${\mathcal{C}}_{m,n}(R,S)$ is nonempty [5, 15].

######  Example 1.1.

Below are convex matrices with $R=(4,1,1,2,1,1)$ and $S=(2,1,3,1,$ $1,1,1)$,
and $R=(5,2,2,3,3,1)$ and $S=(2,2,5,4,1,1,1)$, respectively.

$A_{1}=\left[\begin{array}[]{c|c|c|c|c|c|c}&1&1&1&1&&\\\ \hline\cr&&1&&&&\\\
\hline\cr&&1&&&&\\\ \hline\cr&&&&&1&1\\\ \hline\cr 1&&&&&&\\\ \hline\cr
1&&&&&&\end{array}\right],\qquad
A_{2}=\left[\begin{array}[]{c|c|c|c|c|c|c}&&1&1&1&1&1\\\ \hline\cr&&1&1&&&\\\
\hline\cr&&1&1&&&\\\ \hline\cr&1&1&1&&&\\\ \hline\cr 1&1&1&&&&\\\ \hline\cr
1&&&&&&\end{array}\right].$

$\Box$

######  Example 1.2.

This next example stresses that, not surprisingly, the ordering of the
components of $R$ and $S$ is important for the nonemptiness of
${\mathcal{C}}(R,S)$. Let $R=S=(2,2,1)$. Then we have the convex matrices

$\left[\begin{array}[]{c|c|c}1&1&\\\ \hline\cr 1&1&\\\
\hline\cr&&1\end{array}\right]\mbox{ and }\left[\begin{array}[]{c|c|c}&1&1\\\
\hline\cr 1&1&\\\ \hline\cr 1&&\end{array}\right]\mbox{ but also the nonconvex
}\left[\begin{array}[]{c|c|c}1&&1\\\ \hline\cr 1&1&\\\
\hline\cr&1&\end{array}\right].$

Now let $R=S=(2,1,2)$. Then, as is easily checked,
${\mathcal{C}}(R,S)=\emptyset$. Note that the a matrix whose 1’s form a
Ferrers diagram (the maximal matrix of Ryser when $R$ and $S$ are
nondecreasing) is convex.  $\Box$

As mentioned, it is an NP-complete problem to determine whether a class
$\mathcal{C}(R,S)$ is nonempty, but a goal of this paper is to characterize
this property in terms of $R$ and $S$ for certain subclasses of
$\mathcal{C}_{m,n}(R,S)$.

An epitope333The word ‘epitope’ is a synonym for determinant, a word we avoid
in the current context since it has a well-known and different meaning in
mathematics. of ${\mathcal{A}}(R,S)$ is any information that determines
uniquely a matrix that is known to be in ${\mathcal{A}}(R,S)$. Trivially the
positions of all but one of the 1’s of an $A\in{\mathcal{A}}(R,S)$ is an
epitope of ${\mathcal{A}}(R,S)$. But knowing the position of all but two 1’s
is not an epitope in general, as seen with $R=(1,1)=S$ and the matrices

$\left[\begin{array}[]{cc}1&0\\\ 0&1\end{array}\right]\mbox{ and
}\left[\begin{array}[]{cc}0&1\\\ 1&0\end{array}\right].$

In fact, any two matrices in ${\mathcal{A}}(R,S)$ can be obtained from one
another by a sequence of interchanges which replace any $2\times 2$ submatrix
equal to one of these with the other.

Let $m=n$ and $R=S=(1,1,\ldots,1)$. Then ${\mathcal{A}}(R,S)$ is the set
${\mathcal{P}}_{n}$ of $n\times n$ permutation matrices. In [9] Fulton
determined an epitope of ${\mathcal{P}}_{n}$ called the ranked essential set
obtained as follows. For each 1 of $P\in\mathcal{P}_{n}$ shade (or delete) all
the positions from the 1 and eastwards and from the 1 and southwards leaving
the diagram of $P$. The essential set of $P$ is the set of southeast corners
of the connected components of the unshaded squares of the diagram. For
example, if

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

then, using the above description, we have

$P:\left|\begin{array}[]{c|c|c|c|c|c}\hline\cr&\pagecolor[gray]{.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\star&\pagecolor[gray]{0.9}\hfil&&\star&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\star&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\end{array}\right|\rightarrow\left|\begin{array}[]{c|c|c|c|c|c}\hline\cr\phantom{\star}&\pagecolor[gray]{.9}\
1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr
0&\pagecolor[gray]{0.9}\hfil&&1&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&2&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\end{array}\right|,$ (1)

where the essential set consists of the squares with a $\star$ which are then
replaced by the number of $1$’s in the northwest submatrix they determine
(equivalently, the rank of the northwest submatrix); recall that the shaded
squares are considered deleted. Fulton shows that a permutation matrix is
determined by these rank numbers and their locations, the ranked essential
set, and that in general none of these can be omitted. For emphasis we remark
that the ranked essential set determines $P$ with the knowledge that $P$ is an
$n\times n$ permutation matrix, that is, an $n\times n$ $(0,1)$-matrix with
exactly one 1 in each row and column. The ranked essential set in (1) is given
by

$\\{(2,1;0),(2,4;1),(5,3;2)\\}$

where the first two entries in each triple specify the location and the last
entry specifies the corresponding rank. These triples determine the locations
of the 1’s of the permutation matrix $P$ and thus the ranked essential set is
an epitope for the classes ${\mathcal{A}}(R,S)$ when $R=S=(1,1,\ldots,1)$. In
[8] an algorithm is given that determines a permutation matrix from its ranked
essential set. We show that this algorithm works also for a collection of
“convex matrices” which we call generalized polyominos. In [8] it is also
shown that a permutation matrix is determined by the rank function on a subset
of its essential set called its core where the core has size at most $n$. Thus
the core is also an epitope for these classes. In [7] it is proved that the
average size of the essential set of an $n\times n$ permutation matrix is
asymptotic to $\frac{n^{2}}{36}$. The only permutation matrix in
${\mathcal{P}}_{n}$ with an empty essential set is the identity matrix. If the
essential set has size more than $n$, then the permutation matrix itself is a
more compact representation. Therefore, classes of permutation matrices with
“small” ranked essential sets are interesting.

Recall that a permutation $\pi$ of $\\{1,2,\ldots,n\\}$ is a grassmannian
provided it has exactly one descent (i.e., a pair $(\pi_{i},\pi_{i+1})$ such
that $\pi_{i}>\pi_{i+1}$) and is a bigrassmannian provided both the
permutation and its inverse are grassmannians. With $n=8$, the permutation
$(2,5,7,1,3,4,6,8)$ has exactly one descent, namely $(7,1)$ and is a
grassmannian. Its inverse $(4,1,5,6,2,7,3,8)$ has three descents, namely
$(4,1)$, $(6,2)$, and $(7,3)$, and thus is not a bigrassmannian. The
permutation $(4,5,1,2,3)$ is a bigrassmanian as it has exactly one descent,
namely $(5,1)$, and its inverse $(3,4,5,1,2)$ has exactly one descent, namely
$(5,1)$. We apply the words grassmannian and bigrassmannian to permutation
matrices as well.

######  Example 1.3.

Consider the grassmannian permutation $(2,5,7,1,3,4,6,8)$, its corresponding
grassmannian permutation matrix, its diagram, and its ranked essential set:

$\begin{array}[]{|c|c|c|c|c|c|c|c|}\hline\cr&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr&\pagecolor[gray]{0.9}\hfil&&&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr
0&\pagecolor[gray]{0.9}\hfil&&1&\pagecolor[gray]{0.9}\hfil&2&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}1\pagecolor[gray]{0.9}&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}1\\\
\hline\cr\end{array}.$

The ranked essential set is $\\{(3,1;0),(3,4;1),(3,6;2)\\}$. Notice that the
essential set is contained in one row, thus is row-linear, and the rank
numbers in that row are strictly increasing.  $\Box$

In [10] it is shown that bigrassmannians are characterized by having their
essential sets of cardinality 1. In [8] it is shown that grassmannians are
characterized by having a row-linear essential set and so we get again that
bigrassmannians are characterized by having their essential sets of
cardinality 1 (apply the transpose operation to get the permutation matrix
corresponding to the inverse).

The remaining paper is organized as follows. Section 2 considers convex sets
and extends the definition of ranked essential sets to that class. It is shown
that the ranked essential set determines a matrix in $\mathcal{C}(R,S)$
uniquely, and an algorithm for doing this is given. Next, Section 3 is devoted
to subclasses of $\mathcal{C}(R,S)$ and characterizations of when these
classes are nonempty. Section 4 concerns interchanges that preserve convexity
and $\mathcal{A}(R,S)$ classes with only convex matrices. Finally, in Section
5, we discuss a natural partial order on the class of $m\times n$ convex
matrices.

Notation: By a line of a matrix, we mean either a row or a column. The
$k\times l$ matrix of all 1’s is denoted by $J_{k,l}$, abbreviated to $J_{k}$
if $l=k$.

##  2 Convex $(0,1)$-matrices and ranked essential sets

We discuss convex matrices and introduce their ranked essential sets. A
$(0,1)$-matrix $A$ is called connected provided that

(i) it does not have any zero rows or zero columns, and

(ii) every pair of 1’s is connected by a rookwise path of either row adjacent
or column adjacent 1’s.

To say that a $(0,1)$-matrix is connected is equivalent to saying that it is
the biadjacency matrix of a connected bipartite graph, in particular, it does
not have any isolated vertices. We now show that the essential set is an
epitope of a polyomino in ${\mathcal{A}}(R,S)$. We refer to [2] for
information about convex $(0,1)$-matrices for these and the definitions to
follow. A polyomino is a connected, convex $(0,1)$-matrix444We could allow
zero rows and zero columns in a polyomino as is often done, but such rows and
columns would have to be initial or terminal, and thus would not play any role
in our investigations.. A southeast source, abbreviated to SE-source, of a
$(0,1)$-matrix is a 1 such that every other 1 is reachable from it by a
southeast rookwise path of row adjacent or column adjacent 1’s. NE-sources,
NW-sources, and SW-sources are define analogously. When such sources exist,
they are clearly unique. The matrix $A$ is directed provided it has a source
of at least one of these types. Since under 90 degree rotations, a source of
one type becomes a source of another type, without loss of generality one may
assume that a source is a SE-source. If $A$ is directed and does not have any
zero rows or zero columns, then clearly $A$ is connected. A connected
$(0,1)$-matrix $A$ does not have zero rows or zero columns, and hence if $A$
has a SE-source, it must be a 1 in position $(1,1)$.

The first convex matrix in Example 1.1 is neither connected nor directed; the
second is a directed polyomino with a NW-source and a SW-source

The following theorem is from [14] (see also [2]).

######  Theorem 2.1.

A directed, convex matrix $A$ in ${\mathcal{A}}(R,S)$ is uniquely determined
by its source and can be reconstructed in $O(mn)$ time. In particular, a
polyomino known to be in a class ${\mathcal{A}}(R,S)$ which has a $1$ in
position $(1,1)$ $($or $(1,n)$ or $(m,1)$ or $(m,n)$$)$ is uniquely
determined.

######  Example 2.2.

If the row and column sum vectors $R$ and $S$ do not have any zeros, then the
only possibility for a source is a 1 in one of the corner positions, and each
such 1 is a source. Let $R=(1,3,4,3,1)$ and $S=(1,2,4,3,2)$. Then the two
matrices

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

both belong to ${\mathcal{C}}(R,S)$ where $A_{1}$ does not have a source but
$A_{2}$ has a NW-source. Thus $A_{2}$ is uniquely constructable from $R$ and
$S$ and its source in position $(5,5)$.

We can define the essential set and ranked essential set for any $m\times n$
$(0,1)$-matrix $A$ as for permutation matrices: For each 1 of $A$ shade (or
cross out) its row to the east and its column to the south (including the 1
itself). This gives the diagram of $A$, defined as the set of unshaded
positions. The essential set of $A$ is the set of southeast corners of the
connected components of the diagram of $A$. In each element of the essential
set put the number of 1’s in the leading submatrix it determines (that is, the
number of $1$’s in northeast submatrix with the specified element of the
essential set in its southeast corner). These corner positions and their
numbers give the ranked essential set.

######  Example 2.3.

Consider the polyomino $A_{2}$ in Example 1.1 with row sum vector
$R=(5,2,2,3,3,1)$ and column sum vector $S=(2,2,5,4,1,1,1)$. Then its ranked
essential set is easily computed to be $\\{(3,2;0),(4,1;0)\\}$. Any convex
matrix in ${\mathcal{C}}(R,S)$ with this ranked essential set equals $A_{2}$;
see below.  $\Box$

We define a Ferrers array $F$ to be a left-justified array of positions where
the number of positions in the rows form a nonincreasing vector $U$. Thus, $F$
is uniquely defined by $U$, and we write $F=F(U)$.

######  Theorem 2.4.

Let $A$ be a polyomino of size $m\times n$. Then the diagram of $A$ is a
Ferrers array F. Its ranked essential set consists of the positions of the
lower right corners of $F$ each filled with a $0$. A polyomino
$A\in{\mathcal{C}}_{m,n}(R,S)$ is uniquely determined by its ranked essential
set.

Proof. Let $A=[a_{ij}]$. Since every row and column contains a 1, there exist
a smallest $i$ and a smallest $j$ such that $a_{i1}=a_{1j}=1$. Also, as $A$ is
connected and convex, the leftmost 1 in the first $i$ rows determine a
northeast rookwise path $P_{1}$ from $(i,1)$ to $(1,j)$ (possibly, it only
consists of $(1,1)$). There is also a smallest $k$ such that $a_{mk}=1$ and a
southeast rookwise path $P_{2}$ from $(i,1)$ to position $(m,k)$. Clearly, the
only positions in $A$ that remain after crossing out the row to the east and
column to the south of the 1’s in $P_{1}\cup P_{2}$ are the positions
northwest of the path $P_{1}$, and these positions form a Ferrers array $F$
and give the diagram of $A$. The lower right corners of $F$ constitute the
essential set of $A$, and the ranked essential set has 0’s in all of these
positions. Thus all the entries of $A$ in the positions of the diagram $F$
equal 0. Moreover, the essential set also determines the diagram $F$. Then
each position in $A$ adjacent to $F$ in a row or column is a 1. Now with
convexity, connectivity, and $R$ and $S$, the remaining positions of $A$ are
determined.

######  Corollary 2.5.

The ranked essential set is an epitope of a polyomino in ${\mathcal{A}}(R,S)$.

######  Corollary 2.6.

The essential set of a polyomino $A$ is empty if and only if $A$ has a SE-
source.

Proof. If the essential set of $A$ is empty, then clearly $A$ has a 1 in
position $(1,1)$ and thus a SE-source. Conversely, assume that $A$ has a SE-
source which is necessarily a 1 in position $(1,1)$. Then the associate
Ferrers array, that is, its essential set is empty.

######  Example 2.7.

Below is the matrix $A_{2}$ from Example 1.1 and its ranked essential set (to
the left); the diagram is the unshaded area constituting a Ferrers array $F$.
The matrix $A_{2}$ is uniquely reconstructed by first putting zeros in all the
positions in the Ferrers array, and then putting ones in all positions
adjacent to $F$. The row and column sums then determine $A_{2}$. Here
$R=(5,2,2,3,3,1)$ and $S=(2,2,5,4,1,1,1)$.

$\left[\begin{array}[]{c|c|c|c|c|c|c}&&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr&&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr&0&\pagecolor[gray]{0.9}\mbox{ }&\pagecolor[gray]{0.9}\mbox{
}&\pagecolor[gray]{0.9}\mbox{ }&\pagecolor[gray]{0.9}\mbox{
}&\pagecolor[gray]{0.9}\mbox{ }\\\ \hline\cr
0&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\\\
\hline\cr\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil&\pagecolor[gray]{0.9}\hfil\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c}0&0&1&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1}\\\
\hline\cr 0&0&1&&&&\\\ \hline\cr 0&0&1&&&&\\\ \hline\cr 0&1&&&&&\\\ \hline\cr
1&&&&&&\\\
\hline\cr&&&&&&\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c}0&0&1&1&1&1&1\\\
\hline\cr 0&0&1&1&&&\\\ \hline\cr 0&0&1&1&&&\\\ \hline\cr 0&1&1&1&&&\\\
\hline\cr 1&1&1&&&&\\\ \hline\cr 1&&&&&&\end{array}\right].$

$\Box$

We define a generalized polyomino to be a convex $m\times n$ $(0,1)$-matrix
without zero rows or zero columns. Thus, in contrast to a polyomino, a
generalized polyomino may not be connected. A generalized polyomino is
obtained from some $k\times k$ permutation matrix by replacing each of its 1’s
by a polyomino. If the 1 in row $i$ of $P$ is replaced by the polyomino
$A_{i}$ $(1\leq i\leq k)$, then we denote this generalized polyomino by
$P(A_{1},A_{2},\ldots,A_{k})$.

######  Example 2.8.

Let

$P=\left[\begin{array}[]{ccc}0&1&0\\\ 0&0&1\\\
1&0&0\end{array}\right],A_{1}=\left[\begin{array}[]{ccc}0&1&1\\\ 1&1&0\\\
1&0&0\end{array}\right],A_{2}=\left[\begin{array}[]{ccc}0&1&1\\\ 1&1&1\\\
1&0&0\end{array}\right],A_{3}=\left[\begin{array}[]{ccc}1&1&1\\\
0&1&1\end{array}\right].$

Then

$P(A_{1},A_{2},A_{3})=\left[\begin{array}[]{ccc||ccc||ccc}&&&0&1&1&&&\\\
&&&1&1&0&&&\\\ &&&1&0&0&&&\\\ \hline\cr\hline\cr&&&&&&0&1&1\\\ &&&&&&1&1&1\\\
&&&&&&1&0&0\\\ \hline\cr\hline\cr 0&1&1&&&&&&\\\
1&1&1&&&&&&\end{array}\right]$

where unspecified entries equal 0.

Our generalized polyomino is an 8-connected $(0,1)$-convex matrix as defined
in [2], but without any zero rows or columns. In the lemma below, for ease of
exposition and subsequent examples, we now consider the diagram of an $m\times
n$ $(0,1)$-matrix $A$ to be an $m\times n$ array (rather than just a subset of
positions of an array) whose unshaded positions are what we called previously
the diagram of $A$; so the diagram is considered as an $m\times n$ array of
positions some of which are unshaded. The following lemma is straightforward
to verify.

######  Lemma 2.9.

The diagram of the generalized polyomino $P(A_{1},A_{2},\ldots,A_{k})$ is
obtained from the diagram of $P$ by replacing its shaded zeros with
appropriately sized shaded arrays, its unshaded zeros with appropriately
unshaded arrays, and its ones with the corresponding diagram of the $A_{i}$’s.

######  Example 2.10.

Continuing with Example 2.8, the diagram of $P(A_{1},A_{2},A_{3})$ and its
ranked essential set is as specified in

$\left[\begin{array}[]{ccc||ccc||ccc}&&&0&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&&\\\
&&&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&\pagecolor[gray]{0.8}X&\\\
&&&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&&\\\
\hline\cr\hline\cr&&&&&&5&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
&&&&\pagecolor[gray]{0.8}X&&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
&&0&&&&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr\hline\cr
0&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&&&&&\\\
\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&\pagecolor[gray]{0.8}X&&&\pagecolor[gray]{0.8}X&\end{array}\right],$

where the shaded $X$’s are matrices of appropriate sizes with all other
positions shaded.

######  Example 2.11.

Consider the generalized polyomino $P(A_{1},A_{2})$, with $P=I_{2}$,
$R=(2,2,2,1,1,2)$, and $S=(2,2,1,4,1)$ given by

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

Bordering the matrix by its row sum vector and column sum vector for visual
ease, we see that the essential set and ranked essential set are specified in

$\left[\begin{array}[]{c||c|c|c|c|c}&2&2&1&4&1\\\ \hline\cr\hline\cr
2&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
2&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
2&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
1&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
1&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&4&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
2&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\end{array}\right].$

We show how $A$ can be constructed from $R$, $S$, and the ranked essential
set. Using convexity and the ranked essential set as determined above, it is
not hard to first get

$\left[\begin{array}[]{c||c|c|c|c|c}&2&2&1&4&1\\\ \hline\cr\hline\cr
2&1&1&0&&\\\ \hline\cr 2&1&1&0&&\\\ \hline\cr 2&0&0&0&&\\\ \hline\cr
1&0&0&0&&\\\ \hline\cr 1&0&0&0&&\\\ \hline\cr 2&&&&&\end{array}\right]\mbox{
and then }\left[\begin{array}[]{c||c|c|c|c|c}&2&2&1&4&1\\\ \hline\cr\hline\cr
2&1&1&0&0&0\\\ \hline\cr 2&1&1&0&0&0\\\ \hline\cr 2&0&0&0&1&1\\\ \hline\cr
1&0&0&0&1&0\\\ \hline\cr 1&0&0&0&1&0\\\ \hline\cr
2&0&0&1&1&0\end{array}\right].$

As another example, the generalized polyomino with specified ranked essential
set given by

$\left[\begin{array}[]{c||c|c|c|c|c|c|c}&1&1&3&2&2&2&1\\\ \hline\cr\hline\cr
1&&&1&&&&\\\ \hline\cr 1&&&1&&&&\\\ \hline\cr 3&1&1&1&&&&\\\ \hline\cr
2&&&&&&1&1\\\ \hline\cr 2&&&&&1&1&\\\ \hline\cr 2&&&&1&1&&\\\ \hline\cr
1&&&&1&&&\end{array}\right]\rightarrow\left[\begin{array}[]{c||c|c|c|c|c|c|c}&1&1&3&2&2&2&1\\\
\hline\cr\hline\cr
1&&&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
1&&0&\pagecolor[gray]{0.8}\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
3&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
2&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&&5&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
2&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&5&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
2&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\\\
\hline\cr
1&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil&\pagecolor[gray]{0.8}\hfil\end{array}\right]$

is readily reconstructable.  $\Box$

We now extend the algorithm given in [8] (for permutation matrices) to
generalized polyominoes. Let $A$ be an $m\times n$ generalized polyomino in
${\mathcal{C}}(R,S)$. We use the entrywise partial order on positions defined
by $(i,j)\leq(k,l)$ provided $i\leq k$ and $j\leq l$.

Algorithm to reconstruct a generalized polyomino in ${\mathcal{C}}(R,S)$

from its ranked essential set

  * 0.

Input: The nonnegative, integral vectors $R$, $S$ (with the same sum) and a
candidate ranked essential set, i.e., some set (possibly empty) of positions
of an $m\times n$ matrix $E$ and a corresponding nonnegative number in each of
these positions, and an $m\times n$ matrix $A$ with all positions initially
empty.

  * 1.

Alternate between applying the following steps below to $E$ and ${A}$ until
either all entries of ${A}$ have been determined, or some entry of ${E}$ in a
position of the essential set has become negative.

    * 1a.

For each position ($i,j)$ in the essential set equal to 0, put a 0 in each
position $(k,l)$ with $(k,l)\leq(i,j)$ and then remove those positions from
further consideration, including the positions of the essential set containing
a 0.

    * 1b.

Put a 1 in a minimal (in the partial order) position $(p,q)$ of ${A}$ and
decrease by 1 the remaining positions $(u,v)$ of the essential set with
$(u,v)\geq(p,q)$. Repeat until all minimal positions have a 1. If a row or
column has the correct sum, fill in the remaining positions of that row or
column with zeros.

  * 2.

If some entry of ${E}$ has become negative, the given set is not a ranked
essential set of a generalized polyomino; otherwise, output ${A}$.

The following theorem generalizes Theorem 2.1.

######  Theorem 2.12.

The function that maps a matrix in $\mathcal{C}_{m,n}(R,S)$ into its ranked
essential set is injective. Moreover, the algorithm above reconstructs
$A\in\mathcal{C}_{m,n}(R,S)$ from its ranked essential set in $O(mn)$ time.

Proof. The proof is by induction on the number $m+n$ of lines. Let $f$ denote
the function defined on $\mathcal{C}_{m,n}(R,S)$ that maps a matrix
$A\in\mathcal{C}_{m,n}(R,S)$ into its ranked essential set $f(A)=E$.

Consider first the case when $E$ is empty. Let $A=[a_{ij}]\in f^{-1}(E)$. Then
$a_{11}=1$ (otherwise $(1,1)$ would be in the diagram and $E$ would be
nonempty), and the first row and column are determined by convexity ($r_{1}$
and $s_{1}$ ones, respectively, followed by zeros). Then the first $r_{1}$
columns and the first $s_{1}$ rows are also determined by convexity. We
continue like this until $A$ is partially determined, uniquely, as a direct
sum $A=A_{1}\oplus A_{2}$. Here $A_{2}$ has smaller size than $A$, and by
induction it is uniquely determined by its ranked essential set, which must be
empty. Therefore $A$ is uniquely determined, i.e., $|f^{-1}(E)|=1$, as
desired. (We see that, in the case of an empty essential set of a generalized
polyomino $A$, the corresponding permutation matrix $P$ is an identity
matrix.)

Next, assume $E$ is nonempty. Let $(k,l)$ be a minimal element in the
entrywise partial order of our ranked essential set and let $r$ be its rank.
We consider two cases, namely $r\geq 1$ and $r=0$.

If $r\geq 1$, then $a_{11}=1$ and we can argue as in the previous paragraph
and uniquely fill in ones and zeros by convexity. Note that each such 1 must
be in some position $(i,j)$ where $i<k$ and $j<l$ because any matrix $A$ with
$E=f(A)$ has zeros in row $k$ and column $l$ up to position $(k,l)$. Therefore
$A$ is a direct sum $A=A_{1}\oplus A_{2}$ and we are done by induction as in
the previous paragraph. Note that the rank associated with each position of
the essential set in the region occupied by $A_{2}$ is reduced by $r$.

Next, consider the case $r=0$. Let $F$ be the set of positions
$(i,j)\leq(p,q)$ for some minimal position $(p,q)$ in the minimal essential
set with rank $0$. Then $F$ is the set of positions of a Ferrers array, and
$a_{ij}=0$ for every $(i,j)\in F$ and every $A=[a_{ij}]\in f^{-1}(E)$. Next,
all the positions adjacent to $F$ are uniquely determined by convexity and
line sums. Then $A$ is a direct sum and we proceed by induction as above. This
proves that the function $f$ is injective, and the first part of the theorem
holds.

The correctness of the algorithm is seen from the arguments above, because the
uniquely determined parts of the matrix are given values as in the algorithm.
So, if $E=f(A)$ for some $A\in\mathcal{C}_{m,n}(R,S)$, the algorithms computes
$A$. If the algorithm stops and does not return any matrix in
$\mathcal{C}_{m,n}(R,S)$, no such matrix exists for the given set $E$. That
the number of steps is $O(mn)$ is clear from the algorithm.

######  Example 2.13.

We apply the algorithm to the generalized polyomino $P(A_{1},A_{2},A_{3})$

$\left[\begin{array}[]{cc|cc|cccc}&&1&1&&&&\\\ &&0&1&&&&\\\ &&0&1&&&&\\\
\hline\cr&&&&0&1&0&0\\\ &&&&1&1&0&0\\\ &&&&0&1&1&1\\\ \hline\cr 0&1&&&&&&\\\
1&1&&&&&&\end{array}\right],\quad\mbox{ where
}P=\left[\begin{array}[]{ccc}0&1&0\\\ 0&0&1\\\ 1&0&0\end{array}\right].$

Note that we do not assume that $P$ is known, only that we are dealing with a
generalized polyomino with known row sum vector $R=(2,1,1,1,2,3,1,2)$ and
known column sum vector $S=(1,2,1,3,1,3,1,1)$. The ranked essential set is
calculated to be as specified in the initial matrix below; now it is
convenient to shade the positions of the essential set $E$. To simplify
things, we superimpose $E$ on $A$, and when a position and rank of the ranked
essential set has been fully taken into account, we remove its shading.

$\left[\begin{array}[]{c|c|c|c|c|c|c|c}&&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1}\\\
\hline\cr&&&&&&\\\ \hline\cr&&&&&&\\\ \hline\cr&&&&\pagecolor[gray]{0.8}4&&\\\
\hline\cr&&&&&&&\\\ \hline\cr&\pagecolor[gray]{0.8}0&&&&&\\\
\hline\cr\pagecolor[gray]{0.8}0&&&&&&\\\
\hline\cr&&&&&&\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1}\\\
\hline\cr 0&0&&&&&&\\\ \hline\cr 0&0&&&&&&\\\ \hline\cr
0&0&&&\pagecolor[gray]{0.8}4&&&\\\ \hline\cr 0&0&&&&&&\\\ \hline\cr
0&0&&&&&&\\\ \hline\cr 0&&&&&&&\\\
\hline\cr&&&&&&&\end{array}\right]\rightarrow$
$\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&&&&&\\\ \hline\cr 0&0&0&&&&&\\\
\hline\cr 0&0&0&&&&&\\\ \hline\cr 0&0&0&&\pagecolor[gray]{0.8}3&&&\\\
\hline\cr 0&0&0&&&&&\\\ \hline\cr 0&0&0&&&&&\\\ \hline\cr 0&1&0&0&0&0&0&0\\\
\hline\cr
1&&0&&&&&\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\
\hline\cr 0&0&0&&&&&\\\ \hline\cr 0&0&0&&&&&\\\ \hline\cr
0&0&0&&\pagecolor[gray]{0.8}2&&&\\\ \hline\cr 0&0&0&&&&&\\\ \hline\cr
0&0&0&&&&&\\\ \hline\cr 0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow$
$\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\ \hline\cr
0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&&&&&\\\ \hline\cr
0&0&0&&\pagecolor[gray]{0.8}1&&&\\\ \hline\cr 0&0&0&&&&&\\\ \hline\cr
0&0&0&&&&&\\\ \hline\cr 0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\
\hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr
0&0&0&0&\pagecolor[gray]{0.8}0&&&\\\ \hline\cr 0&0&0&0&&&&\\\ \hline\cr
0&0&0&0&&&&\\\ \hline\cr 0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow$
$\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\ \hline\cr
0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&0&0&1&0&0\\\
\hline\cr 0&0&0&0&1&&&\\\ \hline\cr 0&0&0&0&0&&&\\\ \hline\cr
0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\
\hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr
0&0&0&0&0&1&0&0\\\ \hline\cr 0&0&0&0&1&&&\\\ \hline\cr 0&0&0&0&0&&&\\\
\hline\cr 0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow$
$\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\ \hline\cr
0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&0&0&1&0&0\\\
\hline\cr 0&0&0&0&1&1&0&0\\\ \hline\cr 0&0&0&0&0&&&\\\ \hline\cr
0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\
\hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr
0&0&0&0&0&1&0&0\\\ \hline\cr 0&0&0&0&1&1&0&0\\\ \hline\cr 0&0&0&0&0&1&&\\\
\hline\cr 0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow$
$\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\ \hline\cr
0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&0&0&1&0&0\\\
\hline\cr 0&0&0&0&1&1&0&0\\\ \hline\cr 0&0&0&0&0&1&1&\\\ \hline\cr
0&1&0&0&0&0&0&0\\\ \hline\cr
1&1&0&0&0&0&0&0\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c|c|c}0&0&1&1&0&0&0&0\\\
\hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&1&0&0&0&0\\\ \hline\cr
0&0&0&0&0&1&0&0\\\ \hline\cr 0&0&0&0&1&1&0&0\\\ \hline\cr 0&0&0&0&0&1&1&1\\\
\hline\cr 0&1&0&0&0&0&0&0\\\ \hline\cr 1&1&0&0&0&0&0&0\end{array}\right]$

Concerning Theorem 2.12 the requirement that the row and column sums are known
is essential. For instance, many different convex matrices have an empty
essential set, e.g., the two matrices where the first has its ones in the
first row, and the second has its ones in the first column. However, then the
row and column sums do not coincide. Also, the algorithm can possibly be made
more efficient in that as soon as one places a 1, then because of convexity,
that row to the east, and that column to the south can be completed knowing
$R$ and $S$.

##  3 Subclasses and characterizations

The well-known Gale-Ryser theorem (see e.g. [3]) says that there is a
$(0,1)$-matrix $A$ with given row sum vector $R$ and column sum vector $S$ if
and only if $S\preceq R^{*}$. Here $\preceq$ denotes majorization order and
$R^{*}$ is the conjugate of $R$. If one also requires that the matrix $A$ is
convex, the situation is much more complicated. In fact (see a previous
remark), it is NP-complete to decide for given $R$ and $S$ if there is a
convex $(0,1)$-matrix with $R$ and $S$ as row and column sum vectors. The same
is true for polyominos (obtained by adding the requirement of connectedness);
see [15] for more on these complexity questions. With this background it is
natural to ask if there are subclasses of $\mathcal{C}_{m,n}(R,S)$ where it is
possible to characterize when the class is nonempty. We study this question in
this section.

First we consider the special case $\mathcal{C}_{m,n}(R,S)$, where $R=e$, the
all 1’s vector of size $m$, and $S=(s_{1},s_{2},\ldots,s_{n})$ is a
nonnegative, integral vector.

######  Lemma 3.1.

The set $\mathcal{C}_{m,n}(e,S)$ is nonempty if and only if
$S=(s_{1},s_{2},\ldots,s_{n})$ satisfies $\sum_{j=1}^{n}s_{j}=m$.

Proof. If $\mathcal{C}_{m,n}(e,S)$ is nonempty, then
$\sum_{j}s_{j}=\sum_{i}r_{i}=m$. Conversely, if this condition holds,
construct the $(0,1)$-matrix $A=[a_{ij}]$ by $a_{11}=\cdots=a_{s_{1},1}=1$,
$a_{s_{1}+1,2}=\cdots=a_{s_{1}+s_{2},2}=1$ etc, while the other entries are
zero. Then $A\in\mathcal{C}_{m,n}(e,S)$.

Therefore, when $R=e$, convexity places no further restriction on the possible
column sum vectors. Similar conclusions hold when $S$ is the all ones vector.

Next, we consider $R=ke=(k,k,\ldots,k)$ for some natural number $k\geq 2$.
Here the situation is different, as the next example shows.

######  Example 3.2.

Let $R=(2,2,2)$ and $S=(3,2,1)$. Then ${\mathcal{C}}(R,S)=\emptyset$, but with
the permutation of $S$ given by $(1,3,2)$ we have the following convex matrix

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

If $R=(3,3,3,3,3)$ and $S=(4,4,3,3,1)$, such a permutation does not exist in
this case, since there are three 1’s in row 1 and three 1’s in row 5, and so
by convexity we must have a column of sum 5.

Let again $R=ke=(k,k,\ldots,k)$ and let $A$ be a $(0,1)$-matrix with row sum
$R$. Then permuting rows of $A$ does not have any effect on row or column
sums, but it may affect convexity as Example 3.2 shows. We do have the
following lemma.

######  Lemma 3.3.

Let $k$ be a positive integer, and let $S$ be a nonnegative integral vector of
length $n$. Then $\mathcal{C}_{m,n}(ke,S)$ is nonempty if and only if there is
a row convex matrix in $\mathcal{A}_{m,n}(ke,S)$.

Proof. Since a convex matrix is also row convex, we only need to prove that if
$\mathcal{A}_{m,n}(R,S)$ contains a row convex matrix $A$, then there is also
a convex matrix in that class. Let $l_{i}$ denote the position of the left-
most 1 in row $i$ of $A$ ($i\leq m$). Reorder rows in $A$ according to
increasing value of $l_{i}$ ($i\leq m$), and let $A^{\prime}$ be the resulting
matrix. Clearly $A^{\prime}$ is row-convex, and it has a staircase pattern,
with $k$ ones in every row. From this one can easily verify that it is also
column convex. Thus $A^{\prime}\in\mathcal{C}_{m,n}(R,S)$, as desired.

Next, we consider the special case $k=2$. The following result characterizes
the possible column sums of convex $m\times n$ $(0,1)$-matrices with two ones
in every row.

######  Theorem 3.4.

Let $S=(s_{1},s_{2},\ldots,s_{n})$ be a nonnegative integral vector. Then
$\mathcal{C}_{m,n}(2e,S)$ is nonempty if and only if $S$ satisfies
$\sum_{j=1}^{n}s_{j}=2m$ and

$\sum_{i=1}^{j}(-1)^{j-i}s_{i}\;\;\;(j=1,2,\ldots,n-1).$ (2)

Proof. Assume that the class $\mathcal{C}_{m,n}(2e,S)$ is nonempty. Then
$\sum_{j}s_{j}=\sum_{i}r_{i}=2m$. Moreover, $\mathcal{C}_{m,n}(2e,S)$ contains
a matrix $A$ with staircase pattern so the position of the leftmost 1 is
weakly increasing by rows. Consequently there are nonnegative integers
$k_{1},k_{2},\ldots,k_{n-1}$ such that the $k_{1}$ first rows has initial 1 in
column 1, the next $k_{2}$ rows has initial 1 in column 2, etc. Since each row
has two consecutive ones the column sums are given by

$s_{j}=k_{j-1}+k_{j}\;\;\;(j=1,2,\ldots,n)$ (3)

where $k_{0}=k_{n}=0$. Therefore $k_{j}=s_{j}-k_{j-1}$ for each $j$ and

$k_{1}=s_{1},\;k_{2}=s_{2}-s_{1},\;k_{3}=s_{3}-k_{2}=s_{3}-s_{2}+s_{1},$

and in general $k_{j}$ is an alternating sign sum of
$s_{1},s_{2},\ldots,s_{j}$

$k_{j}=\sum_{i=1}^{j}(-1)^{j-i}s_{i}\;\;\;(j=1,2,\ldots,n-1).$ (4)

Since all these numbers are nonnegative, we obtain (2). Conversely, assume
$\sum_{j=1}^{n}s_{j}=2m$ and (2) hold, and define $k_{j}$ ($j\leq n-1$) by
(4). Then $k_{j}\geq 0$ ($j\leq n-1$) and, also, (3) holds. So, if we
construct a staircase matrix $A$ based on the $k_{j}$’s as above, this matrix
will be in $\mathcal{C}_{m,n}(2e,S)$ as $\sum_{j=1}^{n}s_{j}=2m$, and the
proof is complete.

######  Example 3.5.

Let $k=2$ and $S=(3,2,1)$. In Example 3.2 we saw that
$\mathcal{C}_{3,3}(2e,S)$ is empty. In fact, the inequalities in (2) are

$s_{1}\geq 0,\;\;s_{2}-s_{1}\geq 0,\;\;s_{3}-s_{2}+s_{1}\geq 0$

and the second inequality is violated: $2-3=-1\not\geq 0$. If, however,
$S=(1,3,2)$, then all these inequalities hold, and the matrix

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

lies in $\mathcal{C}_{3,3}(2e,S)$. Here $k_{1}=1$, $k_{2}=2$ and $k_{3}=0$.

The next result deals with convex matrices with both equal row sums and equal
column sums.

######  Theorem 3.6.

Let $k\leq m$, $l\leq n$ be positive integers. The class
$\mathcal{C}_{m,n}(ke,le)$ is nonempty if and only if $m=pk$ and $n=pl$ for
some integer $p$.

Proof. Assume that $m=pk$ and $n=pl$ for an integer $p$. Then the matrix
(direct sum)

$A=J_{k,l}\oplus J_{k,l}\oplus\cdots\oplus J_{k,l}$

where $J_{k,l}$ occurs $p$ times, lies in $\mathcal{C}_{m,n}(ke,le)$. Next,
assume that $A=[a_{ij}]$ lies in $\mathcal{C}_{m,n}(ke,le)$. Consider $i$
minimal such that $a_{i1}=1$. By convexity,

$a_{i1}=a_{i+1,1}=\cdots=a_{i+k-1,1}=1.$

Therefore, again by convexity, the $k\times l$ submatrix of $A$ containing
rows $i,i+1,\ldots,i+k-1$ and columns $1,2,\ldots,l$ equals $J_{k,l}$. The
remaining entries in these $k$ rows, and in these $l$ columns, are zero. So,
deleting these $k$ rows and $l$ columns, we can repeat this argument. After
identifying $\min\\{\lfloor m/k\rfloor,\lfloor n/l\rfloor\\}$ such submatrices
$J_{k}$ (that do not have any lines in common), we are left with a submatrix
with either fewer rows than $k$ or fewer columns than $l$. The only
possibility is that there are no rows and no columns left, otherwise it would
contradict that $A\in\mathcal{C}_{m,n}(ke,le)$. We conclude that $m/k=n/l$
must be an integer, as desired.

Moreover, from the proof above, we see that when $m=pk$, $n=pl$

$\mathcal{C}_{m,n}(ke,le)=\\{P\otimes J_{k,l}:\mbox{$P$ is a permutation
matrix of order $p$}\\}$

where $\otimes$ denotes Kronecker product. Thus,
$|\mathcal{C}_{m,n}(ke,le)|=p!$.

We now consider a special, but natural, class of convex matrices. We define a
Ferrers matrix to be a $(0,1)$-matrix the positions of whose 1’s form a
Ferrers array. Let $m_{1},m_{2},n_{1},n_{2}$ be positive integers and consider
a matrix

$A=\left[\begin{array}[]{c|c}A_{11}&A_{12}\\\ \hline\cr A_{21}&A_{22}\\\
\end{array}\right]$ (5)

where $A_{22}$, $A_{12}$, $A_{21}$, $A_{11}$ are matrices obtained by rotation
of some (possibly different) Ferrers matrices $0$, $90$, $180$ and $270$
degrees counter clockwise, respectively, where $A_{11}$ has size $m_{1}\times
n_{1}$ and $A_{22}$ has size $m_{2}\times n_{2}$, thereby determining the
sizes of the other two matrices. We call $A$ a Ferrers-convex matrix. Let
$R(A_{ij})$ be the row sum vector and $R^{\prime}(A_{ij})$ be the column sum
vector of $A_{ij}$ ($i,j\leq 2$). Then $R^{\prime}(A_{ij})$ is the conjugate
of $R(A_{ij})$, but with the components in the reverse order for $A_{11}$ and
$A_{21}$. Then clearly the row sum and column sum vectors of $A$ are given by

$\begin{array}[]{ll}\vspace{0.1cm}R(A)=(R(A_{11})+R(A_{12}),R(A_{21})+R(A_{22})),\\\
S(A)=(R^{\prime}(A_{11})+R^{\prime}(A_{21}),R^{\prime}(A_{21})+R^{\prime}(A_{22})).\end{array}$

######  Example 3.7.

An example of a Ferrers-convex matrix of size $9\times 7$ is

$A=\left[\begin{array}[]{cccc|ccccc}&&&1&&&&&\\\ &&1&1&1&&&&\\\
&&1&1&1&1&&&\\\ 1&1&1&1&1&1&1&\\\ \hline\cr&1&1&1&1&1&1&1&1\\\ &&&1&1&&&\\\
&&&1&&&&&\\\ \end{array}\right].$

######  Lemma 3.8.

Every Ferrers-convex matrix is convex and has unimodal row and column sum
vectors.

Proof. Consider $A$ as in (5). Then the ones in each row are consecutive since
the ones in $A_{11}$ and $A_{21}$ are right-justified, and the ones in
$A_{12}$ and $A_{22}$ are left-justified. Similarly, the ones are
consecutively in each column. Thus, $A$ is convex. Moreover, from the Ferrers
property, the row sums are nondecreasing in the first $m_{1}$ rows, and
nonincreasing in the last $m_{2}$ rows, so the row sum vector is unimodal. For
similar reasons the column sum vector is unimodal.

Thus, Ferrers-convex matrices form a large class of convex matrices obtained
from all possible partitions of four integers being the number of ones in each
of the four submatrices in (5).

######  Example 3.9.

Let $A_{n}=[a_{ij}]$ be the $(0,1)$-matrix of order $n$ with 1’s on the
diagonal and superdiagonal, i.e., $a_{ij}=1$ when $i\leq j\leq i+1$ ($i<n$)
and $a_{nn}=1$. For instance,

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

Then, for each $n$, $A_{n}$ is connected, convex and unimodal, as
$R(A_{n})=(2,2,\ldots,2,1)$ and $S(A_{n})=(1,2,2,\ldots,2)$. However, one can
easily check that $A_{n}$ is not Ferrers-convex. Thus, a converse of Lemma 3.8
does not hold.

Even Ferrers-convex matrices are not uniquely determined by their row and
column sum, as Example

$\left[\begin{array}[]{cc}1&0\\\ 1&1\\\ 0&1\end{array}\right]\mbox{ and
}\left[\begin{array}[]{cc}0&1\\\ 1&1\\\ 1&0\end{array}\right].$

with $R=(1,2,1)$ and $S=(2,2)$ shows.

##  4 Interchanges and convex-classes

We continue to investigate convex matrices, but now with a focus on
interchanges and preservation of convexity.

Let $J_{k,l}$ as usual be the $k\times l$ all ones matrix. Let $J^{1}_{k,l}$
be obtained from $J_{k,l}$ by replacing each of the ones in positions $(1,1)$
and $(k,l)$ by a zero. Similarly, let $J^{2}_{k,l}$ be obtained from $J_{k,l}$
by replacing each of the ones in positions $(1,l)$ and $(k,1)$ by a zero. Note
that an interchange in $J^{1}_{k,l}$ involving the first and last row and
column gives $J^{2}_{k,l}$.

######  Proposition 4.1.

Let $A\in\mathcal{C}_{m,n}$ be such that each row and column sum is at least
$2$. Then $A$ permits an interchange into another matrix $B$ in
$\mathcal{C}_{m,n}$ if and only if $A$ has the form

$A=\left[\begin{array}[]{ccc}A_{11}&A_{12}&A_{13}\\\ A_{21}&A_{22}&A_{23}\\\
A_{11}&A_{32}&A_{33}\\\ \end{array}\right]$ (6)

where $(i)$ $A_{22}$ equals either $J^{1}_{k,l}$ or $J^{2}_{k,l}$ for some
$k,l$, and $(ii)$ the first and last row of $A_{21}$ and $A_{23}$ are zero,
and $(iii)$ the first and last column of $A_{12}$ and $A_{32}$ are zero.

Proof. Let $A$ be as in (6) with the block matrices as stated in the theorem
where $A_{22}=J^{1}_{k,l}$. Then we may apply an interchange in $A$ involving
the first and last row and column of $A_{22}$. The resulting matrix $B$ is as
$A$ except that the block $A_{22}$ is replaced by $J^{2}_{k,l}$. The zeros
described in conditions (ii) and (iii) assure that $B$ is a convex matrix.

We shall prove the converse. In a convex matrix the ones in every line (row or
column) are consecutive, and those positions form an interval. The following
observation follows from the assumption that each line sum is at least 2.

  * •

If an interchange in a convex matrix results in another convex matrix, then in
each of the four modified lines the interval is changed by shifting the
interval one position.

Assume now that $A$ permits an interchange into another matrix $B$ in
$\mathcal{C}_{m,n}$. We can partition $A$ as in (6) such that the interchange
involves the first and last rows and columns of the submatrix $A_{22}$. By
symmetry we may assume that $A_{22}$ has zeros on the upper right and the
lower left corner positions. Then, by the observation above, all entries in
the first and last row and column of $A_{22}$ are 1, except the two mentioned
zeros. Convexity then implies that the remaining entries in $A_{22}$ are 1, so
$A_{22}=J^{1}_{k,l}$. This proves the converse.

Let $R=(r_{1},r_{2},\ldots,r_{m})$ and $S=(s_{1},s_{2},\ldots,s_{n})$. The
class ${\mathcal{A}}(R,S)$ is a convex-class provided every matrix in
${\mathcal{A}}(R,S)$ is convex, that is,
${\mathcal{A}}(R,S)={\mathcal{C}}(R,S)$. Consider a convex-class
$\mathcal{A}(R,S)$ and let $A=[a_{ij}]\in\mathcal{A}(R,S)$. Let $i\leq m$ and
consider $I=\\{j:a_{ij}=1\\}$ which we call a horizontal interval. Similarly,
we have the vertical interval  $\\{i:a_{ij}=1\\}$ for each $j$. If
$I,I^{\prime}$ are two horizontal intervals of the form
$I=\\{k,k+1,\ldots,l\\}$ and $I^{\prime}=\\{k+1,k+2,\ldots,l+1\\}$ for some
$k<l$ (so, in particular, $|I|=|I^{\prime}|$), we say that $I^{\prime}$ is a
$1$-shift of $I$, and vice versa. We also say that $I,I^{\prime}$ is a 1-shift
pair. A similar notion applies to vertical intervals. All intervals are
nonempty as there are no zero lines. The next result establishes very strong
requirements on the structure of matrices in a convex-class, requiring
$m\choose 2$ pairwise comparisons of rows and $n\choose 2$ pairwise
comparisons of columns.

######  Theorem 4.2.

Assume that $\mathcal{A}(R,S)$ is a convex-class, and let
$A\in\mathcal{A}(R,S)$. Let $I$ and $I^{\prime}$ be horizontal intervals
associated with different rows of $A$. Then $($at least$)$ one of the
following holds:

$(i)$ $|I|=|I^{\prime}|=1$;

$(ii)$ $I\subseteq I^{\prime}$ or $I^{\prime}\subseteq I$;

$(iii)$ $I^{\prime}$ is a $1$-shift of $I$.

In particular, if for some $k\geq 1$, $|I|=k$ and $|I^{\prime}|\geq k+1$, then
$I\subseteq I^{\prime}$.

Similar properties hold for the vertical intervals. Moreover, every
interchange in $\mathcal{A}(R,S)$ either takes place in two rows $($or
columns$)$ with a single $1$, or two rows $($or columns$)$ corresponding to a
$1$-shift pair.

Proof. First note that the conditions (i), (ii), and (iii) imply that if
$|I|=|I^{\prime}|=1$ and $I\neq I^{\prime}$, then $I=\\{k\\}$ and
$I^{\prime}=\\{k+1\\}$ for some $k$; also, if two horizontal intervals or two
vertical intervals are disjoint, then they both contain exactly one element.

We assume that (i) and (ii) do not hold and prove (iii) holds. Let
$I=\\{i,i+1,\ldots,k\\}$ and
$I^{\prime}=\\{i^{\prime},i^{\prime}+1,\ldots,k^{\prime}\\}$ where we may
assume $i<i^{\prime}$, since by symmetry, we may take $i\leq i^{\prime}$, and
if $i=i^{\prime}$, (ii) would be violated. Then $k<k^{\prime}$, due to (ii).
Moreover, $A$ contains ones in the positions corresponding to $i$ in $I$ (that
is, the row associated with $I$ and column $i$) and to $k^{\prime}$ in
$I^{\prime}$ (the row associated with $I^{\prime}$ and column $k^{\prime}$).
Therefore we can make an interchange in $A$ involving these two ones (as the
other two positions involved contain zeros). Let $A^{\prime}$ be the resulting
matrix. However, $A^{\prime}$ has consecutive ones in these two rows if and
only if $i^{\prime}=i+1$ and $k^{\prime}=k+1$, i.e., when $I^{\prime}$ is a
$1$-shift of $I$. Here we used that at least one of the intervals $I$ and
$I^{\prime}$ contains more than one element. Thus (iii) holds. Clearly, a
similar arguments applies to column intervals.

The last statement of the theorem follows from the first part as the two rows
of the interchange cannot be of type (ii).

######  Example 4.3.

Let $R=(2,3,3)$ and $S=(2,3,2,1)$. The matrix

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

is a convex matrix in ${\mathcal{A}}(R,S)$, but rows 1 and 3, and columns 1
and 4 do not satisfy the conditions in Theorem 4.2, and indeed an interchange
replaces $A$ with a non-convex matrix.

Now suppose that $R=(2,1,2)$ and $S=(3,1)$. Then the matrix in
${\mathcal{A}}(R,S)$

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

satisfies (i), (ii), and (iii) of Theorem 4.2 but is not convex, and so
${\mathcal{A}}(R,S)$ is not a convex class.  $\Box$

Concerning the structure of convex-classes an interesting special case is when
$r_{i}=n$ for some $i$; we then say that row $i$ is full. Let
$A\in\mathcal{A}(R,S)$. Then convexity implies that the full rows are
consecutive, say in rows $p,p+1,\ldots,p^{\prime}$ and the remaining intervals
above and below are nested:

$I_{1}\subseteq I_{2}\subseteq\cdots\subseteq
I_{p}=\\{1,2,\ldots,n\\}=\cdots=I_{p^{\prime}}\supseteq
I_{p^{\prime}+1}\supseteq\cdots\supseteq I_{m}$

where $I_{i}$ is the interval associated with row $i$ ($i\leq m$). The
previous theorem may be used to construct convex-classes, as the next example
illustrates.

######  Example 4.4.

Let $R=(1,4,6,4,1)$ and $S=(1,2,4,4,3,2)$, and the following convex matrix in
$\mathcal{A}(R,S)$

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

The interval in row 4 is a 1-shift of the interval in row 2. An interchange in
these two rows and columns 2 and 5 gives the convex matrix

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

The first and last rows each have only one 1 and they permit an interchange
using columns 3 and 4. The ones involved in these interchanges are indicated
in boldface. All these 4 matrices constructed from these interchanges are
convex, and there are no other matrices in $\mathcal{A}(R,S)$, so this is a
convex class.

We now generalize this example and construct a family of convex-classes. This
is done by selecting intervals (consecutive integers) with a certain property
and then embedding these as the row intervals in a matrix.

Algorithm to construct a convex-class $\mathcal{A}(R,S)$

  * 1.

Choose a 1-shift pair $I_{1},I^{\prime}_{1}$.

  * 2.

for $i=2,3,\ldots,k$
Choose a 1-shift pair $I_{i},I^{\prime}_{i}$ such that $I_{i}\cap
I^{\prime}_{i}\supseteq I_{i-1}\cup I^{\prime}_{i-1}$.

  * 3.

Construct the matrix $A$ with $2k$ rows corresponding to these intervals:
$I_{1}$ and $I^{\prime}_{1}$ are the first and last row, $I_{2}$ and
$I^{\prime}_{2}$ are the second and second last row etc. Do this in such a way
that $A$ has no zero columns.

We obtain the following result.

######  Corollary 4.5.

The algorithm constructs a convex-class $\mathcal{A}(R,S)$ consisting of
$2^{k}$ matrices.

Proof. First, the constructed matrix is convex: it is clearly row-convex, and
the condition $I_{i}\cap I^{\prime}_{i}\supseteq I_{i-1}\cup I^{\prime}_{i-1}$
assures that it is also column-convex. Next, no interchange is possible for
two rows when one interval is contained in the other. Therefore, the only
possible interchanges are for each of the pairs $I_{i},I^{\prime}_{i}$ ($i\leq
k$). Each of these gives a new convex matrix, due to mentioned intersection
condition, and these interchanges are “independent”, so that the class
consists of $2^{k}$ matrices.

It would be of interest to characterize the pairs $R,S$ for which there is a
unique convex matrix in ${\mathcal{A}}(R,S)$, that is, for which
$|{\mathcal{C}}(R,S)|=1$.

##  5 A Partially Ordered Set

Consider the partially ordered set $({\mathcal{C}}_{m,n},\leq)$ of all
$m\times n$ convex matrices with the entrywise partial order. Starting with a
connected matrix $C\in{\mathcal{C}}_{m,n}$, we can sequentially change 0’s to
1’s, one 0 at a time, in such a way that we obtain $J_{m,n}$ with all
intermediary matrices convex. If $C$ is not connected, then by applying this
procedure to each connected component of $C$, we can first arrive at a convex
matrix of the form $P(J_{m_{1},n_{1}},\ldots,J_{m_{p},n_{p}})$ for some
$p\times p$ permutation matrix $P$, and then sequentially change 0’s to 1’s
with all resulting matrices convex and arrive at $J_{m,n}$. In a similar way,
starting with any convex matrix $A\in{\mathcal{C}}_{m,n}$, we can sequentially
change 1’s to 0’s and arrive at the zero matrix $O_{m,n}$ with all
intermediary matrices convex.

It follows that maximal chains in $({\mathcal{C}}_{m,n},\leq)$ have length
$mn$ (i.e., contain $(mn+1)$ matrices) and every $C\in{\mathcal{C}}_{m,n}$
belongs to a maximal chain. Also if $C_{1}$ and $C_{2}$ are in
${\mathcal{C}}_{m,n}$, then $C_{2}$ covers  $C_{1}$ provided $C_{1}\leq C_{2}$
and the number of 1’s in $C_{2}$ is one more than the number of 1’s in
$C_{1}$. If $C_{1},C_{2}\in{\mathcal{C}}_{m,n}$, then the intersection
$C_{1}\wedge C_{2}$ of $C_{1}$ and $C_{2}$ is the $m\times n$ $(0,1)$-matrix
$C_{1}\wedge C_{2}$ which has 1’s in exactly those places where both $C_{1}$
and $C_{2}$ have 1’s.

######  Lemma 5.1.

If $C_{1},C_{2}\in{\mathcal{C}}_{m,n}$, then $C_{1}\wedge
C_{2}\in{\mathcal{C}}_{m,n}$ and $C_{1}\wedge C_{2}$ is the meet $($i.e.,
GLB$)$ of $C_{1}$ and $C_{2}$ in ${\mathcal{C}}_{m,n}$.

Proof. Suppose, e.g., there are two 1’s in a row of $C_{1}\wedge C_{2}$. Then
in between these 1’s there are only 1’s in $C_{1}$ and $C_{2}$. It follows
that $C_{1}\wedge C_{2}$ is a convex matrix and is the meet of $C_{1}$ and
$C_{2}$.

######  Theorem 5.2.

The partially ordered set $({\mathcal{C}}_{m,n},\leq)$ is a lattice.

Proof. Since ${\mathcal{C}}_{m,n}$ is a finite set with a meet, then every two
convex matrices $C_{1}$ and $C_{2}$ in ${\mathcal{C}}_{m,n}$ have a join
$C_{1}\vee C_{2}$ (i.e., LUB), namely the meet of all the matrices
$X\in{\mathcal{C}}_{m,n}$ with $C_{1},C_{2}\leq X$.

Let $A$ be an arbitrary $(0,1)$-matrix of size $m\times n$. We define the
convex hull $\overline{A}^{c}$ of $A$ to be the meet of all the convex sets
$C$ in $({\mathcal{C}}_{m,n},\leq)$ such that $A\leq C$. The convex hull
$\overline{A}^{c}$ of $A$ is obtained by replacing every 0 between two 1’s
with a 1, repeatedly, until one obtains a convex matrix.

######  Example 5.3.

A matrix $A$ and its convex closure $\overline{A}^{c}$ are illustrated below:

$A=\left[\begin{array}[]{c|c|c|c}1&1&&\\\ \hline\cr 1&&&1\\\ \hline\cr&&1&1\\\
\hline\cr&&&\end{array}\right],\quad\overline{A}^{c}=\left[\begin{array}[]{c|c|c|c}1&1&&\\\
\hline\cr 1&1&1&1\\\ \hline\cr&&1&1\\\ \hline\cr&&&\end{array}\right].$

The essential set of a convex matrix was defined relative to the southeast
(SE) and so it is more appropriately called the SE-essential set. It could
just as well have been defined relative to the other three possible
directions: the SW-essential set, NE-essential set, and NW-essential set. For
a convex matrix $C\in{\mathcal{C}}_{m,n}$, let ${\mathcal{E}}(A)$ be the union
of these four essential sets. A specific one of these essential sets is empty
exactly when there is a 1 in the oppositely directed corner. Thus
${\mathcal{E}}(C)=\emptyset$ if and only if there is a 1 in each of the four
corners of $C$, and since $C$ is convex, if and only if $C=J_{m,n}$.

We have the following theorem.

######  Theorem 5.4.

Let $C\in{\mathcal{C}}(m,n)$. Then $C^{\prime}\in{\mathcal{C}}_{m,n}$ covers
$C$ in $({\mathcal{C}}_{m,n},\leq)$ if and only if $C^{\prime}$ is obtained
from $C$ by replacing the $0$ in some position of ${\mathcal{E}}(C)$ with a
$1$. In particular, the number of convex matrices in ${\mathcal{C}}_{m,n}$
that cover $C$ equals $|{\mathcal{E}}(C)|$.

Proof. A position belongs to ${\mathcal{E}}(C)$ if and only if it is occupied
by a 0, and there is a 1 opposite it in the two positions S and E, N and E, N
and W, or S and W. These are exactly the positions corresponding to the four
essential sets.

######  Example 5.5.

Consider the convex matrix

$C=\left[\begin{array}[]{c|c|c|c|c|c}&&&1&1&1\\\ \hline\cr&&1&1&1&\\\
\hline\cr&&1&1&&\\\ \hline\cr&1&1&1&&\\\ \hline\cr 1&1&1&&&\\\
\hline\cr&&1&&&\end{array}\right]\rightarrow\left[\begin{array}[]{c|c|c|c|c|c}&&a&1&1&1\\\
\hline\cr&&1&1&1&c\\\ \hline\cr&a&1&1&c&\\\ \hline\cr a&1&1&1&&\\\ \hline\cr
1&1&1&c&&\\\ \hline\cr&b&1&&&\end{array}\right],$

where $a$ denotes a position in the SE-essential set, $b$ denotes a position
in the NE-essential set, and $c$ denotes a position in the NW-essential set.
The SW-essential set is empty. Then it is easy to check that these positions
in ${\mathcal{E}}(C)$ are those and only those positions in which a 1 can be
inserted to get a convex set.  $\Box$

It is natural to ask whether $({\mathcal{C}}_{m,n},\leq)$ is a distributive
lattice, that is, whether

$C_{1}\vee(C_{2}\wedge C_{3})=(C_{1}\vee C_{2})\wedge(C_{1}\vee C_{3}).$

That this need not hold is already seen with the simple example

$C_{1}=\left[\begin{array}[]{c|c|c}1&0&0\end{array}\right],C_{2}=\left[\begin{array}[]{c|c|c}0&1&0\end{array}\right],C_{3}=\left[\begin{array}[]{c|c|c}0&0&1\end{array}\right],$

where

$C_{1}\vee(C_{2}\wedge
C_{3})=\left[\begin{array}[]{c|c|c}1&0&0\end{array}\right]\mbox{ and
}(C_{1}\vee C_{2})\wedge(C_{1}\vee
C_{3})=\left[\begin{array}[]{c|c|c}1&1&0\end{array}\right].$

## References

  * [1] A. Alpers, P. Gritzmann, Reconstructing binary matrices under window constraints from their row and column sums, Fund. Inform., 155 (2017), no. 4, 321–340.
  * [2] P. Balázs, Decomposition algorithms for reconstructing discrete sets with disjoint components, in Advances in Discrete Tomography and its Applications, G.T. Herman and A. Kuba eds., Birkha̋user, 2007, 153–173.
  * [3] R.A. Brualdi, H.J. Ryser,  Combinatorial Matrix Theory,  Encyclopedia of Mathematics, Cambridge University Press, 1991.
  * [4] R.A. Brualdi, G. Dahl, Matrices of zeros and ones with given line sums and a zero block. Proceedings of the Workshop on Discrete Tomography and its Applications, 83–97, Electron. Notes Discrete Math., 20, Elsevier Sci. B. V., Amsterdam, 2005.
  * [5] G. Dahl, T. Flatberg, Optimization and reconstruction of $hv$-convex $(0,1)$-matrices, Discrete Applied Mathematics 151 (2005), 93 –105.
  * [6] J. Engbers, A. Hammett, On comparability of bigrassmannian permutations¡ Australasian J. Combinatorics, 71 (1) (2018), 121-152.
  * [7] K. Eriksson, S. Linusson, The size of Fulton’s essential set, Electron. J. Combinatorics., 2 (1995) # R6.
  * [8] K. Eriksson, S. Linusson, Combinatorics of Fulton’s essential set, Duke Math. J., 85 (1996), 61–76.
  * [9] W. Fulton, Flags, Schubert polynomials, degeneracy loci, and determinantal formulas, Duke Math. J., 65 , 381–420 (1992).
  * [10] M. Kobayashi, Bijection between bigrassmanniagn permutations maximal below a permutation and its essential set, Electron. J. Combinatorics. 17 (2010), no.1, #N27.
  * [11] M. Kobayashi, Enumeration of bigrassmannian permutations below a permutation in Bruhat order, Order 28 (1), (2011). 131–137.
  * [12] M. Kobayashi, $3412,4231$ patterns produce singular points of essential sets, Saitama Math. J. 28 (2011), 13–23.
  * [13] M. Kobayashi, More combinatorics of Fulton’s essential set, Int. Math. Forum, 8 (2013), 1735–1760.
  * [14] A. Kuba, E. Balogh, Reconstruction of convex 2D discrete sets in polynomial time, Theor. Comput. Sci., 283 (2002), 223–242.
  * [15] G.J. Woeginger, The reconstruction of polyominoes from their orthogonal projections, Inform. Process. Lett., 77 (2001), 225–229.