IMO 1971 SL 11

Origin: POL

Problem

The matrix ⎛ ⎜ ⎝ a11 . . . a1n ... \cdot \cdot \cdot ... an1 . . . ann ⎞ ⎟ ⎠ satisfies the inequality n j=1 |aj1x1 + \cdot \cdot \cdot + ajnxn| \leqM for each choice of numbers xi equal to \pm1. Show that |a11 + a22 + \cdot \cdot \cdot + ann| \leqM.

Solution

We use induction. The statement for n = 1 is trivial. Suppose that it holds for n = k and consider n = k + 1. From the given condition, we have k  j=1 |aj,1x1 + \cdot \cdot \cdot + aj,kxk + aj,k+1| +|ak+1,1x1 + \cdot \cdot \cdot + ak+1,kxk + ak+1,k+1| \leqM, k  j=1 |aj,1x1 + \cdot \cdot \cdot + aj,kxk −aj,k+1| +|ak+1,1x1 + \cdot \cdot \cdot + ak+1,kxk −ak+1,k+1| \leqM for each choice of xi = \pm1. Since |a + b| + |a −b| \geq2|a| for all a, b, we obtain k  j=1 |aj1x1 + \cdot \cdot \cdot + ajkxk| + 2|ak+1,k+1| \leq2M, that is, k  j=1 |aj1x1 + \cdot \cdot \cdot + ajkxk| \leqM −|ak+1,k+1|. Now by the inductive assumption k j=1 |ajj| \leqM −|ak+1,k+1|, which is equivalent to the desired inequality.