Problem 7.20: How large can a gap $\SUM{A}/\SUM{\oA}$ be?Our goal is to show that there are $n\times n$ matrices $A$ with \[ \SUM{A}/\SUM{\overline{A}}\Geq n^{1/4-o(1)}\,. \] For this, we use known rank separation results and complexity bounds for Kronecker products of matrices. Recall that the Kronecker product $A\otimes B$ of two $m\times m$ matrices $A$ and $B$ is the $m^2\times m^2$ matrix obtained by replacing each $1$-entry of $A$ with a copy of the matrix $B$, and by replacing each $0$-entry of $A$ with the $m\times m$ all-$0$ matrix. Also recall that SUM-rank of a matrix $A$, denoted by $\pr{A}$ (known also as the partition number) is a minimal number of disjoint rectangles covering all $1$s in $A$; a rectangle is an all-$1$ submatrix of $A$.
Theorem 1: There exists an $m\times m$ matrix $B$ such that for every $m\times m$ matrix $A$, \[ \pr{A} \cdot \frac{m^2}{\log^2 m}\Leq \SUM{A\otimes B}\Leq \pr{A} \cdot \frac{m^2}{\log m}\,. \qquad\qquad(1) \]Proof: Find et al. [2] showed that $ \SUM{A \otimes B} \preceq \pr{A} \cdot m^2 / \log m$ holds for any $m \times m$ matrices $A$ and $B$, and that if $B$ is $t$-free, then also the lower bound $\SUM{A \otimes B} \succeq \pr{A} \cdot |B| / t^2$ holds; recall that a matrix is $t$-free if it has no $(t+1)\times (t+1)$ all-$1$ submatrices. For a random $m \times m$ matrix $B$, we have $|B| \asymp m^2$ and $t \asymp \log m$. Therefore, for Kronecker products with such matrices, these bounds directly imply the bounds in (1). $\Box$
Corollary 1: There exists an $m\times m$ matrix $B$ such that for every $m\times m$ matrix $A$, \[ \frac{\SUM{A\otimes B}}{\SUM{\overline{A\otimes B}}}\Geq \frac{1}{\log m}\cdot \frac{\pr{A}}{\pr{\oA}}\,. \qquad\qquad(2) \]Proof: Let $B$ be an $m\times m$ matrix guaranteed by Theorem 1. The complement of the matrix $A\otimes B$ is $\overline{A \otimes B} = J \otimes \oB + \oA \otimes B$, where $J$ denotes the all-1s $m\times m$ matrix. By Lupanov's bound [3, Theorem 2.2], we have $\SUM{B}\Leq m^2/\log m$. So, $\SUM{J \otimes \oB}\leq \SUM{B}\Leq m^2/\log m$. From (1) we also have the upper bound $\SUM{\oA \otimes B}\Leq \pr{\oA} \cdot m^2 / \log m$. So, $\SUM{\overline{A\otimes B}}\Leq \pr{\oA} \cdot m^2/\log m$. Together with the lower bound in (1), the lower bound (2) follows. $\Box$
Thus, to obtain large gaps, it is enough to find matrices satisfying $\pr{\oA} \gg \pr{A}$.
A classical result of Graham and Pollak [4] is that $\bp{K_n}{1}=n-1$ holds for the complete $n$-vertex graph $K_n$. Alon [1] substantially extended this result by showing that $\bp{K_n}{k}=\Theta(k n^{1/k})$ holds for every $k\geq 1$.
A biclique $1.5$-covering of a graph $G$ is a biclique $2$-covering $B(X_1,Y_1),\ldots,B(X_t,Y_t)$ of $G$ such that $(X_i\times Y_i)\cap (X_j\cap Y_j)=\emptyset$ for all $i\neq j$. That is, we now consider disjoint rectangles $X_i\times Y_i$ ("directed" versions of bicliques $B(X_i,Y_i)$), and the requirement is that for every edge $\{u,v\}$ of $G$, either $(u,v)$ or $(v,u)$ belongs to at least one of the rectangles $X_i\times Y_i$.
It is clear that $\bp{G}{2}\leq \bp{G}{1.5}\leq \bp{G}{1}$ holds for every graph $G$. For the complete graph, Alon's result yields $\bp{G}{1.5}\geq \bp{G}{2}\Geq n^{1/2}$. By improving a previous result of Amano [2], where an upper bound $\bp{K_n}{1.5}\Leq n^{2/3}$ was proved, Shigeta and Amano [8] proved an almost optimal upper bound $\bp{K_n}{1.5}\leq n^{1/2+o(1)}$.
We thus have the following
Theorem 2 (Shigeta and Amano [8]): The complement $\overline{I_m}$ of the identity $m\times m$ matrix $I_m$ has a partial decomposition $R_1,\ldots,R_t$ into $t\leq m^{1/2+o(1)}$ rectangles.
Using this result, it is easy to construct an $m\times m$ matrix $A$ whose SUM-rank satisfies $\pr{A}\leq m^{1/2+o(1)}$ while the complement matrix $\oA$ has full SUM-rank $\pr{\oA}=m$. Namely, let $A$ be the $m\times m$ matrix with $A[i,j]=1$ iff $R_k[i,j]=1$ for some $k\in\{1,\ldots,t\}$. Thus, $A$ is obtained from the matrix $\overline{I_m}$ by switching to $0$ some its $1$-entries (those not covered by the rectangles). Below is an example of a partial decomposition of $\overline{I_6}$ into $4$ rectangles $R_1=\{1,2\}\times\{4,6\}$ ($\bullet$), $R_2=\{1,3\}\times\{2,5\}$ ($\ast$), $R_3=\{3,6\}\times\{1,4\}$ ($\Box$) and $R_4=\{2,4,6\}\times\{3,5\}$ ($\diamond$), and the resulting matrix $A$:
\[ \mathrm{Rectangles} = \begin{bmatrix} {\bf 0} & \ast & . & \bullet & \ast & \bullet\\ . & {\bf 0} & \diamond & \bullet & \diamond & \bullet\\ \Box & \ast & {\bf 0} & \Box & \ast & . \\ . & . & \diamond & {\bf 0} & \diamond & . \\ . & . & . & . & {\bf 0} & . \\ \Box & . & \diamond & \Box & \diamond & {\bf 0} \end{bmatrix}\qquad A=\begin{bmatrix} {\bf 0} & 1 & 0 & 1 & 1 & 1\\ 0 & {\bf 0} & 1 & 1 & 1 & 1\\ 1 & 1 & {\bf 0} & 1 & 1 & 0 \\ 0 & 0 & 1 & {\bf 0} & 1 & 0 \\ 0 & 0 & 0 & 0 & {\bf 0} & 0 \\ 1& 0 & 1 & 1 & 1 & {\bf 0} \end{bmatrix} \]
The partial decomposition $R_1,\ldots,R_t$ into $t\leq m^{1/2+o(1)}$ rectangles of $\overline{I_m}$ guaranteed by Theorem 2 gives us a partition of all $1$-entries of $A$ into $t\leq m^{1/2+o(1)}$ pairwise disjoint rectangles; so, $\pr{A}\leq m^{1/2+o(1)}$. On the other hand, the matrix $A$ has the following property: for every two distinct $0$-entries $(i,i)$ and $(j,j)$ on the diagonal, at least one of $(i,j)$ or $(j,i)$ is a $1$-entry of $A$. Thus, the complement matrix $\oA$ has a fooling set of size $m$: no two $1$-entries of the diagonal of $\oA$ can belong to the same all-$1$ matrix. So, the SUM-rank, and even the OR-rank of $\oA$ is at least $m$, that is, $\pr{\oA}= \br{\oA}=m$. By Corollary 1, there exist an $m\times m$ matrix $B$ for which the $n\times n$ matrix $M=\oA\otimes B$ with $n=m^2$ exposes the desired gap: \[ \SUM{M}/\SUM{\overline{M}}\Geq m^{1/2-o(1)}=n^{1/4-o(1)}\,. \qquad\qquad(3) \] One can also make the matrix $B$ (and hence, also the matrix $\oA \otimes B$) explicit by choosing $B$ as the $t$-free norm-matrix with $t=m^{o(1)}$ of weight $|B|=m^{2-o(1)}$ from [6]. Then the factor $1/\log m$ in (2) turns into an only slightly worse factor $1/m^{o(1)}$. So, the gap (3) is also obtained for an explicit matrix.
References: