题目
给定一个\(m\times n\)的实数矩阵。你可以在任意时刻选择一整行或一整列，把其中所有数同时乘以\(-1\)（即翻转符号）。问：是否总能经过若干次操作，使所有行和与列和都变为非负？
分析
答案是可以。
设当前矩阵所有元素之和为\(S=\sum_{i=1}^m\sum_{j=1}^n a_{ij}\)。
- 若某一行的行和为\(r_i<0\)，翻转该行后，总和变化为：\(S' = S-2r_i > S\)，也就是说\(S\)严格增大。
- 若某一列的列和为\(c_j<0\)，翻转该列后，同理有\(S' = S-2c_j > S\)。
因此，只要还有负的行和或列和，就翻转它。每次都会使\(S\)严格增大。
下面说明为什么“可达到的状态数”至多是\(2^{m+n}\)，而不是\(2^{mn}\)：
- 每一行是否被翻转，记一个二值变量\(x_i\in\{0,1\}\)（\(i=1,\dots,m\)）。
- 每一列是否被翻转，记一个二值变量\(y_j\in\{0,1\}\)（\(j=1,\dots,n\)）。
- 对任意元素\(a_{ij}\)，最终符号只由\(x_i\)与\(y_j\)决定：
\[ a_{ij}\longmapsto(-1)^{x_i+y_j}a_{ij}.\]
也就是说，一个状态由\((x_1,\dots,x_m,y_1,\dots,y_n)\)决定，总共有\(2^m\cdot2^n=2^{m+n}\)种选择，所以可达到状态数至多\(2^{m+n}\)。
\(2^{mn}\)对应的是“每个元素都可独立翻转”的模型；但本题操作只能整行或整列翻转，元素之间有耦合约束，不能独立选择每个\(a_{ij}\)的符号，因此不应按\(2^{mn}\)计数。
由于状态数有限且每一步都使\(S\)严格增大，过程不可能无限进行，最终会停在某个状态。
在终止状态中，不可能存在负行和或负列和；否则还可继续翻转并增大\(S\)，与“终止”矛盾。
故最终一定能得到：所有行和、列和都非负。