Ponder This Challenge - October 2005 - Matrices with special 2x2 minors

Ponder This Challenge:

Puzzle for October 2005.

This months puzzle concerns arrays of integers, a(i,j) with the following property.  For all pairs of distinct rows i1,i2 and distinct columns j1,j2 the diagonal sum a(i1,j1)+a(i2,j2) and the anti-diagonal sum a(i1,j2)+a(i2,j1) are unequal.  We are interested in finding such arrays with the entries chosen from as narrow a range of integers as possible.  For example the following is an example of such a 3x3 array with entries chosen from {0,1}

        0  0  1
        0  1  0
        1  0  0

Find a 5x5 array with this property with entries chosen from {0,1,2}. If this is too easy try to find a 7x7 array with entries from {0,1,2,3,4}, a 11x11 array with entries from {0,1,...,6,7} and a 13x13 arrays with entries from {0,1,...,7,8}.  This will probably require computer assistance.

The first 100 people who answer all four parts correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Answer:

           5x5 array with entries {0,1,2}

          a(i1,j1)+a(i2,j2) not equal to a(i1,j2)+a(i2,j1) is equivalent to a(i1,j1)-a(i1,j2) not equal to a(i2,j1)-a(i2,j2).  Therefore the row wise differences between any pair of columns j1 and j2 must be distinct.  Similarly the column wise differences between any pair of rows j1 and j2 must be distinct.  With entries from {0,1,2} the possible differences are {-2,-1,0,1,2} so each must appear exactly once between each pair of rows or columns.  Each row contains at least two pairs of equal elements.  So there are least 10 pairs of equal elements considering all 5 rows.  But there are only 10 pairs of columns.  So each row must contain exactly two pairs of equal elements which means no element can appear 3 times.  This means there are at most two 0's and two 2's in each row.  So there are at most 4 differences of +2 or -2 in that row.  So considering all 5 rows there are at most 20 row wise differences of +2 or -2. Now each pair of columns contains one row wise difference of 2 and one of -2 or 20 in all.  So each row must contain two 0's, two 2's and one 1.  Similarly for the columns.  So by permuting rows and columns we can put the array in the following form:

          0  0  1  2  2
          0  a     c  c
          1
          2  b
          2  b

          Now the entry marked a must be 2 in order to obtain a row wise difference of -2 between the first pair of columns.  Also one of entries marked b must be a 0 in order to obtain a difference of 2. Similarly for the entries marked c.  So we now have (permuting if necessary):

          0  0  1  2  2
          0  2  c  0  d
          1  a
          2  0
          2  b

          The entry marked a cannot be 1 as this would mean two row wise differences of 0 in the first pair of columns.  Since we already have two 0's in the second column this means a=2 which implies b=1. Similarly c=2, d=1.  So we now have:

          0  0  1  2  2
          0  2  2  0  1
          1  2  b  d
          2  0  c  a
          2  1

          Since each row and column contains exactly one 1 the entry marked a must be the fifth 1.  The entry marked b must be 0 in order to obtain a row wise difference of 2 between the second and third columns.  Also the entry marked c must be 2 in order to obtain a row wise difference of -2 between the second and third columns.  Similarly
  d=2.  This leaves:

          0  0  1  2  2
          0  2  2  0  1
          1  2  0  2
          2  0  2  1
          2  1

          Now since each row and column contains two 0's, one 1 and two 2's it is easy to fill in the remaining elements.

          0  0  1  2  2
          0  2  2  0  1
          1  2  0  2  0
          2  0  2  1  0
          2  1  0  0  2

          This must still be checked which can be done by considering each pair of columns.

          7x7, 11x11 and 13x13 arrays

          For these larger sizes we look for solutions of a particular type.  Suppose p is a prime and let A be a pxp array with entries a(i,j)=(i-1)*(j-1) mod p.  It is easy to see that A satisfies the property mod p.  Also we may add (mod p) a constant to any row or column of A and A will still satisfy the property mod p.  Clearly A will also satisfy the property over the integers.  So starting with A we search for constants to add to the rows and columns of A to minimize the size of the entries.  For example when p=3 we start with

          0  0  0
          0  1  2
          0  2  1

  and by adding 1 to the third row and third column mod p we obtain.

          0  0  1
          0  1  0
          1  0  0

  For p=5,7,11,13 we obtain the following arrays.

          0  1  0  2  2
          0  2  2  0  1
          2  0  1  0  2
          1  0  2  2  0
          2  2  0  1  0

          0  2  2  0  3  4  3
          0  3  4  3  0  2  2
          3  0  2  2  0  3  4
          2  0  3  4  3  0  2
          4  3  0  2  2  0  3
          2  2  0  3  4  3  0
          3  4  3  0  2  2  0

          0  1  5  1  0  2  7  4  4  7  2
          0  2  7  4  4  7  2  0  1  5  1
          4  7  2  0  1  5  1  0  2  7  4
          1  5  1  0  2  7  4  4  7  2  0
          2  7  4  4  7  2  0  1  5  1  0
          7  2  0  1  5  1  0  2  7  4  4
          5  1  0  2  7  4  4  7  2  0  1
          7  4  4  7  2  0  1  5  1  0  2
          2  0  1  5  1  0  2  7  4  4  7
          1  0  2  7  4  4  7  2  0  1  5
          4  4  7  2  0  1  5  1  0  2  7

          0  7  3  1  1  3  7  0  8  5  4  5  8
          0  8  5  4  5  8  0  7  3  1  1  3  7
          7  3  1  1  3  7  0  8  5  4  5  8  0
          8  5  4  5  8  0  7  3  1  1  3  7  0
          3  1  1  3  7  0  8  5  4  5  8  0  7
          5  4  5  8  0  7  3  1  1  3  7  0  8
          1  1  3  7  0  8  5  4  5  8  0  7  3
          4  5  8  0  7  3  1  1  3  7  0  8  5
          1  3  7  0  8  5  4  5  8  0  7  3  1
          5  8  0  7  3  1  1  3  7  0  8  5  4
          3  7  0  8  5  4  5  8  0  7  3  1  1
          8  0  7  3  1  1  3  7  0  8  5  4  5
          7  0  8  5  4  5  8  0  7  3  1  1  3

          It would be of interest to find good arrays that can not be constructed in this way.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Chuck Carroll (10.01.2005 @03:11:11 PM EDT)
• Wolfgang Kais (10.03.2005 @07:07:00 PM EDT)
• Daniel Bitin (10.04.2005 @08:29:17 AM EDT)
• Eugene Vasilchenko (10.05.2005 @12:52:44 AM EDT)
• Marco Rolando (10.05.2005 @05:25:01 AM EDT)
• Ardian Kristanto Poernomo (10.05.2005 @02:43:36 PM EDT)
• Yong Liu (10.05.2005 @03:37:11 PM EDT)
• Rohit Das (10.05.2005 @06:28:15 PM EDT)
• John Hubenschmidt (10.06.2005 @02:14:14 PM EDT)
• Bertram Felgenhauer (10.06.2005 @11:57:23 PM EDT)
• Michael Brand (10.07.2005 @10:01:40 AM EDT)
• Emile Joubert (10.07.2005 @10:49:35 AM EDT)
• V. Balakrishnan (10.08.2005 @12:34:38 AM EDT)
• Viktor Medvedev (10.10.2005 @12:08:37 AM EDT)
• Robert Benea (10.10.2005 @04:28:42 AM EDT)
• David Friedman (10.10.2005 @12:32:53 PM EDT)
• Raicho Tchalkov (10.11.2005 @05:14:07 AM EDT)
• Kalyana Chakravarthy (10.11.2005 @01:02:11 PM EDT)
• Dave Biggar (10.12.2005 @01:00:15 AM EDT)
• Dharmadeep Muppalla (10.12.2005 @01:33:24 AM EDT)
• Piotr Zielinski (10.12.2005 @10:58:09 AM EDT)
• Tom Sirgedas (10.12.2005 @06:11:27 PM EDT)
• Patrick Beebe (10.12.2005 @06:49:02 PM EDT)
• Kin Keung Ma (10.13.2005 @01:13:21 PM EDT)
• Bin Zhao (10.13.2005 @02:16:23 AM EDT)
• John G. Fletcher (10.13.2005 @11:44:45 PM EDT)
• Se Kwon Kim (10.16.2005 @04:15:59 AM EDT)
• Ashutosh Mahajan (10.17.2005 @07:16:35 PM EDT)
• Kennedy and Slick (10.18.2005 @01:54:39 AM EDT)
• Zdenek Spacek (10.18.2005 @07:28:51 PM EDT)
• Shawn Simister (10.19.2005 @12:43:25 AM EDT)
• Vinay Gupta (10.20.2005 @09:18:19 AM EDT)
• Lucas Galfaso (10.26.2005 @02:54:15 AM EDT)
• Oleg Trott (10.27.2005 @09:28:52 AM EDT)
• Patricio Alva (10.27.2005 @05:39:35 PM EDT)
• Ananda Raidu (10.28.2005 @10:33:51 AM EDT)
• Devin Myers (10.28.2005 @11:43:37 AM EDT)
• Max Alekseyev (10.29.2005 @08:56:38 AM EDT)
• Liubing Yu (10.31.2005 @09:36:47 AM EDT)
• DaiLiang (10.31.2005 @09:02:15 PM EDT)