MathDB

Let

n\ge 2

be an integer. Elwyn is given an

n\times n

table filled with real numbers (each cell of the table contains exactly one number). We define a rook set as a set of

n

cells of the table situated in

n

distinct rows as well as in n distinct columns. Assume that, for every rook set, the sum of

n

numbers in the cells forming the set is nonnegative.\\ \\ By a move, Elwyn chooses a row, a column, and a real number

a,

and then he adds

a

to each number in the chosen row, and subtracts

a

from each number in the chosen column (thus, the number at the intersection of the chosen row and column does not change). Prove that Elwyn can perform a sequence of moves so that all numbers in the table become nonnegative.

Problem Statement