MathDB

Matrix satisfy the inequality, prove the other inequality

Source:

September 22, 2010

linear algebramatrixInequalitycombinatorial inequalityIMO Shortlist

Problem Statement

The matrix

A=\begin{pmatrix} a_{11} & \ldots & a_{1n} \\ \vdots & \ldots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{pmatrix}

satisfies the inequality

\sum_{j=1}^n |a_{j1}x_1 + \cdots+ a_{jn}x_n| \leq M

for each choice of numbers

x_i

equal to

\pm 1

. Show that

|a_{11} + a_{22} + \cdots+ a_{nn}| \leq M.