Date: Wed, 11 Feb 1998 11:26:21 +0000
From: Joshua Bao <xxb1@psu.edu>
To: Dave Rusin <rusin@math.niu.edu>
Subject: Re: Diophantine Equations

Dave Rusin wrote:

> I'm almost certain there is no closed form for the number you seek. This is
> usually called the "postage stamp problem". It may be discussed in
> Guy's "Unsolved Problems in Number Theory";
>
> dave

Thank you for your help.  I also have another somewhat related inquiry.
It comes from a problem that I found.  I don't know if a solution exists.
Suppose that we have an MxN grid of positive integers which can undergo the
following transformations:
1)  Subtract 1 from one element and all of its neighbors.
2)  Add 1 to one element and all of its neighbors.
A neighbor is defined as elements directly adjacent to the number (above or
below, left or right, excluding diagonals).
Example, for a plate of the shape:

                        5 2 1 3 8
                        6 8 1 2 2
                        4 6 5 2 9

Using transform 2) in the position (2,3) leads to the board:

                        5 2 2 3 8
                        6 9 2 3 2
                        4 6 6 2 9

and then, using 1) on (1,4) the following board is obtained:

                        5 2 1 2 7
                        6 9 2 2 2
                        4 6 6 2 9

Is it possible to describe a sequence of moves that should lead to a grid where
all the elements have
the same value x ?  If so what is the minimum number of moves?

I would really appreciate it if you could help me or referr me to some
references.


--
- Josh Bao
  SCAHS(Class of 1998) CTY-93 YSSP-95 RSI-97 SET Member
  <xxb1@psu.edu> <jbao@mit.edu> <rsi97@mit.edu> <ysp95@mit.edu>
  <hscomputing@delos.com> <hs-aces@delos.com>   Home Page -
  http://web.mit.edu/jbao/www/
  "Always do what you love to do, and justify that love."

==============================================================================

Date: Wed, 11 Feb 1998 11:04:29 -0600 (CST)
From: Dave Rusin <rusin>
To: xxb1@psu.edu
Subject: Re: Diophantine Equations

What do you allow around the edges? Can I increase just one edge cell (e.g.
the (1,3) cell) on the grounds that this is just the visible effect of
a type-1 move centered at the (0,3) spot? How about moves centered at
positions like  (1,x): is it your intention to allow increasing/decreasing
precisely the entries (1,x-1) (1,x) (1,x+1) and (2,x) ?

If it weren't for edge effects, it would be easy to show that NOT all
grids can be reduced to a constant grid. If  w  is a primitive sube root of
unity and  I = sqrt(-1), we can associate to any grid the complex number
S = sum(  x[i,j] w^i I^j ); then your allowable moves change  S  by
adding or subtracting
	w^i I^j * ( 1 + w^(-1) + w + I^(-1) + I ) = 0
That is,  S  is an invariant under the proposed moves. The state to which
you hope to transform the grid has  S = 0  if the number of columns is
a multiple of  3, say; so an initial grid filled with zeroes except for
a lone  1  somewhere cannot possibly be transformed to a constant grid.

As I say, the previous paragraph assumes no moves are allowed along the
edges (or more generally that no moves are allowed which alter  S).

dave
==============================================================================

Date: Wed, 11 Feb 1998 18:22:18 +0000
From: Joshua Bao <xxb1@psu.edu>
To: Dave Rusin <rusin@math.niu.edu>
Subject: Re: Diophantine Equations

Dave Rusin wrote:

> What do you allow around the edges? Can I increase just one edge cell (e.g.
> the (1,3) cell) on the grounds that this is just the visible effect of
> a type-1 move centered at the (0,3) spot?

No.  A move has to be centered on a cell that exist on the grid (i.e., the cell
(i,j) with 1<=i<=mand 1<=j<=n).

> How about moves centered at
> positions like  (1,x): is it your intention to allow increasing/decreasing
> precisely the entries (1,x-1) (1,x) (1,x+1) and (2,x) ?

Yes.  A neighbor is increased or decreased as long as both it and the chosen
center exists on the grid.I would like to know 1) if all grids are transferable
2) if there is a sytematic process of doing so.
I apologize for the imprecision of the statement of the problem.  Thank you for
your help.



J. Bao
==============================================================================

Date: Wed, 11 Feb 1998 18:24:02 +0000
From: Joshua Bao <xxb1@psu.edu>
To: Dave Rusin <rusin@math.niu.edu>
Subject: Addendum

Naturally we must assume that n,m>=3.  Thanks
==============================================================================

Date: Sun, 15 Feb 1998 15:09:12 +0000
From: Joshua Bao <xxb1@psu.edu>
To: Dave Rusin <rusin@math.niu.edu>
Subject: Re: Addendum

Dave Rusin wrote:

> > Naturally we must assume that n,m>=3.  Thanks
>
> Au contraire, I would argue that there's no reason to disallow  m,n = 1, 2.
> Those cases fit just fine into the framework. Let me show you what I came up
> with. In return, let me ask you to tell me how this particular question arose:
> I had a good time playing with some of the data during the day!

Thank you for the extensive analysis !! A special case of the problem comes from a
chinesepuzzles book.  I would also like to know a way to find 'move's to transfer
the given matrix to the form of xJ(all elements are same integer) where the x is an
given integer.  Clearly, this is much easier - all we need to do is solve a system
of linear integer (diophantine) equations.  Is there a systematic method of doing
this (with matrix and integer operations), particularly when G/H is infinite ?
Thanks.

                                                Sincerely,

                                                                    J. Bao
==============================================================================

Date: Mon, 16 Feb 1998 10:48:39 -0600 (CST)
From: Dave Rusin <rusin>
To: xxb1@psu.edu
Subject: Re: Addendum

> I would also like to know a way to find 'move's to transfer
> the given matrix to the form of xJ(all elements are same integer)

I don't know if there's anything more elegant than brute force. You are
given an  mxn matrix  M  and  m*n  matrices  M(i,j)  of the same size;
you want to solve  m*n  equations in  m*n+1  unknowns  
	Sum  x(i,j) M(i,j) = M + x J

Well, that system of linear equations may be written as a single matrix
equation  A X = B  where  A  is an  m*n by m*n+1 matrix, and  X  and  B
are columns of the appropriate sizes. You can do row-reduction to determine
the solutions, but since you want to find all _integer_ solutions, you
need to do this without division. 

It turns out that you can reduce all integer matrices to a canonical
form this way (I think it's usually called "Smith normal form"). If
you view ordinary row-reduction as writing every matrix  A  in the 
form  U Z V  with  U  and  V  invertible and  Z  of the special form
	[ identity matrix	possible zeros ]
	[ possible zeros	possible zeros ]
then the right statement for integer matrices is that one can do
row-reduction without division and write  A = U Z V  where  U  and  V  are
integral matrices with integral inverses, and  Z  has the form
	[ diagonal matrix	possible zeros ]
	[ possible zeros	possible zeros ]
where the diagonal entries satisfy  d1 | d2 | d3 | ...  and all  d_i > 0.
With those conditions, Z  is unique  (U  and  V  are not).  In this case,
the equation   A X = B  may be written  Z (V X) = U^(-1) B  which is then
easy to solve: there is no solution unless the rows of  U^(-1)B  are zero
whenever the corresponding row of  Z  is zero (those are the rows at the
bottom of Z), and there is no solution unless the  i-th row of  U^(-1) B
is a multiple of  d_i. Otherwise there are solutions, and it's clear how
to get them: the i-th entry of  (VX)  must be  (i-th entry of  U^(-1)B)/(d_i)
and the entries of  VX  corresponding to the zero rows of  Z  are arbitrary.
That is, the solutions have the form
	(VX) = W_0 + [0, 0, ..., r_1, r_2, ...]^t
(I write []^t for the transpose of a row vector rather than trying to 
type out a column vector on my screen!) Here the  r_i  are arbitrary integers.
Then you have the solution to your original problem:
	X = V^(-1) ( W_0 + [0, 0, ..., r_1, r_2, ...]^t )
The entries of this column matrix describe the complete solution for your
unknowns  x(i,j).

Since I'm sure I've lost you at this point, let me do an example. Suppose
you wanted to find moves taking  M =
	[ 1 2 3 ]
	[ 4 8 6 ]
to a multiple of the identity. We need to find 7 unknowns which make
	sum( x(i,j) M(i,j) ) = M + x J,  that is,

	x(1,1)[ 1 1 0] + x(1,2)[1 1 1] + x(1,3)[0 1 1] +
	      [ 1 0 0]         [0 1 0]         [0 0 1]

	x(2,1)[ 1 0 0] + x(2,2)[0 1 0] + x(2,3)[0 0 1] - x [1 1 1] = [1 2 3] 
	      [ 1 1 0]         [1 1 1]         [0 1 1]     [1 1 1]   [4 8 6]

So I get 6 equations in the 7 unknowns. I peel off the coefficients of
each unknown in the usual fashion to get a matrix equation  A X = B :
	[ 1 1 0 1 0 0 -1] [x(1,1)]  [ 1 ]
	[ 1 1 1 0 1 0 -1] [x(1,2)]  [ 2 ]
	[ 0 1 1 0 0 1 -1]*[x(1,3)] =[ 3 ]
	[ 1 0 0 1 1 0 -1] [x(2,1)]  [ 4 ]
	[ 0 1 0 1 1 1 -1] [x(2,2)]  [ 8 ]
	[ 0 0 1 0 1 1 -1] [x(2,3)]  [ 6 ]
	                  [  x   ]

I can perform all the  "U^(-1)" work described above by simply doing row-
reduction using integer transformations in the usual methodical fashion:
	[ 1 0 0 0  1 -1  0 | -1 ]
	[ 0 1 0 0 -1  0  0 | -3 ]
	[ 0 0 1 0  1  1 -1 |  6 ]
	[ 0 0 0 1  0  1 -1 |  5 ]
	[ 0 0 0 0  2  0  0 |  6 ]
	[ 0 0 0 0  0  0  0 |  0 ]

I can further reduce using column operations, although this will alter the
solution set as I'll describe below. But by adding multiples of the first
four columns to the other columns, we can clear achieve the matrix  Z =
	[ 1 0 0 0 0 0 0 ]
	[ 0 1 0 0 0 0 0 ]
	[ 0 0 1 0 0 0 0 ]
	[ 0 0 0 1 0 0 0 ]
	[ 0 0 0 0 2 0 0 ]
	[ 0 0 0 0 0 0 0 ]
Here  d1=d2=d3=d4=1, d5=2. There is a zero row, but it's opposite a zero
in  the right-hand column "U^(-1)B". Likewise, the 5th entry of that
column (=6) is a multiple of  d5 (=2). Thus there are integer solutions
to the original problem. All the solutions to  Z (VX) = U^(-1)B  are
clearly of the form  (VX) = 
	[ -1 ] <- just dividing by  d1=1  here
	[ -3 ]
	[  6 ]
	[  5 ]
	[  3 ]  <- had to divide by d5=2 here
	[ r_1]  <- any arbitrary integer here
	[ r_2]  <-      ... and here  (Z  had two columns of zeros)
(That's  "W"  in the discussion above).

Now,  V  is the matrix for which  A' = ZV,  where  A'  was the result of
doing just the row operations. It's straightforward to see that  V^(-1) =
	[ 1 0 0 0 -1  1  0 ]
	[ 0 1 0 0  1  0  0 ]
	[ 0 0 1 0 -1 -1  1 ]
	[ 0 0 0 1  0 -1  1 ]
	[ 0 0 0 0  1  0  0 ]
	[ 0 0 0 0  0  1  0 ]
	[ 0 0 0 0  0  0  1 ]
(That is, V^(-1) is built from the same "blocks" as  A', with sign changes
off the diagonal.) Thus we recover our solutions  X  by multiplying  
(VX) by this  V^(-1)  on the left:
	[x(1,1)]  [-4+r1  ]
	[x(1,2)]  [0      ]
	[x(1,3)] =[3-r1+r2]
	[x(2,1)]  [5-r1+r2]
	[x(2,2)]  [3      ]
	[x(2,3)]  [r1     ]
	[  x   ]  [r2     ]

So now you know just what moves are possible to turn the original  M
into  xJ:  use  (-4+r1) of the first, none of the second, etc. Here,
a negative number of moves means to subtract 1's from certain spots
rather than add them, of course. Total number of moves is then
	|-4+r1| + |0| + |3-r1+r2| + |5-r1+r2| + |3| + |r1|
	= |-4+r1| + |3-r1+r2| + |5-r1+r2| + |r1| + 3.

The minimum value of this expression across the entire  r1-r2 plane
is  9,  which occurs in a box bounded by r1=0, r1=4, r2-r1=-3, r2-r1=-5.
So for example you could use  r1=4 and r2=0, meaning
	0, 0, -1, 1, 3, 4
moves of types 1, 2, ..., 6 respectively to go from  xJ = r2 J = the zero
matrix to the original matrix  M. You can check this directly.

As it turns out, there is enough of a pattern to the  M(i,j)  that you
can expect the matrix  A  to have a pattern, too, making it plausible
that the computations can be done more elegantly. But for small  m  and
n  this procedure is fairly efficient as it stands.

dave