|
Question:
Matrix Bound
Suppose that each entry in a 2k-1 by 2k-1 matrix M (k is a natural number) is a
real number of magnitude not exceeding 1 (that is, absolute value of each entry
is less than or equal to 1). Suppose also that these entries have been
carefully chosen and arranged so that the four entries in every 2 by 2 submatrix
add up to zero. Prove, then, that the sum of all the entries in M cannot exceed
2k-1. Answer:
We are given a 2k-1 by 2k-1 matrix with the
special property that the elements of every 2x2 submatrix sum to 0, and are
asked to find the sum of all of the elements. We can subtract any 2x2
submatrix without affecting thes whole sum because the elements sum to 0
anyway, and my solution exploits this. Consider The following method of 2x2
submatrix removal: Draw a diagonal line from the upper left corner to the
lower right corner. Beginning from the upper right corner, add a line of
((2k-2)/2 = k-1) non-overlapping 2x2 matrices approaching the upper left
corner. On the next line down, beginning from the most upper right not covered
by a matrix, add a line of ((k-1)-1 = k-2) nonoverlapping 2x2 matrices going
left. Continue this process of adding k-1-(n/2) matrices to line n (matrix
indexed from 0 to 2k-2) until k-1-(n/2) = 0, or equally expressed as n = 2k-2.
What we now have is a rough triangle of elements that do not affect the
overall sum of the whole matrix.
Now take this rough triangle and symmetrically
flip it over the diagonal line we drew from the upper left corner to the lower
right. Suppose we remove both of these rough triangles from the overall sum:
We are left with this diagonal line we drew originally, only now it it
composed of alternating elements that were never subtracted, and elements that
were subtracted twice. This line has no two elements in the same row or
column, so there must be 2k-1 elements in it. Since everything not on this
diagonal sums to 0 anyway, we can consider only this diagonal when considering
the sum of the whole. And since each element can have magnatude up to 1, we
know that the sum of this entire matrix can be at most 2k-1.
- Stefan Dorsett
Also Sean Simon has neatly wrote an
inductive proof in
LaTeX.
|
