Hi, doooglega:
Let G be "stochastic" (a nonnegative matrix with row sums equal to 1),
and let x,y be column vectors of equal length such that:
Gx = y
We will show that:
(max y_i  min y_i) <= T(G) (max x_i  min x_i)
i i i i
where the components of x,y are x_i and y_i, respectively, and where:
T(G) = (1/2) SUM max  g_{i,k}  g_{j,k} 
k i,j
the indicated sum being taken over the columns of G of the maximum
"deviation" between any two entries of G in each column.
Proof:
First note that (max y_i  min y_i) = max (y_i  y_j).
i i i,j
It suffices therefore to produce an estimate of the form:
(y_i  y_j) <= T(G) (max x_k  min x_k)
k k
because we can then take a maximum of the left hand side over all i,j
to obtain the desired result.
Now recall by the definition of matrix multiplication that:
y_i  y_j = SUM g_{i,k} x_k  SUM g_{j,k} x_k
k k
= SUM (g_{i,k}  g_{j,k}) x_k
k
We have one small trick up our sleeves. Using the fact that the row
sums of G are each equal to 1, we know that for any constant a:
0 = SUM (g_{i,k}  g_{j,k}) * a
k
Thus we can subtract this from the previous equality, getting:
y_i  y_j = SUM (g_{i,k}  g_{j,k})*(x_k  a)
k
In particular we can estimate:
(g_{i,k}  g_{j,k})*(x_k  a) <= max g_{i,k}  g_{j,k}*x_k  a
i,j
Making the skillful choice of a = (1/2)(max x_k + min x_k) results in:
k k
x_k  a <= (1/2) (max x_i  min x_i)
i i
for if x_k were above a, then:
x_k  a = x_k  a
<= (max x_i)  a
i
= (1/2)(max x_i)  (1/2)(min x_i)
i i
= (1/2)(max x_i  min x_i)
i i
and similarly if x_k were below a, then:
x_k  a = a  x_k
<= a  (min x_i)
i
= (1/2)(max x_i)  (1/2)(min x_i)
i i
= (1/2)(max x_i  min x_i)
i i
Putting these estimate together gives the desired inequality:
y_i  y_j = SUM (g_{i,k}  g_{j,k})*(x_k  a)
k
= SUM max g_{i,k}  g_{j,k}*x_k  a
k i,j
= SUM max g_{i,k}  g_{j,k} * (1/2)(max x_i  min x_i)
k i,j i i
= (1/2) SUM max g_{i,k}  g_{j,k} * (max x_i  min x_i)
k i,j i i
= T(G) (max x_i  min x_i)
i i
QED
* * * * * * * * * * * * * * * * * * * * * *
Careful analysis of the steps in this proof will show that we did not
use any facts about G except that its row sums are equal. To see that
the result cannot be proven for arbitrary square matrices, even if we
assume the nonnegativity of x,y and G, consider:
Example: Let x = (1,0)', prime denoting transpose, and:
/ 4 0 \
G =  
\ 0 1 /
so that y = Gx = (4,0)'. Now T(G) = (1/2)*(4+1) = 5/2, but:
(max x_i  min x_i) = 1
i i
(max y_i  min y_i) = 4
i i
The inequality 4 <= T(G) * 1 is therefore not valid in this case.
regards, mathtalkga 
Clarification of Answer by
mathtalkga
on
14 Jul 2005 21:58 PDT
Oops, I dropped the inequality marks in moving the last few steps of
the proof into final form. I should have written:
Putting these estimates together gives the desired inequality:
y_i  y_j = SUM (g_{i,k}  g_{j,k})*(x_k  a)
k
<= SUM max g_{i,k}  g_{j,k}*x_k  a
k i,j
<= SUM max g_{i,k}  g_{j,k} * (1/2)(max x_i  min x_i)
k i,j i i
= (1/2) SUM max g_{i,k}  g_{j,k} * (max x_i  min x_i)
k i,j i i
= T(G) (max x_i  min x_i)
i i
Sorry for the confusion!
regards, mathtalkga

Clarification of Answer by
mathtalkga
on
14 Jul 2005 22:53 PDT
As a more substantive correction, I noticed that I interchanged the
order of summation and maximization in the way I defined T(G). You
wrote:
T(G) = (1/2) max SUM g_{i,k}  g_{j,k}
i,j k
and I wrote:
T(G) = (1/2) SUM max  g_{i,k}  g_{j,k} 
k i,j
The proof is probably a little simpler with your definition. We would
again write the difference of two components of y as the row & column
products, and introduce the parameter a as before (because two rows of
G have equal sums):
y_i  y_j = SUM (g_{i,k}  g_{j,k})*(x_k  a)
k
Estimate the right hand side by the triangle inequality, and choose a
to be halfway between the maximum and minimum entries of x so that
again:
x_k  a <= (1/2) (max x_i  min x_i)
i i
and we have the estimate, after moving the 1/2 outside the summation:
y_i  y_j <= (1/2) ( SUM g_{i,k}  g_{j,k} ) * (max x_k  min x_k)
k k k
By leaving i,j free on both sides of the inequality, we can now pass
to the maximum over i,j for both simultaneously:
(max y_i  min y_i) <= (1/2) max ( SUM g_{i,k}  g_{j,k} )
i,j k
* (max x_k  min x_k)
k k
= T(G) * (max x_i  min x_i)
i i
Note that I've freely changed the "bound" variable for minimum and
maximum components of x between i and k for (hopefully) clarity of
notation.
regards, mathtalkga
