6
$\begingroup$

If you consider all $10$ by $15$ matrices with entries that are either $0$ or $1$, there are ${2^{15} \choose 10}$ with no repeated rows (up to row permutation) and ${2^{10} \choose 15}$ with no repeated columns (up to column permutation). How many are there with neither any repeated rows or columns (up to either row or column permutation)?

$\endgroup$
3
+25
$\begingroup$

This can actually be worked out in a much more straight-forward manner than it seems, through a bit of reasoning.

Suppose that we construct a $10\times15$ matrix such that there are no repeated columns. Now, we must necessarily have that the number of repeated rows is somewhere between 0 and 9 (assuming that one row has to be "unique" first before there is a repeat). And so, we go about finding the number of possibilities for each repeat-count starting with the highest.

It is easy enough to see that there cannot be 9 repeats, as that would require all 15 columns to be either all-zeros or all-ones, and thus at most two would be "unique". Similarly, with 8 repeats, there would be only two "unique" rows, and thus only four possible columns. We can say the same thing about 7 repeats, which would provide only eight possible columns. Thus, we begin with the case of 6 repeats.

If there are 6 repeats, then there are four "unique" rows. In order to satisfy the conditions, these four "unique" rows must contain 15 of the 16 possible 4-bit combinations. The remaining 6 rows can be chosen from amongst the four "unique" rows.

If there are 5 repeats, then there are five "unique" rows, and we can find the number of these by observing that this is proportional to the number of $5\times15$ matrices with no repeated column, for which there are no repeating rows (and thus you subtract off a number proportional to the one we obtained for 6 repeats).

This can then be repeated until we get to $10\times15$, by working out how many $n\times15$ matrices can be made without repeats based on the value for $n-1$.

With the $n\times15$ case, there are ${2^n}\choose{15}$ possible matrices (up to column permutation). From these, we must subtract off the number of matrices that have $k$ repeated rows, with $k$ running from $1$ to $n-4$. We will call the number of $n\times15$ matrices without repeats $M_n$.

Now, we can see that $$ M_n ={2^n\choose15} - \sum_{k=4}^{n-1} S(n,k)M_k $$ where $S(n,k)$ is a Stirling number of the second kind. This is because we are partitioning our set of $n$ rows into non-empty subsets such that there are $k$ unique subsets, and for which order is irrelevant (that is, we take the subset containing the first row to be subset "1", then the subset containing the first row not in the first subset to be subset "2", and so on).

Now, we can do our calculations...

$$ M_4 = {16\choose15}\\ M_5 = {32\choose15} - S(5,4) M_4 = {32\choose15} - 10\times 16\\ M_6 = {64\choose15} - S(6,4) M_4 - S(6,5) M_5 = {64\choose15} - 65 M_4 - 15 M_5\\ \vdots $$ and so on.

Once you have $M_{10}$, you must finish the process by dividing out the possible row permutations - that is, divide by $10!$. Of course, the actual number is going to be very close to ${2^{10}\choose15}/10!$, as one would expect repeats to be far less common than non-repeats.

(Through use of a spreadsheet, I find that the number is roughly $2.709912\times10^{26}$, although some small truncation error may have made its way into that expression)

$\endgroup$
  • $\begingroup$ What is $P_{15}$? $\endgroup$ – Gilles Bonnet Feb 27 '14 at 19:46
  • $\begingroup$ Oops, sorry - that's a leftover from when I was working out the actual number of permutations, before I realised that I could work with column combinations. Will be fixed in a moment. (it was meant to be the permutation, $^{2^n}P_{15}$) $\endgroup$ – Glen O Feb 27 '14 at 20:56
  • $\begingroup$ I am trying to use your formula, however $M_4$ isn't divisible by $4!$ and $M_5$ isn't divisible by $5!$. $\endgroup$ – abuzittin gillifirca Jan 7 '17 at 10:08
  • $\begingroup$ @abuzittingillifirca - you're right; on thinking about it, there's a flaw in that final step - my reasoning works correctly for finding the number of ways up to column permutation, but it does not correctly deal with row permutations, as row permutations can overlap with column permutations. I can think of a way to fix the approach, but it will take a little more time for me to think it through. In simple terms, you enforce an order on the rows (and possibly columns, too). $\endgroup$ – Glen O Jan 7 '17 at 16:31
1
$\begingroup$

Edit: I misread the question and tried to answer a different question! I am trying here to get the number of matrices $10\times15$ with no repeated rows or columns but I don't do the identification up to permutation of rows or columns. This is probably a question harder then the original one.

This is just an attempt. This does not give an answer to the problem but I think the following observations are interesting and might help to find an answer. At the end I explain the limit of this attempt. This limit is also the reason why I think the answer of @clintonmonk does not work.

Call $\hat{M}_{n, m}$ the subset of $M_{n, m}(\mathbb{Z}_2)$ of matrices with no repetated rows nor columns.

My first observation is that

Lemma: For any $n\in\mathbb{N}, $ $\mathrm{Card}\hat{M}_{n, 2^n}=\mathrm{Card}\hat{M}_{n, 2^n-1}=2^n!$

Proof: We have $2^n$ possible vectors with $n$ binary entries. We have $2^n!$ ways to order them without repetition. That is why $\mathrm{Card}\hat{M}_{n, 2^n}=2^n!$

Now, we can define a bijection beetween $\hat{M}_{n, 2^n}$ and $\hat{M}_{n, 2^n-1}$, given by removing the last column. The inverse is adding in the end of the matrix the (unique) missing vector.

If we apply this lemma with $n=4$ we obtain:

Corollary: $\mathrm{Card}\hat{M}_{4, 16}=\mathrm{Card}\hat{M}_{4, 15}=16!$

If we complete a matrix $M$ in $\hat{M}_{4, 15}$ by $6$ lines different from the $4$ lines of $M$ and different between each other then we obtain a matrix in $\hat{M}_{10, 15}$. So for each $M$ in $\hat{M}_{4, 15}$ we have $(2^{15}-4)!/(2^{15}-10)!$ possibilities to complete it and obtain a matrix in $\hat{M}_{10, 15}$. Hence:

$\mathrm{Card}\hat{M}_{10, 15}\geq 16! \frac{(2^{15}-4)!}{(2^{15}-10)!} \simeq 10^{40} $

The problem is that this is probably not an equality. Indeed if $N\in\hat{M}_{10, 15}$, we don't necessarily have that the first $4$ columns of $N$ form a matrix in $\hat{M}_{4, 15}$. It can happen that $2$ rows of $M$ have the same first $4$ entries and differ somewhere in the $6$ next. So we are not going to list all the matrices by this procedure.

$\endgroup$
  • 1
    $\begingroup$ Your lower bound is about $2.6 * 10^{40}$. But this is already bigger than ${2^{10} \choose 15}$. $\endgroup$ – felix Feb 26 '14 at 21:07
  • $\begingroup$ @felix ${2^{10} \choose 15}$ is the number of matrices with no repeated columns up to permutation of the columns. There is no contradiction here: ${2^{10} \choose 15} 15! \simeq 10^{45}$ $\endgroup$ – Gilles Bonnet Feb 27 '14 at 15:16
  • $\begingroup$ @felix sorry I just realise now that you ask to count matrices up to permutation of either rows or columns. Now I understand your comment and our misunderstanding. My answer is about counting matrices without identification when we do permutation of the columns or row. $\endgroup$ – Gilles Bonnet Feb 27 '14 at 19:39
0
$\begingroup$

Consider splitting the problem into two separate ones: Finding a $10 \times 10$ matrix with no repeated rows or columns and then finding $10 \times 5$ extra values.

To find a $10 \times 10$ matrix with no repeated rows or columns, look for all possible {0,1}-matrices that are nonsingular. Row-space and column-space have the same rank and a nonsingular $n \times n$ matrix will have full rank (why this works). You therefore need to calculate the number of nonsingular $n \times n$ {0,1}-matrices $N_{nonsingular}$.

We can use the algorithm A046747 to find the (asymptotic) probability a random $n \times n$ {0,1}-matrix is singular. (A055165 is better, but it depends on A046747.) It looks like $N_{nonsingular}$ may need to be calculated by brute-force, unless someone else finds a better approach. For now, assume $N_{nonsingular}$ for $n=10$ is known.

Next, because we know the rows and columns in the $10 \times 10$ are distinct, the remaining 5 columns can be anything as long as they're different from the first 10 columns.

$$ Possible\ combinations = N_{combos} = \frac{(2^{10} - 10)!}{(2^{10} - 15)!} \\ $$

Therefore, our number of matrices is: $$ N = N_{nonsingular} * N_{combos} $$

NOTE: I tried this originally with the formulas from the linked algorithms, but my answers were higher than expected. I imagine this was due to error on my part and also to not quite knowing what ordering the last 5 "free" columns should have with respect to the other 10 columns. I instead hope this answer provides some insight on a good technique to try.

$\endgroup$
  • $\begingroup$ what about splitting it into a 5x5 matrix of 2x3 blocks. Then you can have a square matrix whose entries are in 1-64. You get ${64^5 \choose 5}$, rows or columns, I think, up to permutations of rows or columns. But it has it's own problems though... $\endgroup$ – snulty Feb 24 '14 at 11:32
  • 1
    $\begingroup$ I am not sure this works. If I understand it right. You are assuming that if $M$ is a $10\times15$ matrix with different lines then the first $10\times10$ extracted matrix have different lines. I don't think this is true. One couple lines of $M$ may differ only on the 5 last numbers and not on the 10 first. $\endgroup$ – Gilles Bonnet Feb 26 '14 at 12:46
  • $\begingroup$ Unfortunately, the matrix need not be nonsingular. Any one row or column could be all zeros, or a row or column could be the sum of two other rows or columns (whose dot product is zero) - in both cases, the matrix is singular, but still satisfies the conditions being applied. $\endgroup$ – Glen O Feb 27 '14 at 7:20
  • $\begingroup$ @Glen O - Good points. The first I would argue could be solved by mapping {0,1} to some other digits, but the second does invalidate the nonsingular approach. $\endgroup$ – clintonmonk Feb 28 '14 at 21:45
  • $\begingroup$ @GillesBonnet The assumption was that if you have a nonsingular matrix (rows/columns different), then you could add in the different columns later. So your example of the last 5 columns being the different ones could be interpreted as the 10x10 nonsingular matrix being in columns 6-15. Columns 1-5 would then be the "free" columns that could be identical across the rows. As GlenO pointed out, this approach won't work anyway. $\endgroup$ – clintonmonk Feb 28 '14 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.