嘿，这个问题很有意思，咱们一步步来分析，最终可以证明方程的解x的每个元素只能是-1、0或1，下面是具体的推导过程：

前提回顾 #

先明确已知条件：

• $M$ 是 $n \times n$ 的可逆0-1矩阵，每一列的元素和为 $k$（即每列恰好有 $k$ 个1，$n-k$ 个0），且 $k \notin {0,n}$（否则矩阵列全0或全1，必然不可逆）
• $b$ 是0-1向量，元素和也为 $k$
• 我们需要求解 $Mx = b$，并判断 $x$ 的元素取值范围

步骤1：推导解的元素和为1 #

对等式 $Mx = b$ 两边取所有元素的和：
$$
\sum_{i=1}^n (Mx)i = \sum{i=1}^n b_i
$$
左边展开后交换求和顺序：
$$
\sum_{i=1}^n \sum_{j=1}^n M_{ij}x_j = \sum_{j=1}^n x_j \sum_{i=1}^n M_{ij}
$$
因为每列的和为 $k$，右边的元素和为 $k$，代入得：
$$
\sum_{j=1}^n x_j \cdot k = k
$$
由于 $k \neq 0$，两边除以 $k$ 可得：
$$
\sum_{j=1}^n x_j = 1
$$

步骤2：证明解的元素都是整数 #

因为 $M$ 是整数矩阵且可逆，其行列式 $\det(M)$ 是整数，伴随矩阵 $\text{adj}(M)$ 的元素也都是整数，因此 $M$ 的逆矩阵可以表示为：
$$
M^{-1} = \frac{1}{\det(M)} \cdot \text{adj}(M)
$$
于是解 $x = M^{-1}b = \frac{1}{\det(M)} \cdot \text{adj}(M)b$，其中 $\text{adj}(M)b$ 是整数向量，所以 $x$ 的元素都是有理数，分母整除 $\det(M)$。

假设 $x_j = \frac{p_j}{q}$（$q$ 是 $\det(M)$ 的正因数，$p_j$ 是整数，且 $\gcd(p_j,q)=1$），对于任意行 $i$，有：
$$
\sum_{j: M_{ij}=1} \frac{p_j}{q} = b_i \implies \sum_{j: M_{ij}=1} p_j = b_i q
$$
右边是整数，左边也是整数，这没问题。但如果 $q>1$，由于 $M$ 可逆，任意两列不相同，必然存在某行 $i$ 使得该行仅在列 $j$ 处为1（或仅在少数列处为1），此时左边的和为单个 $p_j$，而 $p_j \not\equiv 0 \mod q$，导致左边无法等于右边的 $b_i q$（后者是 $q$ 的倍数），矛盾。因此 $q=1$，即 $x$ 的元素都是整数。

步骤3：证明元素只能是-1、0或1 #

假设存在某个 $x_j = t$，且 $|t| \geq 2$：

• 如果 $t \geq 2$，由 $\sum x_j =1$ 可知，其余元素的和为 $1-t \leq -1$。考虑列 $j$ 对应的 $k$ 个行（这些行在列 $j$ 处为1），对这些行有：
  $$
  t + \sum_{m \neq j, M_{im}=1} x_m = b_i \in {0,1}
  $$
  移项得 $\sum_{m \neq j, M_{im}=1} x_m = b_i - t \leq 1-2=-1$。但由于 $M$ 可逆，列 $j$ 不是全1，必然存在行 $i'$ 在列 $j$ 处为0，该行的和 $\sum_{m: M_{i'm}=1}x_m = b_{i'} \in {0,1}$，但这些 $x_m$ 都属于其余元素，和 $\leq -1$，与 $b_{i'} \geq0$ 矛盾。
• 如果 $t \leq -2$，同理，其余元素的和为 $1-t \geq3$，列 $j$ 对应的行的和为 $b_i -t \geq0 -(-2)=2$，但 $b_i$ 最大为1，矛盾。

因此不存在 $|t| \geq2$ 的元素，即 $x$ 的每个元素只能是-1、0或1。

备注：内容来源于stack exchange，提问作者Augustin Pan