2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.