Counting sets which can be partition in two subsets satisfying certain criterion

This is not an answer but an input regarding the maximum of $M$.

Claim:

For $M \gt 2^{n(n-1)}-n(2^{n-1}-1)$ there is no $C$ satisfying the criterion.

Argument:

When pairing matrices, at least two rows must differ. This means the only pairing which isn't allowed is the pairing of matrices which differ in exactly one row. For a given matrix, how many such disallowed pair-mates are there?

If a row has $n-1$ binary digits there are $2^{n-1}$ possible permutations of that row. For a given row and a given matrix, there are thus $2^{n-1}-1$ matrices which differ from the given matrix in only that row. With $n$ rows there are thus $n(2^{n-1}-1)$ matrices which differ from the given matrix in one row.

An example with $n=3$. The given matrix:

$$ \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix} $$

has the following $n(2^{n-1}-1)$ disallowed pair-mates:

$$ \begin{pmatrix} 0 & 1 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix} $$ $$ \begin{pmatrix} 0 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 1 & 1 \\ 0 & 0 \\ \end{pmatrix} $$ $$ \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 1 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 1 & 1 \\ \end{pmatrix} $$ This means a given matrix can only be paired with $2^{n(n-1)}-n(2^{n-1}-1)-1$ other matrices (the $-1$ at the end is because a given matrix cannot be paired with itself). A subset $C$, where $D$ consists only of the given matrix, can therefore at most have $|C-D| = 2^{n(n-1)}-n(2^{n-1}-1)-1$ other elements and can therefore at most have cardinality $M = 2^{n(n-1)}-n(2^{n-1}-1)$.

If the sole element of $D$ is the given matrix, we know from above that we cannot add extra matrices in $C-D$, but perhaps we can add extra matrices in $D$, thus increasing $M$?

If we add a disallowed matrix to $D$ (say the upper left matrix in the example above) we see that this new member of $D$ doesn't share $(n-1)(2^{n-1}-1)$ of the disallowed with the given matrix. Since the total number of matrices that a matrix can be paired with remains constant for a given $n$, the number of matrices that both the given matrix and the new member can be paired with, is reduced by $(n-1)(2^{n-1}-1)$. So one extra member of $D$, but a greater reduction in $|C-D|$.

If we add an allowed matrix to $D$, the reduction of $|C-D|$ would be even greater.

Let me know what you think.

For $M=2$ we have to count the number of pairs of matrices that differ at least at 2 rows. For this we have to substract from the total number of pairs of matrices the number $C_2$ of pairs of matrices that differ at exactly one row.

For this you have to choose first one matrix (so you have $2^{n(n-1)}$ choices, and then you have to choose one row (so you have $n$ choices) and choose then from the possible values of the chosen row one of the $2^{n-1}-1$ remaining possible rows. Since you have repeated every pair, you have to divide by 2. So $$ C_2=2^{n(n-1)}n(2^{n-1}-1)/2=n2^{n^2-n-1}(2^{n-1}-1). $$

Another way to compute $C_2$ is to choose first one row (you have $n$ choices), then choose the possible values of the rows that are equal (you have $2^{(n-1)^2}$ choices) and then pick two possible values of the chosen row (you have $\binom{2^{n-1}}{2}$ choices)and so $$ C_2=n 2^{(n-1)^2}\binom{2^{n-1}}{2}=n2^{n^2-n-1}(2^{n-1}-1). $$

Now substract $C_2$ from the total number of pairs and obtain $$ \#C=\binom{2^{n(n-1)}}{2}-n2^{n^2-n-1}(2^{n-1}-1). $$

For $M=2$ I'm pretty sure about the count. For $M=3$ I have the following reasoning:

A set of three matrices is not admissible if either all three coincide in all but one row, or they coincide in all but two rows. In the first case you have $n$ choices for the row, then $2^{(n-1)^2}$ choices for the coinciding rows, and you have to choose 3 values for the chosen row, so you have $\binom{2^{n-1}}{3}$ choices. This means that you have $$ n2^{(n-1)^2}\binom{2^{n-1}}{3}=2^{n(n-1)}(2^{n-1}-1)(2^{n-2}-1)n/3 $$ of such sets of three matrices.

In the second case you have to choose two rows (that makes $\binom{n}{2}$ choices) choose the values of the coinciding rows (you have $2^{(n-1)(n-2)}$ choices) and then choose two possible values $A_1$ and $A_2$ for the first chosen row (that's $\binom{2^{n-1}}{2}$ choices) and then choose two possible values $B_1$ and $B_2$ for the second chosen row (that's $\binom{2^{n-1}}{2}$ choices).

Then you can construct four possible sets of three matrices with the given data:

I. First matrix: $A_1$, $B_1$

Second matrix: $A_1$, $B_2$

Third matrix: $A_2$, $B_1$

II. First matrix: $A_1$, $B_1$

Second matrix: $A_2$, $B_1$

Third matrix: $A_2$, $B_2$

III. First matrix: $A_1$, $B_1$

Second matrix: $A_1$, $B_2$

Third matrix: $A_2$, $B_2$

IV. First matrix: $A_1$, $B_2$

Second matrix: $A_2$, $B_2$

Third matrix: $A_2$, $B_1$

So the number of sets of three matrices such that the number of the different rows for each possible pair is $\{2,1,1\}$ is given by $$ \binom{n}{2}2^{(n-1)(n-2)}\binom{2^{n-1}}{2}^2\cdot 4=2^{n(n-1)}(2^{n-1}-1)^2\binom{n}{2}. $$ Finally we arrive at $$ \#C=\binom{2^{n(n-1)}}{3}-2^{n(n-1)}(2^{n-1}-1)(2^{n-2}-1)n/3-2^{n(n-1)}(2^{n-1}-1)^2\binom{n}{2}, $$ for $M=3$.

For sets of four matrices it is much more complicated to write down the configurations of matrices that cannot be separated in two sets of distance at least two (define a distance function between matrices simply by setting the distance equal to the number of differing rows) so the formula gets more and more complicated for increasing $M$.

${\bf EDIT:}$

One can see this problem from the viewpoint of graph theory. For each $n$ consider the graph where the vertices are the matrices and there is an edge between two vertices if the matrices coincide in all but one row. Then you want to count the number of disconnected sets (of size $M$). For $n=2$ the graph is very simple (just a square), but for $n=3$ the graph has already $64$ vertices and $288$ edges, so the question is very difficult to answer. It corresponds to a 9-regular, distance-regular graph.

In general the graph is distance-regular, and the main theorem of "The vertex-connectivity of a distance-regular graph" by Andries E. Brouwer and Jack H. Koolen in European Journal of Combinatorics Volume 30, Issue 3, April 2009, Pages 668-673 European Journal of Combinatorics

says that the vertex-connectivity of a distance-regular graph equals its valency. Since the valency is the number of neighbors $k=n(2^{n-1}-1)$, this means that if you have $M> 2^{n(n-1)}-n(2^{n-1}-1)$, then every subset of vertices of cardinality $M$ is connected, and thus cannot have a subset $C$ satisfying the criterion of the OP. This gives a complete proof of the statement in @Jens answer.

Moreover the same theorem says that the only disconnecting sets of vertices of size not more than $k$ are the point neighbourhoods. Hence for $n>2$ and $M=2^{n(n-1)}-n(2^{n-1}-1)$ we have exactly $2^{n(n-1)}$ sets, that are the complements of the point neighborhoods, that are disconnected, and so that is the count for that $M$. (Note that for $n>2$ the point neighborhood uniquely determines the point of which it is the neighborhood).

${\bf SECOND\ EDIT:}$ The following is Definition 2.1 in https://arxiv.org/pdf/1410.6294.pdf

A connected graph $\Gamma$ with diameter $D$ is called distance-regular if there are constants $c_i$, $a_i$, $b_i$ — the so-called intersection numbers — such that for all $i = 0, 1, . . . , D,$ and all vertices $x$ and $y$ at distance $i = d(x, y)$, among the neighbors of $y$, there are $c_i$ at distance $i − 1$ from $x$, $a_i$ at distance $i$, and $b_i$ at distance $i + 1$.

In our case the diameter is $n$. If the matrices $y$ and $x$ have distance $i$ between them, this means that they differ in $i$ rows. Let the matrix $z$ be a neighbor of $y$.

If $z$ has a distance of $i-1$ to $x$, then it has to coincide in all rows with $y$ except in one row, among the distinguished $i$ rows, where it coincides with $x$. Then we have $i$ choices and so $c_i=i$.

If $z$ has a distance of $i$ to $x$, then it has to coincide in all rows with $y$ except in one row, among the distinguished $i$ rows, where it also differs from $x$. Then we have $2^{n-1}-2$ choices, and since we already chose one of the $i$ distinguished rows, we have $a_i=i(2^{n-1}-2)$.

If $z$ has a distance of $i+1$ to $x$, then it has to coincide in all rows with $y$ except in one row, which is not among the distinguished $i$ rows. Then we have $(2^{n-1}-1)$ choices, and since we already chose one of the $n-i$ rows (which are not distinguished), we have $b_i=(n-i)(2^{n-1}-1)$.

Note that $a_i+b_i+c_i=n(2^{n-1}-1)$, which is the number of neighbors of $y$ and so is the valency of the graph.

This proves that the graph is distance-regular for any $n$.