# Bounding the number of identical rows in a Boolean matrix using summary statistics

I am currently stuck on the following problem: given a $n \times d$ Boolean matrix $X = [x_1,\ldots,x_d]$ where each $x_j =[x_{1,j},\ldots,x_{n,j}]^\top \in \{0,1\}^n$, I want to bound the number of identical rows (i.e. rows $i$ where $x_{i,j} = 0$ for all $j$, or $x_{i,j} = 1$ for all $j$) in terms of summary statistics for $X$.

More formally, I want to bound the size of the set: $$\Gamma(X) := \left\{k \in \{1,...,n\} ~|~ x_{i,j} = x_{i,k} ~\text{for all}~ j,k = 1,\ldots,d \right\},$$ to a non-trivial interval: $$|\Gamma(X)| \in [R^\min, R^\max] \subset[0,n]$$ where $R^\min$ and $R^\max$ can be set using the following summary statistics:

1. the number of non-zero entries in each column, $s_j := \sum_{i=1}^{n} x_{i,j}$
2. the distance matrix $D :=[d_{j,k}] \in \mathbb{Z}_{+}^{d\times d}$, where $d_{j,k} := \sum^{n}_{i=1}|x_{i,j} - x_{i,k}|.$

I can produce non-trivial bounds using the $s_j$ (see below). I am not sure how to use the distance matrix $D$. However, I do know that it is important. As a example, say $d_{j,k} = n$ for some $j,k$ then $x_{i,j} = 1 - x_{i,k}$ for all $i$. In this case, all rows will have an entry that is 0 and an entry that is 1, meaning that $R^{\max} = 0$.

Example: We can set $R^\max{}$ using only the $s_j$ as follows. Given the $s_j$, we know that $P := \sum_{j=1}^{n}{s_i}$ entries must equal 1, and $Q := nd - P$ entries must equal 0. We set $R^\max{}$ by arranging these entries to maximize the number of identical rows. This results in:

$$R^\max = \min({s^{\min}, \left\lfloor \frac{P}{n}\right\rfloor}) + \min(n-s^{\max}, \left\lfloor \frac{Q}{n}\right\rfloor)$$

where $s^{\min} := \min{s_j}$ and $s^{\max} := \max{s_j}$.

Here, $R^\max$ is determined as: max # of rows with all 1s + max # of rows with all 0s. If we wanted to maximize the # of rows with all 1s, we would arrange the $P$ non-zero entries into $\left\lfloor \frac{P}{d}\right\rfloor$ rows of all 1s. Since there is a column with at most $s^{\min}$ 1s, however, it follows that we can have at most $\min({s^{\min}, \left\lfloor \frac{P}{n}\right\rfloor})$ rows of all 1s. Similarly, we could pack the $Q$ entries into $\left\lfloor \frac{Q}{d}\right\rfloor$ rows of all 0s. Since one column has at most $n - s^{\max}$ 0s, however, there can only be at most $\min(n-s^{\max}, \left\lfloor \frac{Q}{n}\right\rfloor)$ rows of all 0s.