Kvant Math Problem 80

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m03s
Source on kvant.digital

Problem

In the table $m\times n$, arbitrary numbers are placed. It is allowed to simultaneously change the sign of all numbers in any one column or all numbers in any one row. Prove that, by repeating this operation several times, it is possible to obtain a table in which the sum of the numbers in any column and the sum of the numbers in any row are non-negative.

A. S. Schwarz

Exploration

For a $1\times 1$ table the statement is trivial. For a $1\times n$ table, changing the sign of a column changes only one entry, so every entry can be made non-negative independently. Then the unique row sum and all column sums are non-negative.

For a $2\times 2$ table,

$$\begin{pmatrix} a&b\ c&d \end{pmatrix},$$

the operation amounts to multiplying rows and columns by signs $\pm1$. The final entry in position $(i,j)$ has the form $\varepsilon_i\delta_j a_{ij}$, where $\varepsilon_i,\delta_j\in{\pm1}$. The row sums become

$$\varepsilon_1(\delta_1 a+\delta_2 b),\qquad \varepsilon_2(\delta_1 c+\delta_2 d).$$

Once the column signs are fixed, the row signs may be chosen to make both row sums non-negative. The remaining condition is that the column sums are also non-negative after those choices.

This suggests considering some quantity that improves whenever a row or column with negative sum is flipped. The total sum of all entries is natural. If a row has sum $r<0$, then after changing its sign the total sum increases by $-2r>0$. The same holds for a column. Since only finitely many sign patterns exist, the process cannot continue forever if the total sum strictly increases at every step.

The crucial point is to show that a configuration with maximal total sum must already have all row and column sums non-negative. Otherwise one more sign change would increase the total sum further.

There is a possible hidden mistake here. One must verify carefully that maximizing the total sum among all reachable tables is legitimate. The set of reachable tables is finite because each row and each column can only be multiplied by $\pm1$. There are at most $2^{m+n}$ different sign choices, although some may coincide. Hence a maximum exists.

The argument then becomes extremely short. Choose a reachable table with maximal total sum. If some row sum were negative, flipping that row would increase the total sum, contradiction. The same applies to columns.

Problem Understanding

We are given an $m\times n$ table of arbitrary real numbers. We may repeatedly choose any row or any column and multiply all entries in it by $-1$. The task is to prove that after finitely many such operations we can reach a table in which every row sum and every column sum is non-negative.

This is a Type B problem. The statement itself must be proved.

The core difficulty is that changing the sign of one row affects all column sums, and changing the sign of one column affects all row sums. A naive greedy strategy could oscillate. The right viewpoint is global: among all reachable sign configurations, select one maximizing the total sum of all entries.

Proof Architecture

First, prove that only finitely many different tables can be obtained from the initial one, because each row and each column receives an independent sign $\pm1$.

Second, prove that among all obtainable tables there exists one with maximal total sum of entries.

Third, prove that in such a maximal table every row sum is non-negative, because flipping a row with negative sum would increase the total sum.

Fourth, prove analogously that every column sum is non-negative.

The most delicate point is the third lemma. One must compute exactly how the total sum changes under a row flip and verify that the increase is strictly positive when the row sum is negative.

Solution

Consider all tables obtainable from the initial one by a sequence of allowed operations. Every operation changes the sign of an entire row or an entire column.

For each row $i$, let $\varepsilon_i\in{\pm1}$ denote whether that row has been flipped an even or odd number of times. For each column $j$, let $\delta_j\in{\pm1}$ denote whether that column has been flipped an even or odd number of times. Then the entry $a_{ij}$ of the original table becomes

$$\varepsilon_i\delta_j a_{ij}.$$

Hence every obtainable table is determined by the $m+n$ signs

$$\varepsilon_1,\dots,\varepsilon_m,\delta_1,\dots,\delta_n.$$

There are only finitely many such choices, therefore only finitely many obtainable tables.

Among all obtainable tables, choose one for which the total sum of all entries,

$$S=\sum_{i=1}^m\sum_{j=1}^n a_{ij},$$

is maximal.

We prove that in this table every row sum and every column sum is non-negative.

Assume that some row has negative sum. Denote this sum by

$$r=\sum_{j=1}^n a_{ij}, \qquad r<0.$$

Change the sign of that entire row. Every entry in the row changes from $a_{ij}$ to $-a_{ij}$. The contribution of this row to the total sum changes from $r$ to $-r$. Therefore the total sum of the whole table changes from $S$ to

$$S-2r.$$

Since $r<0$, we have $-2r>0$, so

$$S-2r>S.$$

This contradicts the choice of the table as one with maximal total sum.

Hence every row sum is non-negative.

Now assume that some column has negative sum,

$$c=\sum_{i=1}^m a_{ij}, \qquad c<0.$$

Changing the sign of that entire column changes the total sum from $S$ to

$$S-2c.$$

Since $c<0$, again we obtain

$$S-2c>S,$$

contradicting maximality of $S$.

Hence every column sum is non-negative.

We have proved that there exists an obtainable table in which all row sums and all column sums are non-negative. This completes the proof.

∎

Verification of Key Steps

The first delicate step is the finiteness argument. A careless proof might say merely that repeated operations eventually repeat a state, without proving the state space is finite. The precise reason is that each entry acquires the factor $\varepsilon_i\delta_j$, where every $\varepsilon_i$ and $\delta_j$ equals $\pm1$. Thus there are at most $2^{m+n}$ distinct outcomes.

The second delicate step is the computation of the change in the total sum after flipping a row. Suppose the row sum equals $r$. Before the flip, this row contributes $r$ to the total sum. After the flip, it contributes $-r$. The net change equals

$$(-r)-r=-2r.$$

If $r<0$, then $-2r>0$, so the total sum strictly increases. Forgetting the sign here would destroy the contradiction argument.

The third delicate step is the use of maximality. We do not claim that an arbitrary sequence of correcting negative rows and columns terminates. Such a claim would require a separate monotonicity proof. Instead, we select from the outset a table with maximal total sum among all reachable tables. The contradiction then uses only one additional flip, so no infinite process analysis is needed.

Alternative Approaches

Another proof uses an iterative procedure. Whenever a row or column has negative sum, flip it. Each such operation strictly increases the total sum of all entries. Since only finitely many tables are reachable, the process cannot continue indefinitely. When it stops, no row or column has negative sum, which is exactly the desired conclusion.

This proof is close in spirit to the maximality argument. The maximality approach is preferable because it isolates the key idea immediately and avoids discussing termination of an algorithmic process.