A conjecture and its proof regarding an optimal 0-1 matrix with prescribed column sums

A conjecture and its proof regarding an optimal0-1 matrix with prescribed column sumsAuthor: Xinyu Liu, Shengtong ZhangShanghai High School, Shanghai, China Team leader: Guangting WangAdvisor: Changhong LvAbstractThe College Entrance Exam reform in China, beginning in Shanghai, is currently in progress, which engenders the problem of proper course scheduling in high schools. Based on this fact, the paper generalizes a problem of the most theoretically efficient course scheduling and conjectured the existence of it for any value of the totalm⨯matrix subjects n and the total time period m available. We construct a 0-1 nwith the column sums given and use the method of mathematics induction to provem⨯that an inequality on the 1’s in the matrix is necessary and sufficient for any m submatrix of the matrix to have m 1’s neither in the same row nor in the same column. In other words, as long as the number of total classes offered reaches its minimum value to make the most efficient course scheduling possible, then we can guarantee the existence of it, no matter how students may choose their optional testing subjects. The result assures high schools of spending the least class hours on optional testing subjects under the background of the test reform, so that the high school can make the best use of time.Keywords:optimal construction, 0-1 matrix, course scheduling, column sum1. IntroductionProblems about course scheduling have long been very complicated – whenconsidering such problems, we have to take both students’ preference and the school’s resource into account. This problem is prevalent in high schools and universities.[1][2].The College Entrance Exam reform in Shanghai has brought great trouble in course scheduling in high schools. Instead of choosing only one class as optional testing subject in addition to three mandatory subjects, under current circumstances students are required to choose three of the six subjects as additional testing subjects and switch to different classrooms attending each class.The school hopes to maximize its benefit by making the class hours as few as possible. The most ideal case would be offering optional testing classes in exactly three time periods. A course scheduling that allows every student to take the classes they choose to take tests in the three periods is called for.0-1 matrices with prescribed row sums and column sums have always aroused the interest of scientists [3-7], as they have potential application in combinatorics [8], algebra [9] and statistics [10].In this paper, we use such matrices to solve the problem of course scheduling, where we generalize the case to totally n subjects and m time periods. If the class for a specific subject is offered at a certain time period, then we write a “1” in the corresponding square, otherwise a “0”.Subject 1 Subject 2 ······· ······· ······· Subject n Period 1 ······· Period mBased on achieving the most efficient course scheduling, we propose thefollowing conjecture.Conjecture: Giving integers m , n (m ≤n ) and integers n s s s ,,21such thatm s i ≤≤1，),2,1(n i =, the following two statements are equivalent:(1). )1(1+-≥∑=m n m sn i i(2). There exists a n m ⨯ 0-1 matrix, whose m m ⨯submatrices all have theproperty: we can choose m 1’s from the submatrix such that each two 1’s are neither in the same row nor in the same column.In this paper, we present a proof for the conjecture above, meaning that the most efficient matrix always exists, no matter how students choose the subjects.2. Our proof and resultQuestion:Giving integer m , n (m ≤n ) and integers n s s s ,,21such that m s i ≤≤1，),2,1(n i =, prove that the following two statements are equivalent:(1). )1(1+-≥∑=m n m sn i i(2). There exists a n m ⨯ 0-1matrix, whose m m ⨯submatrix all have theproperty: we can choose m 1’s from the submatrix such that each two 1’s are neither in the same row nor in the same column. ………………………………………… （*）Proof:For convenience ’s sake, we call the statement above “statement （*）”, and the property above “property （*）”.Let n s s s s +++= 21 be the number of 1’s in the matrix, s mn T -= be the number of 0’s in the matrix.Statement (1) is necessary for statement (2)In fact, if )1(1+-<∑=m n m sn i iThen )1()1(-=+-->-=m m m n m mn s mn TBy the pigeon hole principle, there must exist a row having no less than m 0’s. Select the columns that those 0’s belong to and a m m ⨯submatrix is formed. We cannot find m 1’s with property (*) in this submatrix, contradictory to statement (2).Statement (1) is sufficient for statement (2)We use mathematics induction to solve this problem and only consider the case of )1(1+-=∑=m n m s ni i . (If we can construct a matrix under this condition, then a matrix satisfying the problem definitely exists if )1(1+->∑=m n m s ni i )When 2=+n m , then 1==n m ⇒11=s , and matrix A is one that meets the requirement. 1Matrix AWhen 3=+n m , then =1, =2⇒221=+s s , ⇒121==s s , and matrix B is one that meets the requirement. 1 1Matrix BSuppose that when k n m =+ and 1-k n m =+, a matrix with property (*) exists. Then in the case of 1+=+k n m , we can also construct such matrix. Theprocess of construction is shown below.For convenience’s sake, we assume that 11-≤≤m s i . In fact, if m s i = , then squares in the corresponding column are all filled with 1’s, so this column will have no effect whether property (*) holds for the whole matrix.If n m =, then 121-====m s s s n . The following matrix meets therequirement. 10 0 0 0 0 0 01 0 0 0 0 0 00 1 0 0 0 0 00 0 1 0 0 0 00 0 0 1 0 0 00 0 0 0 1 0 0 0 0 0 00 1Matrix C If n m <, notice that )1()1(-=+--=m m m n m mn T and a matrix with property (*) cannot have a row with at least m 0’s, so every row should have exactly (m -1) 0’s.We use the coordinate ( , ) to represent the square in row i and column j . Let ),({j i T = The square ( , ) is the only square filled with “1” in column j }.Because n m <, we can know that 1-≤m T .By the pigeon hole principle, there exists a row that has no element in T. Without loss of generality, suppose the first row has no element in T, and the first (m -1) squares of the first row are filled with “0”, and the rest are filled with “1”.According to this assumption, the m th column, the (m +1)th column, …the n th column all have at least two 1’s. We divide this problem into the following two cases.① 11+≥++m s s m mWe know from the inductive assumption that there exists a )1(-⨯n m matrix with property (*) with the sums of all columns n m m m m m s s s m s s s s s ,,,,,,321121+++--+. Based on this matrix, we do the followingoperations to divide the m th column into two:i. If a square is filled with “1”, then it divides into two 1’s;ii. If a square is filled with “0”, then it divides into one 0 and one 1;iii. Exchange some of the 0’s and 1’s on the same row so that the sum of the left column equals s m and the sum of the right column equals s n .For example, if 6=m , 4,576==s s , then we do the operations shown below:0 0 0 1 1 01 i 1 1 ii 1 1 iii 1 10 → 0 → 0 1 → 1 00 0 0 1 0 11 1 1 1 1 1 11 1 1 1 1 1 1We can prove that the n m ⨯ matrix achieved in this way satisfies property (*). Randomly choose m different columns in this n m ⨯ matrix that form set U.And suppose that those columns’ correspondence in the )1(-⨯n m matrix forms set V . ( The m th column and the (m +1)th column in the n m ⨯ matrix all corresponds to the m th column in the )1(-⨯n m matrix ). Let V V ='{column m } in the )1(-⨯n m matrix.(a) If U does not include column m or column m +1, then the generated submatrix has property (*) according to the inductive assumption.(b) If U includes one of column m and column m +1, we know that V has property (*).Let W be the set of 1’s in V that are not in the same row or column. According to our constructive method, W corresponds to m 1’s not in the same row or column in U. Thus property (*) holds for U.(c) If U includes both of column m and column m +1, then V’ includes (m -2) different columns.Claim: there must exist (m -2) 1’s in V with property (*), and the two rows ( call it row i and row j ) that have no “1” in V cannot be both filled “0” in the m th row of the )1(-⨯n m matrix.The claim is not hard to prove. In fact, if the claim is false, then the submatrix formed by V’, the m th column in the )1(-⨯n m matrix and an additional arbitrarily chosen column does not have property (*), contradictory to the inductive assumption.Suppose row i has a “1” in V . and row j has a “0” in V . The claim is enough to prove that property (*) holds for the n m ⨯matrix. For the submatrix of the n m ⨯matrix, we choose the following m squares.i. (m -2) squares that the 1’s in V corresponds to.ii. 2 squares that fill row i and row j .Because there is a “1” row i in V , so this filling can always be achieved.② m s s m m ≤++1We use the coordinate ( , ) to represent the square in row i and column j . Let ),({j i T = The square ( , ) is the only square filled with “1” in column j }.Because n m <, we can know that 1-≤m T .By the pigeon hole principle, there exists a row that has no element in T.Let t ……t be any rearrangement of s ……s such that t ……t ≥2 We are going to construct a matrix with the following properties:(a) The first row has no element in T(b) The first (m -1) squares of the first row are filled with “0”, and the rest are filled with “1”.(c) The sum of each column is t ……t , respectively.After this matrix is constructed, we can rearrange the columns to make the sum of each column s ……s , respectively.By the inductive assumption, we can construct a )1()1-(-⨯n m matrix that the sums of the column are 1,1,1,2,,,321121----++++-n m m m m m t t t t t t t t , respectively. Note that 2,,1≥+n m m t t t , so this matrix can be constructed.Based on this matrix, we add ⎪⎪⎪⎭⎫ ⎝⎛-11,10,0,0'01 ，，s n as the first row and ()00,00,0,1 ，， as the (m +1)th column. So we get a n m ⨯ matrix with column sum n m m m m m t t t t t t t t ,,11,,,321121+++--+，，. Then we exchange some of the 0’s and 1’s in the m th and (m +1)th column to let their column sum to be t m and t m+1. Next we will prove that properly (*) holds for the matrix constructed in this way.Let M be the set of m randomly chosen columns in the n m ⨯ matrix.a) M does not include the m th column and (m +1)th column.By the pigeon hole principle, there must exist at least one “1” in the first row and a certain column. For the rest (m -1) rows and (m -1) columns, we can find (m -1) 1’s neither in the same row nor in the same column. Together with the “1” we select, we’ve got m 1’s with property (*).b) M includes one of the m th column and (m +1)th column.We can select the “1” on the first row and the m th or (m +1)th column. For the rest (m -1) rows and (m -1) columns, we can find (m -1) 1’s not in the same row or column. Together with the “1” we selected, we’ve got m 1’s that meet therequirement.c) M includes both the m th column and (m +1)th column.Suppose the rest (m -2) columns are column 221,,-m a a a , and the column theycorrespond to in the )1()1(-⨯-n m matrix are 221,,-m b b b .Consider the submatrix composed by the m th column of the )1()1(-⨯-n mmatrix as well as 221,,-m b b b , and select (m-1) 1’s that are not in the same rows orcolumns in this submatrix. Then correspond those squares into the m m ⨯submatrix of the n m ⨯ matrix. The “1” in the m th column of the )1()1(-⨯-n m matrix is corresponded to either the m th column or the (m +1)th column. If it is corresponded into the m th column, then also choose the first square in the (m +1)th column, otherwise choose the first square in the n th column. In this way, we prove that there are m 1’s with property (*) in M.3. ConclusionIn this paper, we prove a conjecture concerned with 0-1 matrix and the sum of each column. If the sum of each are given and the sum of those values has a lower bound, we can construct an n m ⨯ 0-1 matrix, in which all m m ⨯submatrix have m 1’s that each two are neither in the same row nor in the same column. The result has some applications in the effective utilization of resources, such as course scheduling in hig h schools.References:1. Y. Wang, Using genetic algorithm methods to solve course scheduling problems, ExpertSystems with Applications 25 (2003) 39–502. D. Shiau, A hybrid particle swarm optimization for a university course scheduling problemwith flexible preferences ， Expert Systems with Applications, 38 (2011) 235–2483. J.P. Morgana, N. Uddinb ， Optimal row-column design for two treatments ，Journal of statistical planning and inference, 115 (2003) 603 – 6224.L. Guo, Z. Jiang, S. Zhou, An Inverse Problem of Matrix with Fixed Row and Column Sums and its Application, Energy Procedia 17 ( 2012 ) 1598 – 1606 5.A. Barvinok, On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries, Advances in Mathematics, 224 (2010) 316–339 6.N. Ho, P. Dooren, Non-negative matrix factorization with fixed row and column sums, Linear Algebra and its Applications 429 (2008) 1020–1025 7.C. Nelson, B. Shader, A (0-1)-matrix existence theorem and equivalent tiling problems with dimers and monomers, Linear Algebra and its Applications, 485 (2015), 503-526 8.J. H. van Lint, R. M. Wilson, A Course in Combinatorics, second edition, Cambridge University Press, Cambridge, 2001. 9. I. G. Macdonald, Symmetric Functions and Hall Polynomials, with contributions by A.Zelevinsky, second edition, Oxford Math. Monogr., Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1995.10.Y. Chen, P.Diaconis, S. P. Holmes, J. S. Liu, Sequential Monte Carlo methods for statistical analysis of tables, J. Amer. Statist, Assoc. 100 (2005) 109-120.Team Member ProfileXinyu Liu: Current Grade 12 student at Shanghai High School. First prize winner of 2017 National High School Mathematics League inChina. Second prize winner of 2016 National High SchoolMathematics League in China. Second prize winner of 2017Science & Technology Innovation Competition in Shanghai.(Physics project). Second prize winner of 2017 “TomorrowTechnology Star Selection”. (Physics project)Shengtong Zhang: Current Grade 12 student at Shanghai High School.IMO (2016) gold medalist. CMO (2016) gold medalist. Firstprize winner of 2016 National High School MathematicsLeague in China.。