Skip to main content
MathOverflow

Return to Answer

Improved formulation
Source Link
Kasper Dokter
Kasper Dokter
  • 41
  • 4

Although the brute force solution of Alex is certainly possible, it is not very efficient. It would be easier in practice to use Hermite's normal form:

First, find a linear map $A \in \mathbb{Z}^{(L-K) \times L}$, such that $V = \ker(A)$ is the null space of $A$ (which can be found by computing the null space of the matrix with $V$ as its rowspace).

Next, compute the Hermite normal form of $A$ to obtain a decomposition $H = AU$, where $H \in \mathbb{Z}^{(L-K) \times L}$ is in column-style Hermite normal form, and $U \in \mathbb{Z}^{L\times L}$ is a unimodular matrix (that is, $U : \mathbb{Z}^L \to \mathbb{Z}^L$ is an isomorphism).

For $\Lambda_H = \ker(H) \cap \mathbb{Z}^n$, we have \begin{align*} \Lambda &= \ker(A) \cap \mathbb{Z}^n \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid A\mathbf{x} = \mathbf{0} \} \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid HU^{-1}\mathbf{x} = \mathbf{0} \} \\ &= \{U\mathbf{y} \mid \mathbf{y} \in \mathbb{Z}^n, H\mathbf{y} = \mathbf{0} \} \\ &= U\Lambda_H \end{align*} As $H$ is in column-style Hermite normal form, it is straightforward to find a basis for the lattice $\Lambda_H$ (it is usually a subset of the standard basis). Application of the isomorphism $U$ yields a basis for the lattice $\Lambda$.

Although the brute force solution of Alex is certainly possible, it is not very efficient. It would be easier in practice to use Hermite's normal form:

First, find a linear map $A \in \mathbb{Z}^{(L-K) \times L}$, such that $V = \ker(A)$ is the null space of $A$ (which can be found by computing the null space of the matrix with $V$ as its rowspace).

Next, compute the Hermite normal form of $A$ to obtain a decomposition $H = AU$, where $H \in \mathbb{Z}^{(L-K) \times L}$ is in column-style Hermite normal form, and $U \in \mathbb{Z}^{L\times L}$ is a unimodular matrix (that is, $U : \mathbb{Z}^L \to \mathbb{Z}^L$ is an isomorphism).

For $\Lambda_H = \ker(H) \cap \mathbb{Z}^n$, we have \begin{align*} \Lambda &= \ker(A) \cap \mathbb{Z}^n \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid A\mathbf{x} = \mathbf{0} \} \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid HU^{-1}\mathbf{x} = \mathbf{0} \} \\ &= \{U\mathbf{y} \mid \mathbf{y} \in \mathbb{Z}^n, H\mathbf{y} = \mathbf{0} \} \\ &= U\Lambda_H \end{align*} As $H$ is in column-style Hermite normal form, it is straightforward to find a basis for the lattice $\Lambda_H$ (it is usually a subset of the standard basis). Application of the isomorphism $U$ yields a basis for the lattice $\Lambda$.

Although the brute force solution of Alex is certainly possible, it is not very efficient. It would be easier in practice to use Hermite's normal form:

First, find a linear map $A \in \mathbb{Z}^{(L-K) \times L}$, such that $V = \ker(A)$ is the null space of $A$ (which can be found by computing the null space of the matrix with $V$ as its rowspace).

Next, compute the Hermite normal form of $A$ to obtain a decomposition $H = AU$, where $H \in \mathbb{Z}^{(L-K) \times L}$ is in column-style Hermite normal form, and $U \in \mathbb{Z}^{L\times L}$ is a unimodular matrix (that is, $U : \mathbb{Z}^L \to \mathbb{Z}^L$ is an isomorphism).

For $\Lambda_H = \ker(H) \cap \mathbb{Z}^n$, we have \begin{align*} \Lambda &= \ker(A) \cap \mathbb{Z}^n \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid A\mathbf{x} = \mathbf{0} \} \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid HU^{-1}\mathbf{x} = \mathbf{0} \} \\ &= \{U\mathbf{y} \mid \mathbf{y} \in \mathbb{Z}^n, H\mathbf{y} = \mathbf{0} \} \\ &= U\Lambda_H \end{align*} As $H$ is in column-style Hermite normal form, it is straightforward to find a basis for the lattice $\Lambda_H$ (it is a subset of the standard basis). Application of the isomorphism $U$ yields a basis for the lattice $\Lambda$.

Source Link
Kasper Dokter
Kasper Dokter
  • 41
  • 4

Although the brute force solution of Alex is certainly possible, it is not very efficient. It would be easier in practice to use Hermite's normal form:

First, find a linear map $A \in \mathbb{Z}^{(L-K) \times L}$, such that $V = \ker(A)$ is the null space of $A$ (which can be found by computing the null space of the matrix with $V$ as its rowspace).

Next, compute the Hermite normal form of $A$ to obtain a decomposition $H = AU$, where $H \in \mathbb{Z}^{(L-K) \times L}$ is in column-style Hermite normal form, and $U \in \mathbb{Z}^{L\times L}$ is a unimodular matrix (that is, $U : \mathbb{Z}^L \to \mathbb{Z}^L$ is an isomorphism).

For $\Lambda_H = \ker(H) \cap \mathbb{Z}^n$, we have \begin{align*} \Lambda &= \ker(A) \cap \mathbb{Z}^n \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid A\mathbf{x} = \mathbf{0} \} \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid HU^{-1}\mathbf{x} = \mathbf{0} \} \\ &= \{U\mathbf{y} \mid \mathbf{y} \in \mathbb{Z}^n, H\mathbf{y} = \mathbf{0} \} \\ &= U\Lambda_H \end{align*} As $H$ is in column-style Hermite normal form, it is straightforward to find a basis for the lattice $\Lambda_H$ (it is usually a subset of the standard basis). Application of the isomorphism $U$ yields a basis for the lattice $\Lambda$.