Integer Linear system

Integer linear system

For given \(\mathbf{A} \in \mathbb{Z}^{m \times n}\) and \(\mathbf{b} \in \mathbb{Z}^{m}\), consider to solve integer linear system \(\mathbf{Ax} = \mathbf{b}\) in \(\mathbf{x} \in \mathbb{Z}^{n}\). Let the Hermite normal form of \(\mathbf{A}\) be \(\mathbf{H} = \mathbf{AR}\), where \(\mathbf{R}\) is unimodular and \(\mathbf{H}\) is lower triangular. The given linear system is

\[\begin{split} \begin{pmatrix} H_{11} & & \mathbf{O} & \vdots \\ \vdots & \ddots & & \mathbf{0} \\ H_{r1} & \ldots & H_{rr} & \vdots \\ \ldots & \mathbf{0} & \ldots & \mathbf{O} \\ \end{pmatrix} \mathbf{y} = \mathbf{b}\end{split}\]

where \(\mathbf{y} := \mathbf{R}^{-1}\mathbf{x}\). A special solution, \(\mathbf{x}_{\mathrm{special}} = \mathbf{R}\mathbf{y}_{\mathrm{special}}\), is determined by Gaussian elimination if exists. A general solution for \(\mathbf{Hy}=\mathbf{0}\) is given by

\[\begin{split} \mathbf{y} &= \begin{pmatrix} 0 \\ \vdots \\ 0 \\ n_{r+1} \\ \vdots \\ n_{m} \end{pmatrix} \quad (\forall n_{r+1},\cdots, n_{m} \in \mathbb{Z}).\end{split}\]

Frobenius congruent

For given \(\mathbf{A} \in \mathbb{Z}^{m \times n}\) and \(\mathbf{b} \in \mathbb{Z}^{m}\), consider to solve Frobenius congruent \(\mathbf{Ax} \equiv \mathbf{b} \, (\mathrm{mod}\, \mathbb{R}/\mathbb{Z})\) for \(\mathbf{x} \in \mathbb{R}^{n}\). Let the Smith normal form of \(\mathbf{A}\) be \(\mathbf{D} = \mathbf{LAR}\), where \(\mathbf{L}\) and \(\mathbf{R}\) are unimodular matrices.

\[\begin{split} \mathbf{LAx} &= \mathbf{Lb} + \mathbb{Z}^{n} \\ \mathbf{Dy} &= \mathbf{v} + \mathbb{Z}^{n} \quad \mbox{where}\, \mathbf{y}:= \mathbf{R}^{-1} \mathbf{x},\, \mathbf{v}:= \mathbf{Lb} \\ \mathbf{y} &= \begin{pmatrix} \frac{v_{1}}{D_{11}} \\ \vdots \\ \frac{v_{r}}{D_{rr}} \\ 0 \\ \vdots \\ 0 \end{pmatrix} + \begin{pmatrix} \frac{1}{D_{11}} n_{1} \\ \vdots \\ \frac{1}{D_{rr}} n_{r} \\ 0 \\ \vdots \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ \vdots \\ 0 \\ a_{r+1} \\ \vdots \\ a_{m} \end{pmatrix} \quad (\forall n_{1}, \cdots, n_{r} \in \mathbb{Z}, \forall a_{r+1}, \cdots, a_{m} \in \mathbb{R})\end{split}\]

Modular integer linear system

For given \(\mathbf{A} \in \mathbb{Z}^{m \times n}\) and \(\mathbf{b} \in \mathbb{Z}^{m}\), consider to solve modular integer linear system \(\mathbf{Ax} \equiv \mathbf{b} \, (\mathrm{mod} \, q)\) in \(\mathbf{x} \in \mathbb{Z}^{n}\).

First, We consider finding one of solutions of \(\mathbf{Ax}=\mathbf{b} \, (\mathrm{mod} p^{k})\) for given \(\mathbf{A} \in \mathbb{Z}^{m \times n}\) and \(\mathbf{b} \in \mathbb{Z}^{m}\).

Let the Smith normal form of \(\mathbf{A}\) be \(\mathbf{D} = \mathbf{LAR}\), where \(\mathbf{L}\) and \(\mathbf{R}\) are unimodular matrices. Now it is sufficient to solve \(\mathbf{Dy} = \mathbf{Lb} \, (\mathrm{mod} p^{k})\) for \(\mathbf{y} \in \mathbb{Z}^{m}\). After we obtain \(\mathbf{y}\), we easily obtain the solution of the original linear systems as \(\mathbf{x} = \mathbf{Ry} \, (\mathrm{mod} p^{k})\).

We write the SNF as \(\mathbf{D} = \mathrm{diag}(d_{1}, \cdots, d_{r}, 0, \cdots)\). Then, the \(i\)th element of \(\mathbf{y}\) is determined by solving

\[d_{i} y_{i} = [\mathbf{Lb}]_{i} \quad (\mathrm{mod} \, p^{k})\]

for \(i=1, \cdots, r\). The above can be solved by the extended Euclidean algorithm. If \(\mathrm{GCD}(d_{i}, p^{k})\) does not divide \(p^{k}\) for some \(i\), no solution exists.

Note that multiple solutions \(\mathbf{x}\) may exist for \(k \geq 2\). If we need all the solutions, the next task is to construct an integer lattice formed by \(\mathbf{Ax}=\mathbf{0} \, (\mathrm{mod}\,p^{k})\). This problem can also be solved by a lattice algorithm shown in this lecture note.

The generalization from prime powers \(p^{k}\) to other composite numbers \(l\) is straightforward. After factoring \(l\) and solving the linear equations for each prime power, we can get a solution of \(\mathbf{Ax} = \mathbf{b} \, (\mathrm{mod}\, n)\) by the Chinese remainder theorem.