有理矩阵与有理向量构成的线性方程组Ax=b何时存在整数解？

Great question! Let's break this down step by step, starting from basics and moving to the key conditions.

First, let's restate the problem clearly: we have $A \in \mathbb{Q}^{m \times n}$ (a rational matrix) and $b \in \mathbb{Q}^m$ (a rational vector), and we want to know when there exists an integer vector $x \in \mathbb{Z}^n$ such that $Ax = b$.

Step 1: Reduce to an integer linear system #

Since all entries of $A$ and $b$ are rational, we can find a positive integer $k$ that clears all denominators—specifically, $k$ is the least common multiple (LCM) of all denominators in $A$ and $b$. Multiplying both sides of $Ax = b$ by $k$ gives us an equivalent integer linear system:
$$A'x = b'$$
where $A' = kA \in \mathbb{Z}^{m \times n}$ and $b' = kb \in \mathbb{Z}^m$. Now the problem reduces to: when does this integer system have an integer solution?

Step 2: Necessary and sufficient conditions #

For the integer system $A'x = b'$ (and thus the original rational system) to have an integer solution, two conditions must hold:

Condition 1: The system has a rational solution (a prerequisite) #

First, the original system must have at least one solution in $\mathbb{Q}^n$. This is equivalent to the rank condition:
$$\text{rank}(A) = \text{rank}([A \mid b])$$
where $[A \mid b]$ is the augmented matrix of the system. If there's no rational solution at all, there can't be an integer solution.

Condition 2: Integer compatibility (the key solvability condition) #

Assuming a rational solution exists, we need to ensure that we can find an integer solution. The most concrete way to check this is using the Hermite Normal Form (HNF) of $A'$:

• We can transform $A'$ into its HNF $H = PA'$, where $P$ is a unimodular integer matrix (invertible with integer inverse).
• The system $A'x = b'$ is equivalent to $Hx = Pb'$. Since $H$ is an upper-triangular integer matrix with positive diagonal entries $h_{ii}$, and for each $i < j$, $0 \leq h_{ij} < h_{ii}$, the system has an integer solution if and only if each diagonal entry $h_{ii}$ divides the corresponding entry in $Pb'$ (i.e., $h_{ii} \mid (Pb')_i$ for all $i$).

Alternatively, using the Smith Normal Form (SNF) of $A'$:

• Transform $A'$ into SNF $S = PA'Q$, where $P, Q$ are unimodular integer matrices. Let $y = Q^{-1}x$ (so $x$ is integer iff $y$ is integer).
• The system becomes $Sy = Pb'$. $S$ is diagonal: $\text{diag}(s_1, s_2, ..., s_r, 0, ..., 0)$ where $s_1 \mid s_2 \mid ... \mid s_r$ are positive integers. The system has an integer solution iff:
  • For all $i > r$, $(Pb')_i = 0$ (this enforces the rank condition from Condition 1).
  • For all $i \leq r$, $s_i \mid (Pb')_i$.

A simpler practical check (for small systems) #

For small systems, you can:

1. Find any rational solution $x_0 \in \mathbb{Q}^n$. Write $x_0 = (1/t)z$ where $z \in \mathbb{Z}^n$ and $t$ is a positive integer (clear denominators of $x_0$).
2. The general solution to $Ax = b$ is $x = x_0 + y$, where $y$ is in the null space of $A$ (over $\mathbb{Q}$). We need to check if there exists a $y$ in the integer null space such that $x_0 + y$ is integer—meaning $tz$ can be expressed as $t x_0 + t y$, where $t y$ is an integer vector from the scaled null space.

Examples #

• Example 1: $A = \begin{bmatrix} 1/2 & 1/3 \end{bmatrix}$, $b = [1]$. Multiply by 6 (LCM of 2 and 3) to get $A' = \begin{bmatrix} 3 & 2 \end{bmatrix}$, $b' = [6]$. The system $3x_1 + 2x_2 = 6$ has integer solutions (e.g., $x_1=2, x_2=0$), so the original system has an integer solution.
• Example 2: $A = \begin{bmatrix} 1/2 \end{bmatrix}$, $b = [1/3]$. Multiply by 6 to get $3x = 2$. 3 does not divide 2, so no integer solution exists for the integer system, hence none for the original rational system.

内容的提问来源于stack exchange，提问作者Piwaldo