Rearranging rows of a matrix

315 Views Asked by At

Let $n,r,k$ be positive integers such that and $k \geq 2$. Consider the set of integers $\{1,2, \cdots, n\}$. I need to arrange these integers in a $kn \times r$ matrix in such a way that the entries in each row is strictly increasing and entries in each column is non-decreasing with the extra condition that each integer is repeated exactly $kr$ times. Now given such a matrix I believe that there always exist exactly $n$ rows such that the resultant $n \times r$ matrix has the property that each integer is repeated exactly $r$ times. I checked for some smaller cases and it seems true but don't know how to prove the general case.

Here is an example: Consider $n=5,k=r=2$ and the $ 10 \times 2$ matrix $(1,2)(1,3)(1,3)(1,4)(2,4)(2,4)(2,5)(3,5)(3,5)(4,5)$. Then we can extract the matrix (1,2)(1,3)(2,4)(3,5)(4,5) in which each entry is repeated twice.

1

There are 1 best solutions below

4
On BEST ANSWER

Let $n = 6$, $r = 3$, $k = 2$. Let matrix be $$\begin{bmatrix} 1 & 2 & 4 \\ 1 & 2 & 4 \\ 1 & 2 & 4 \\ 1 & 3 & 5 \\ 1 & 3 & 5 \\ 1 & 3 & 5 \\ 2 & 3 & 6 \\ 2 & 3 & 6 \\ 2 & 3 & 6 \\ 4 & 5 & 6 \\ 4 & 5 & 6 \\ 4 & 5 & 6 \end{bmatrix}.$$ Selecting $r = 3$ rows with 6 we get either 2 and 3 at least twice or 4 and 5 at least twice. Selecting 3 rows with 1 we get either 2 and 4 twice or 3 and 5 twice. This means that selecting 3 rows with 1 and 3 rows with 6 we get one of $2, 3, 4, 5$ at least 4 times that is more than $r$. This means that your conjecture is wrong.

Edit. As mentioned in comments there may be additional condition of relative primality of $n$ and $r$. There is a bigger example with the same idea to show that conjecture is wrong. Let $n = 11$, $r = 5$ and $k = 2$. Let matrix be $$\left[\begin{array}{ccccc|ccccc|cc|ccccc|ccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 3 & 4 & 6 & 7 & 7 & 7\\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 4 & 4 & 4 & 4 & 5 & 5 & 5 & 5 & 5 & 7 & 7 & 8 & 8 & 8\\ 3 & 3 & 3 & 3 & 3 & 5 & 5 & 5 & 5 & 5 & 6 & 6 & 6 & 6 & 8 & 8 & 8 & 9 & 9 & 9 & 9 & 9\\ 4 & 4 & 4 & 4 & 4 & 6 & 6 & 6 & 6 & 6 & 8 & 8 & 8 & 8 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10\\ 7 & 7 & 7 & 7 & 7 & 9 & 9 & 9 & 9 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \end{array}\right]^T\phantom.$$ (Note that matrix is transposed to take less space.) There are five rows with 1, 3, 7, five rows with 1, 5, 9, five rows with 3, 5, 11 and five rows with 7, 9, 11. Also we need to keep five rows with each value. However taking five rows with 1 we get at least three rows with either 3 and 7 or 5 and 9. Taking five rows with 11 we get at least three rows with either 3 and 5 or 7 and 9. This means that one of 3, 5, 7, 9 would be taken at least six times.