一次方程组整数解

青青子衿

如果s和t都取整数的话，如下的不定方程参数解是不是会漏解呢？
\begin{align*}
15 x + 18 y + 24 z = 69\\
\\
\left\{
\begin{split}
x &= 1 + 8s \\
y &= 3 + 8t \\
z &= - 5s - 6t
\end{split}
\right.
\\
\\
(x,y,z)\overset{?}{=}(3, 8, -5)
\end{align*}
如何得到当s和t都取整数时的完全整数解？

hejoseph

青青子衿 发表于 2024-1-10 22:36
如果s和t都取整数的话，如下的不定方程参数解是不是会漏解呢？
\begin{align*}
15 x + 18 y + 24 z = 69\\

你上面的解的表达式不能表示全部整数解。方程本身不是最简，可以变为 $5x+6y+8z=23$，进而得到 $5x+6y=-8z+23$，$5x+6y=1$ 的一个特解是 $(x,y)=(-1,1)$，所以 $5x+6y=-8z+23$ 的所有整数解就是 $(x,y)=(6s+8z-23,-5s-8z+23)$，即 $5x+6y+8z=23$ 的所有整数解就是 $(x,y,z)=(6s+8t-23,-5s-8t+23,t)$。

hbghlyj

calcme.com/ 可以计算Smith Normal Form：docs.wiris.com/calcme/es/-en--commands/-en--linear-algebra/-en--smith-normal-form-basis.html
用Calc

用Define

hbghlyj

https://www.maplesoft.com/suppor ... Algebra%2FSmithForm

>	$\mathrm{with}\left(\mathrm{LinearAlgebra}\right):$

>	$A≔\mathrm{Matrix}\left(\left[\left[1,2x,2x^2+2x\right],\left[1,6x,6x^2+6x\right],\left[1,3,x\right]\right]\right)$

$A≔\left[\begin{array}{ccc}1& 2x& 2x^2+2x\\ 1& 6x& 6x^2+6x\\ 1& 3& x\end{array}\right]$

(1)

>	$S≔\mathrm{SmithForm}\left(A\right)$

$S≔\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& x^2+\frac{3}{2}x\end{array}\right]$

(2)

>	$\mathrm{Determinant}\left(A\right)$

$-8x^2-12x$

(3)

>	$\frac{\mathrm{lcoeff}\left(\right)}{}$

$x^2+\frac{3}{2}x$

(4)

>	$U,V≔\mathrm{SmithForm}\left(A,x,\mathrm{output}=\left[\text{'}U\text{'},\text{'}V\text{'}\right]\right):$

>	$\mathrm{map}\left(\mathrm{expand},U·A·V\right)$

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& x^2+\frac{3}{2}x\end{array}\right]$

(5)

hbghlyj

求  $\begin{array}l
x_1 + 2 x_2 + 3 x_3 + 4 x_4 + 5 x_5 + 6 x_6 + 7 x_7=28\\
x_1 + x_3 + x_5 + x_7=4\\
2 x_1 + 4 x_2 + 5 x_3 + 6 x_4 + x_5 + x_6 + x_7=20\\
x_1 + 4 x_2 + 2 x_3 + 5 x_4 + 2 x_5=14\\
x_3 + x_4 + 2 x_5 + 2 x_6 + 3 x_7=9
\end{array}$的整数解.   The Smith Normal Form page373

Solution

系数矩阵$A$计算得 $\operatorname{rank}A=5,\operatorname{null}A=2$
$\mathrm{SNF}(A)=UAV=\pmatrix{D\\&0_{2\times2}},D=\text{diag}(1,1,1,1,2)$.
常数列$c=(28,4,20,14,9)^t$
$c'=U^{-1}c=(-44,53,37,-50,22)^t$
$D^{-1} c'=(-44,53,37,-50,11)^t$
所以$x=(-44,53,37,-50,11,0,0)^{t}$是一个解.
$A$的零空间是$V$的最后2列张成的.
因此全部解 $\begin{array}{l}x_1=-44+29s+16t \\x_2=53-34s-18t \\x_3=37-23s-13t \\x_4=-50+33s+18t \\x_5=11-6s -4t \\x_6=s\\x_7=t\end{array}$   其中$s,t$为任意整数.

青青子衿 发表于 2024-1-10 14:36
如何得到当s和t都取整数时的完全整数解？

通过上述方法：

在 CalcMe 中计算：

smith_normal_form_basis($(15\,18\,24)$) 輸出$\left\{(1),(0\,0\,3),B\right\}$ 所以$(1)\cdot(15\,18\,24)\cdot B=(0\,0\,3)$，其中$B =\left(\begin{smallmatrix}2&0&1\\5&4&2\\-5&-3&-2\end{smallmatrix}\right)$ 我們想要求出$\left(\begin{smallmatrix}?\\?\\?\end{smallmatrix}\right)$使得$(0\,0\,3)\cdot\left(\begin{smallmatrix}?\\?\\?\end{smallmatrix}\right)=69$ 當然是$\left(\begin{smallmatrix}?\\?\\?\end{smallmatrix}\right)=\left(\begin{smallmatrix}s\\t\\\frac{69}3\end{smallmatrix}\right)$ 所以当s和t都取整数时的完全整数解为 $$B\cdot\pmatrix{s\\t\\\frac{69}3}=\pmatrix{2s+23\\5s+4t+46\\-5s-3t-46}$$

hbghlyj

摘自 Allen Hatcher 的书《Algebraic Topology》第 2.1 节 问题5：使用本节开头描述的 Δ-复形结构计算克莱因瓶的单纯同调群。

Figure 4. The homology of the Klein bottle.

We have
$$
C_2=\mathbb{Z}\langle U, L\rangle, \quad C_1=\mathbb{Z}\langle a, b, c\rangle, \quad C_0=\mathbb{Z}\langle v\rangle
$$
and
$$
\partial U=a+b-c, \quad \partial L=c+a-b, \quad \partial a=\partial b=\partial c=\partial v=0
$$
If follows that $Z_2=0 \cong H_2^{\Delta}(|K|)=0$, and $H_0^{\Delta} \cong \mathbb{Z}$. The first homology group has the presentation
$$
\mathbb{Z}\langle U, L\rangle \xrightarrow{P} \mathbb{Z}\langle a, b, c\rangle \rightarrow H_1^{\Delta} \rightarrow 0
$$
where $P$ is the $3 \times 2$ matrix
$$
P=\left[\begin{array}{rr}
1 & 1 \\
1 & -1 \\
-1 & 1
\end{array}\right]
$$
Using the Maple procedure ismith we can diagonalize $P$ over the integers
$$
D_0:=\left[\begin{array}{ll}
1 & 0 \\
0 & 2 \\
0 & 0
\end{array}\right]=A P B
$$
where
$$
A=\left[\begin{array}{ccc}
1 & 0 & 0 \\
1 & -1 & 0 \\
0 & 1 & 1
\end{array}\right], B=\left[\begin{array}{cc}
1 & -1 \\
0 & 1
\end{array}\right]
$$
This means that by choosing the $\mathbb{Z}$-basis $\mu_1:=A^{-1} a, \mu_2:=A^{-1} b, \mu_3=A^{-1} c$ in $\mathbb{Z}\langle a, b, c\rangle$, and the $\mathbb{Z}$-basis $e:=B U, f:=B L$ in $\mathbb{Z}\langle U, L\rangle$ we can represent the linear operator $P$ as the diagonal matrix $D_0$. We deduce that $H_1^{\Delta}$ has an equivalent presentation with three generators $\mu_1, \mu_2, \mu_3$ and two relations
$$
\mu_1=0,2 \mu_2=0
$$
Thus
$$
H_1^{\Delta} \cong \mathbb{Z}_2\left\langle\mu_2\right\rangle \oplus \mathbb{Z}\left\langle\mu_3\right\rangle
$$
Using the MAPLE procedure inverse we find that
$$
A^{-1}=\left[\begin{array}{ccc}
1 & 0 & 0 \\
1 & -1 & 0 \\
-1 & 1 & 1
\end{array}\right]
$$
so that $\mu_2$ is given by the 2 nd column of $A^{-1}$ and $\mu_3$ is given by the third column of $A^{-1}$
$$
\mu_2=c-b, \quad \mu_3=c .
$$

hbghlyj

hbghlyj 发表于 2024-10-22 17:23
where $P$ is the $3 \times 2$ matrix$$P=\left[\begin{array}{rr}1 & 1 \\1 & -1 \\-1 & 1\end{array}\right]$$

这里作一下解释：$P$ 的各列取自以下方程中的 $a,b,c$ 系数：
$$
\partial U = (1)a + (1)b + (-1)c,$$$$
\partial L = (1)a + (-1)b + (1)c$$