We call a matrix $\textsl{binary matrix}$ if all its entries equal to $0$ or $1$. A binary matrix is $\textsl{Good}$ if it simultaneously satisfies the following two conditions: (1) All the entries above the main diagonal (from left to right), not including the main diagonal, are equal. (2) All the entries below the main diagonal (from left to right), not including the main diagonal, are equal. Given positive integer $m$, prove that there exists a positive integer $M$, such that for any positive integer $n>M$ and a given $n \times n$ binary matrix $A_n$, we can select integers $1 \leq i_1 <i_2< \cdots < i_{n-m} \leq n$ and delete the $i_i$-th, $i_2$-th,$\cdots$, $i_{n-m}$-th rows and $i_i$-th, $i_2$-th,$\cdots$, $i_{n-m}$-th columns of $A_n$, then the resulting binary matrix $B_m$ is $\textsl{Good}$.
Problem
Source: China TST 2005
Tags: linear algebra, matrix, graph theory, combinatorics unsolved, combinatorics
27.06.2006 11:45
This is a Ramsey-type result. In fact, we can use Ramsey's Theorem to prove it. Given an $n\times n$ binary matrix $A=(a_{ij})$, we can associate to it a coloring of $K_n$ (the complete graph on $n$ vertices) with four colors as follows: we color the edge $ij,\ i<j$ with color $00$ if $a_{ij}=0,a_{ji}=0$, with color $01$ if $a_{ij}=0,a_{ji}=1$, and so on (the other two colors are $10$ and $11$; you get the picture ). By Ramsey's Theorem, if $M$ is large enough, any four-colored $K_n,\ n\ge M$ will contain a monochromatic complete subgraph of size $m$. If $j_1,\ldots,j_m$ are the vertices of this subgraph, the rows and columns we keep from the matrix $A_n$ associated to the coloring of $K_n$ are precisely $j_1,\ldots,j_m$ (i.e. we erase the other rows and other columns).
02.04.2010 04:11
Nice. It can also be solved without using any theorems at all. Consider all diagonals perpendicular to the main diagonal. For each of these diagonals, we assign a value $ 00,01,10,11$ based on which of those is in majority in the pairings of $ (a_{ij},a_{ji})$ in this diagonal with $ i<j$. Now, number these diagonals from top to bottom $ 0,1,2,3,...$. Take $ n$ large enough so that there must be at least $ m$ diagonals past diagonal $ (m+2)4^m$ with the same number. Starting with the diagonal of smallest number of these, we reduce it to a good diagonal (a diagonal which has all numbers to the left of the main diagonal equal, and all numbers to the right equal, with the middle number being arbitrary) of the same type as that of the diagonal ($ 00,01,10,11$) which we can do in at most ($ \frac{3}{4}$ of the initial diagonal number) number of moves. Then, we move this diagonal up by removing the column and row corresponding to the ends until it moves into the spot held by diagonal 0. Now there are $ m-1$ diagonals of the same type, each at least as large as $ (m+2)4^{m-1}$ (because for each of the remaining diagonals, at most $ \frac{3}{4}(m+2)4^{m-1}$ numbers below the main diagonal were removed, and the number of the diagonal is the number of entries below the main diagonal). We repeat this process again with the next smallest diagonal, this time moving it into spot 1. We continue this procedure with spot 2,3, etc. until we have 1 diagonal which is of the same type whose number is at least $ (m+2)4$. After making it a good diagonal of the same type, it has number at least $ (m+2)$, and then moving it up into spot $ m-1$ with the same process, we have thus made the first $ m$ diagonals of the same type. Remove all rows and columns past $ m$, and we have our good binary matrix. Cheers, Rofler