  The Boolean rank of a $0,1$-matrix $A$, denoted $R_\mathbb{B}(A)$, is the
smallest number of monochromatic combinatorial rectangles needed to cover the
$1$-entries of $A$. In 1988, de Caen, Gregory, and Pullman asked if the Boolean
rank of the Kronecker product $C_n \otimes C_n$ is strictly smaller than the
square of $R_\mathbb{B}(C_n)$, where $C_n$ is the $n \times n$ matrix with
zeros on the diagonal and ones everywhere else (Carib. Conf. Comb. & Comp.,
1988). A positive answer was given by Watts for $n=4$ (Linear Alg. and its
Appl., 2001). A result of Karchmer, Kushilevitz, and Nisan, motivated by
direct-sum questions in non-deterministic communication complexity, implies
that the Boolean rank of $C_n \otimes C_n$ grows linearly in that of $C_n$
(SIAM J. Disc. Math., 1995), and thus $R_\mathbb{B}(C_n \otimes C_n) <
R_\mathbb{B}(C_n)^2$ for every sufficiently large $n$. Their proof relies on a
probabilistic argument.
  In this work, we present a general method for proving upper bounds on the
Boolean rank of Kronecker products of $0,1$-matrices. We use it to
affirmatively settle the question of de Caen et al. for all integers $n \geq
7$. We further provide an explicit construction of a cover of $C_n \otimes
C_n$, whose number of rectangles nearly matches the optimal asymptotic bound.
Our method for proving upper bounds on the Boolean rank of Kronecker products
might find applications in different settings as well. We express its potential
applicability by extending it to the wider framework of spanoids, recently
introduced by Dvir, Gopi, Gu, and Wigderson (SIAM J. Comput., 2020).
