Pigeonhole in a Matrix

Solution

|Contact| |Front page| |Contents| |Up|

Both the problem and its solution were proposed by Professor McWorter. This problem reminds one of the #6 where we showed that a 2×2 submatrix exists that consists entirely of either 0's or 1's. We can't say in advance which it's going to be. Removal of the ambiguity makes the problem that much more difficult.

Let a_i, i = 1, ..., 14, be the number of pairs of rows with 1's in the i-th column of A. Let P be the sum of the a_i, i = 1, ..., 14. For example, suppose A is

     1  1  1  0  0
     1  0  0  1  0
     1  0  0  0  1
     0  1  0  0  1
     0  0  1  1  1

Then a₁ = 3(3 - 1)/2 = 3 because the first column has three 1's and so there are 3(3 - 1)/2 = 3 pairs of rows with a 1 in the first column. Also, a₂ = 2(2 - 1)/2 = 1, a₃ = 1, a₄ = 1, and a₅ = 3. Thus P=9 for this matrix. This matrix has no 2 by 2 submatrix of 1's. P is also not greater than the number, 10 = 5(5 - 1)/2, of pairs of rows.

If P is greater than the number of pairs of rows of A, which is 14(14 - 1)/2 = 91, then, by the pigeonhole principle, some pair of columns have 1's in the same pair of rows, implying that there is a 2×2 submatrix of 1's in A. We show that P is no smaller than 92, the sum obtained when the number of 1's in each column of A are as nearly equal as possible.

If any column, say the i^th, of A has m 1's and some other column, say the j^th, of A, has n < m - 1 1's, then moving a 1 from the i^th column to the j^th reduces a_i by m - 1 and increases a_j by n. Hence this move reduces P. Therefore, the smallest value P can have is that obtained by a matrix whose columns have numbers of 1's as nearly equal as possible. Call this least value L. We show that L = 92, knowing that P ≥ L.

Dividing the 58 1's as evenly as possible among the 14 columns of A, we get 12 columns with four 1's and 2 columns with five 1's (12·4 + 2·5 = 58). Hence L = 12(4(4 - 1)/2) + 2(5(5 - 1)/2) = 92. Since P ≥ L, it follows that P > 91, and so some 2×2 submatrix of A consists of all 1's.

I don't know if this argument always gives the best possible result, but here is some evidence in support of this claim. Let A be the incidence matrix for a projective plane of order k. Then A is (k² + k + 1)×(k² + k + 1), has exactly k + 1 1's in each column, and contains no 2×2 submatrix of 1's. Hence, if a matrix of this size must have a 2×2 submatrix of 1's, then it must contain more than (k + 1)(k² + k + 1) 1's. If A is assumed to have (k + 1)(k² + k + 1) + 1 1's, the above argument will show that A has a 2×2 submatrix of 1's. Hence the above argument gives the best result in infinitely many cases.

Note

#20 is almost the same kind as the problem at hand. It could have been phrased

If an 11 by 10 matrix A contains 40 1's, then some 2 by 2 submatrix of A consists of all 1's.

The only differences are that #20 involves a nonsquare matrix and assumes the columns of A are all different but have the same number of 1's. For both problems, though, it is irrelevant what the non-1 entries are, and so could be any matrix with enough 1's.

In this context, the 40 could be replaced by 39, or one 3-subset and 9 4-subsets.

Remark

Alexander:

I had been toying with the idea of posing to alt.math.recreational the problem of placing 25 checkers on a checkerboard so that no four would be the vertices of a rectangle with sides parallel to the sides of the checkerboard. The proof says that 26 checkers on a checkerboard gurantees four checkers as corners of a rectangle with sides parallel to the sides of the checkerboard. However, I could not place 25 checkers without forming the corners of a rectangle.

Then I noticed that a refinement of the argument shows that any 25 checkers on the checkerboard forces four of the checkers to be corners of a rectangle. For, if 25 checkers are on the board, then some row has at exactly four checkers; any more would guarantee the existence of four checkers which are corners of a rectangle. This determines four columns and seven rows that can contain at most seven checkers if no four checkers form the corners of a rectangle. But then there are four columns and seven rows which must contain at least 25-4-7=14 checkers. These 14 checkers determine at least seven pairs of columns, one more than six pairs of the four columns. Hence 25 checkers on a checkerboard must contain four which are corners of a rectangle with sides parallel to the sides of the checkerboard.

This raises the question, can 24 checkers be placed on the checkerboard so that no four form the corners of a rectangle with sides parallel to the sides of the checkerboard? The answer is yes. An example is below with 1 equal a checker.

     1  1  1  0  0  0  0  0
     1  0  0  1  1  0  0  0
     1  0  0  0  0  1  1  0
     0  1  0  1  0  0  0  1
     0  1  0  0  1  1  0  0
     0  0  1  1  0  0  1  0
     0  0  1  0  0  1  0  1
     0  0  0  0  1  0  1  1

So, my proof is not best possible despite my protestations to the contrary.

Note

Professor McWorter also noticed that the problem admits the following reformulation: Let G be a graph with 14 vertices and 29 edges. Show that G contains a 4-cycle.

|Contact| |Front page| |Contents| |Up|