Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have a matrix of zeros and ones $a_{ij}$ with 16 rows and 30 columns. ($a_{ij}=\{0$ or $1\}$).

  1. For any rows $i=m$ : $\sum\limits_{j=1}^{30}a_{mj} \leq 15$.
  2. For any column $j=n$ : $\sum\limits_{i=1}^{16}a_{in} \geq 8$.
  3. Any 2 rows have exactly k ones ("1") in the same column.

k = ? Using brute force I find $k=7$. I'm looking for some nice and simple mathematical solution how to prove this.

share|improve this question
    
I don't understand, how exactly we can use this principle for this? I mean how this principle can help us to construct such matrix? –  Mike Aug 23 '12 at 16:45
add comment

2 Answers

up vote 4 down vote accepted

I've been thinking about your question about a combinatorial way to construct the matrix. Below is a diagram to help me explain what I did, representing the 1's as boxes and the 0's as empty space.

Diagram

You know that you're going to end up with exactly fifteen 1's in each row and exactly eight 1's in each column. It doesn't matter what order the rows and columns are in, so without loss of generality we can gather the 1's in the first row on the left (i.e. $a_{1j}=1$ if and only if $j \leq 15$). You know you want the second row to share exactly 7 1's with the first, so again without loss of generality we can let $a_{2j}=1$ for $j=1,\ldots,7$. We must have 0's for the remaining spaces under the first row's 1's, so the other eight 1's go just to the right.

Now, it becomes helpful to notice the symmetry of the matrix we're trying to make. We're also making a matrix with exactly fifteen 0's in each row and eight 0's in each column, and by gathering the 1's on the left, we're gathering the 0's on the right. Thus any row we make must be able to be symmetric in the "negative space," as an artist would say - in other words, we could reverse the order of the row, switch the 1's and 0's, and get the same thing back.

I continued in this manner, trying to put as many 1's on the left as I could. Because we need 15 1's in a row, I could not bring 5 on the left while maintaining symmetry. Thus I found two rows with 3 on the left. Knowing that the top half of the columns must add to 4 (again by symmetry), rows 5 through 8 were then forced to be filled in as illustrated. After row 8, I simply reflected the top half of the columns onto the bottom half, then inverted the 1's and 0's in the bottom half of every other column to enforce that the arrangements were unique.

share|improve this answer
    
+1 Your first paragraph under the diagram is clearly right. The idea in the second about negative space is a good one. But when you invoke symmetry in the second it is not clear that one row must be the complement to another one. A good heuristic, justified by the result. It proves existence, but not uniqueness. –  Ross Millikan Aug 24 '12 at 4:19
    
Your way is very clear for me. For the first time, I construct this matrix similarly. Then I realized, that in general all such matrix can be constructed with only 8 vectors $(1,1,0,0); (0,0,1,1);(1,0,0,1);(0,1,1,0);(1,0,1,0);(0,1,0,1); (0,0,0,0); (1,1,1,1)$. From matrix with $k=1$ and so on. By more simple combinatorial way I had in mind the possibility of obtaining the formula of the general form of each row or column. –  Mike Aug 24 '12 at 4:22
add comment

We have $\binom{16}{2}=120$ different pairs of raws. Each of 30 column has 8 ones, so one column will be used in $\binom{8}{2}=28$ pairs. So we have our answer $120\cdot k = 28 \cdot 30 \ \Rightarrow \ k=7.$

Using matrix

$$ A= \left( \begin{array}{cccccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) $$

we can build matrix

$$ A_1=\left( \begin{array}{cccccccccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) $$

And example of such matrix $A_2$

$$ \scriptsize \left( \begin{array}{cccccccccccccccccccccccccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) $$

Upd One notice. We can place 2 ones at 4 positions by $\binom{4}{2}=6$ different ways and this give us: $(1,1,0,0); (0,0,1,1);(1,0,0,1);(0,1,1,0);(1,0,1,0);(0,1,0,1)$. Thats how we get matrix $A$ with $k=1$. If we swap the even-numbered columns with the odd-numbered columns we get the matrix $A^r$. Let $a_4=(1,1,1,1); b_4=(0,0,0,0)$. Then with $k=3$.

$$ A_1=\left( \begin{array}{cccc} A & A & a_4 & b_4 \\ A & A^r & b_4 & a_4 \end{array} \right) $$

And with $k=7$

$$ A_2=\left( \begin{array}{cccc} A_1 & A_1 & a_8 & b_8 \\ A_1 & A_1^r & b_8 & a_8 \end{array} \right) $$

And with $k=15$

$$ A_3=\left( \begin{array}{cccc} A_2 & A_2 & a_{16} & b_{16} \\ A_2 & A_2^r & b_{16} & a_{16} \end{array} \right) $$

and so on...

share|improve this answer
    
It was really hard. Looking at the final result it seems to me that there are must be some easy combinatorical way to construct this matrix. –  Mike Aug 23 '12 at 16:28
2  
+1 for the sheer effort involved in latex-ing such a huge matrix :) –  Rijul Saini Aug 23 '12 at 17:33
1  
This looks suspiciously like a linear error correction code to me, and it feels like some study of Hamming codes and the like might prove fruitful here. –  Steven Stadnicki Aug 23 '12 at 17:42
    
@Steven Stadnicki I think it must be very interesting. I'am only 16. Sorry, I have no idea what you are talking about. But will try to understand it. –  Mike Aug 23 '12 at 17:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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