Hi, dooogle-ga:
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, mathtalk-ga |
Clarification of Answer by
mathtalk-ga
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, mathtalk-ga
|
Clarification of Answer by
mathtalk-ga
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, mathtalk-ga
|
