Here is a fairly simple combinatorial problem that seems to have an important application. Maybe its generalizations deserve further study.
Let n be a positive integer, and r a positive divisor of n. An r-permutation matrix P of order n is a square (0,1)-matrix of order n with the following property: there is a subdivision of the row set I into a disjoint union of r-element blocks I_1, ... , I_{n/r}, and a similar subdivision of the column set J, such that the (i,j)-entry of P is equal to 1 if and only if i \in I_s, and j \in J_s (with the same s).
Thus P has exactly r units in each row or column; in particular, for r=1, we get precisely the permutation matrices.
Claim. Suppose n is a multiple of 6. If P_3 is a 3-permutation matrix, and P_2 a 2-permutation matrix of order n, then P_3 - P_2 has at least one positive entry and at least one negative entry.
Proof. The sum of all entries in P_3 - P_2 is equal to 3n - 2n = n, so at least one of them is positive.
Now the number of 2-blocks in P_2 is n/2, and the number of 3-blocks in P_3 is n/3 < n/2, implying that there exists a 2-block \{i,i'\} \subset I that is not contained in a 3-block. It follows that for some j \in J, both (i,j) and (i',j)-entries of P_2 are equal to 1, while one of these entries in P_3 (say the (i,j)-entry) is 0. Then the (i,j) entry in P_3 - P_2 is -1 < 0, finishing the proof.
Is there a natural generalization?
Let n be a positive integer, and r a positive divisor of n. An r-permutation matrix P of order n is a square (0,1)-matrix of order n with the following property: there is a subdivision of the row set I into a disjoint union of r-element blocks I_1, ... , I_{n/r}, and a similar subdivision of the column set J, such that the (i,j)-entry of P is equal to 1 if and only if i \in I_s, and j \in J_s (with the same s).
Thus P has exactly r units in each row or column; in particular, for r=1, we get precisely the permutation matrices.
Claim. Suppose n is a multiple of 6. If P_3 is a 3-permutation matrix, and P_2 a 2-permutation matrix of order n, then P_3 - P_2 has at least one positive entry and at least one negative entry.
Proof. The sum of all entries in P_3 - P_2 is equal to 3n - 2n = n, so at least one of them is positive.
Now the number of 2-blocks in P_2 is n/2, and the number of 3-blocks in P_3 is n/3 < n/2, implying that there exists a 2-block \{i,i'\} \subset I that is not contained in a 3-block. It follows that for some j \in J, both (i,j) and (i',j)-entries of P_2 are equal to 1, while one of these entries in P_3 (say the (i,j)-entry) is 0. Then the (i,j) entry in P_3 - P_2 is -1 < 0, finishing the proof.
Is there a natural generalization?
2 comments:
Может я чего не понял, но, кажется, достаточно, что ни одно из чисел 2,3 (назовем их p,q, пусть p < q) не кратно другому. Действительно, рассмотрим разбиение строк на p-шки и разбиение на q-шки. Найдется p-шка X, не лежащая целиком в одной q-шке (берем любую q-шку, раз она не разбита на p-шки целиком, то какая-то p-шка X залезает в нее лишь частично). Значит, какие-то два элемента u,v p-шки X лежат в разных q-шках Y,Z. Рассмотрим любой столбец S, сопоставленный p-шке X. Он сопоставлен максимум одной q-шке Y,Z; пусть, скажем, q-шке Y он не сопоставлен. Тогда элемент на пересечении строки Y и столбца Z равен 1 в матрице R_p и 0 в матрице R_q.
Спасибо, Федя! Это условие (ни одно не кратно другому), кажется, необходимо и достаточно. Интересно, что оно же появляется у меня в другом, хотя и похоже, связанном контексте, но это так легко не объяснишь.
Post a Comment