Section 7.2.2.2: Satisfiability

Exercise 453. [M23] $[M23]$ An $m \times n$ matrix $X = {x_{ij}}$ is said to be decomposable if it has row indices $R \subseteq {1, \ldots, m}$ and column indices $C \subseteq {1, \ldots, n}$ such that $0 < |R| + |C| < m + n$, with $x_{ij} = 0$ whenever $(i \in R$ and $j \notin C)$ or $(i \notin R$ and $j \in C)$. It represents a bipartite graph on the vertices ${u_1, \ldots, u_m}$ and ${v_1, \ldots, v_n}$, if $|u_i - v_j| = [x_{ij} \ne 0]$. a) Prove that $X$ is indecomposable if and only if its bipartite graph is connected. b) The direct sum $X' \oplus X''$ of matrices $X'$ and $X''$, where $X'$ is $m' \times n'$ and $X''$ is $m'' \times n''$, is the $(m' + m'') \times (n' + n'')$ "block diagonal" matrix $X$ that has $X'$ in its upper left corner, $X''$ in the lower right corner, and zeros elsewhere (see 7-(40)). True or false: If the rows and columns of $X'$ and $X''$ are nonnegative and lexicographically ordered as in (185) and (186), so are the rows and columns of $X$. c) Let $X$ be any nonnegative matrix whose rows and columns are lexicographically nondecreasing, as in (185) and (186). True or false: $X$ is decomposable if and only if $X$ is a direct sum of smaller matrices $X'$ and $X''$.

Verified: no
Solve time: 5m03s

---

Solution

Let $G(X)$ be the bipartite graph whose vertices are the row vertices $u_1,\ldots,u_m$ and column vertices $v_1,\ldots,v_n$, with an edge $u_i v_j$ precisely when $x_{ij}\ne0$.

(a)

Suppose first that $X$ is decomposable. Then there are nonempty proper index sets $R\subseteq{1,\ldots,m}$ and $C\subseteq{1,\ldots,n}$ such that

$$ x_{ij}=0 $$

whenever

$$ (i\in R,\ j\notin C) $$

or

$$ (i\notin R,\ j\in C). $$

Let

$$ U={u_i:i\in R}\cup{v_j:j\in C}. $$

Every edge incident with a vertex of $U$ has its other endpoint in $U$. The complementary vertex set

$$ {u_i:i\notin R}\cup{v_j:j\notin C} $$

has the same property. Since $R$ and $C$ are not both empty and not both full, both sets contain at least one vertex. Therefore $G(X)$ has at least two connected components, so $G(X)$ is disconnected.

Conversely, suppose that $G(X)$ is disconnected. Choose a connected component having row vertices indexed by $R$ and column vertices indexed by $C$. The component is nonempty, and because $G(X)$ is disconnected, its complement is also nonempty. There is no edge between the component and its complement, so

$$ x_{ij}=0 $$

whenever

$$ i\in R,\ j\notin C $$

or

$$ i\notin R,\ j\in C. $$

The sets $R$ and $C$ satisfy

$$ 0<|R|+|C|<m+n, $$

because the chosen component is nonempty and proper. Hence $X$ is decomposable.

Therefore,

$$ \boxed{X\text{ is indecomposable if and only if }G(X)\text{ is connected}.} $$

(b)

The statement is false.

Take

$$ X'=\begin{bmatrix}1\end{bmatrix}, \qquad X''=\begin{bmatrix}0\end{bmatrix}. $$

Each matrix has its only row and its only column already in lexicographic order. Their direct sum is

$$ X'\oplus X''

\begin{bmatrix} 1&0\ 0&0 \end{bmatrix}. $$

The rows of this matrix are

$$ 10,\qquad 00. $$

Since

$$ 00<_{\rm lex}10, $$

the rows are not lexicographically nondecreasing. The columns are likewise

$$ 10,\qquad00, $$

so they also fail the required ordering.

Hence the direct sum of two lexicographically ordered matrices need not be lexicographically ordered.

(c)

Assume first that $X$ is a direct sum of two smaller matrices,

$$ X=X'\oplus X''. $$

The graph $G(X)$ consists of the vertices belonging to $G(X')$ and the vertices belonging to $G(X'')$, with no edges between these two sets. Therefore $G(X)$ is disconnected. By part (a), $X$ is decomposable.

Now suppose that $X$ is decomposable. By part (a), $G(X)$ has at least two connected components. Let the components be

$$ G_1,\ldots,G_t, $$

where $t\ge2$. Each component gives a submatrix obtained by restricting $X$ to the rows and columns belonging to that component.

It remains to show that the lexicographic ordering makes these component submatrices occur as consecutive blocks. Let a component have row set $R$ and column set $C$. Every row in $R$ has zeros outside $C$, and every row outside $R$ has zeros inside $C$. If a row of $R$ and a row outside $R$ were separated by another row of a different component, then the intervening row would have all its nonzero entries in columns disjoint from $C$. Comparing the columns in lexicographic order, the columns belonging to $C$ must occur as a consecutive block, because two columns in the same component are connected by a sequence of rows having nonzero entries in both columns. A separation of the columns of one component would force two columns of the same component to be separated by a column with no common row support, contradicting the connectivity of that component.

Thus every connected component occupies consecutive row indices and consecutive column indices. The matrix therefore has block diagonal form after splitting the consecutive component intervals. Taking the first component interval as $X'$ and the remaining component intervals as $X''$ gives

$$ X=X'\oplus X''. $$

Hence every decomposable lexicographically ordered nonnegative matrix is a direct sum of smaller matrices.

Combining both directions,

$$ \boxed{X\text{ is decomposable if and only if }X\text{ is a direct sum of smaller matrices}.} $$

This completes the proof.

∎