How can I find a linearly independent subset of a set of vectors in $\mathbb{Z}^n$?

Question

I have a set of $M$ vectors in the module $\mathbb{Z}^n$ ($M>n$) over $\mathbb{Z}$.

Question 1: How can I find a linearly independent subset of these vectors? (so that others can be written as a linear combination of this subset with integer coefficients)

Question 2: Let's assume that this linearly independent subset forms the basis for an $n$-dimensional lattice (or equivalently there are $n$ of them). Is there a way that without finding the subset, I can find the determinant of the matrix whose columns are these basis?

To clarify, let's say for example I have these $M=3$ vectors in $\mathbb{Z}^2$: $$ v_1 = (1,1) \\ v_2 = (2,0) \\ v_3 = (0,2) $$

What I want for the linearly independent subset is either the subset $\{v_1,v_3\}$ or $\{v_1,v_2\}$ but not $\{v_2,v_3\}$. Because for example in the first case I can write $v_2 = 2v_1-v_3$.

Answer 1

Problem 2: It's not quite as straightforward as for a field but you can still get a very concrete answer. A square matrix over a commutative ring with unit $R$ defines an injective map $R^n \rightarrow R^n$ if and only if its determinant is not a zero divisor; and it defines a surjective map $R^n \rightarrow R^n$ if and only if its determinant is invertible.

(In particular, surjective maps $R^n \rightarrow R^n$ are always injective. This isn't really trivial.)

A set of $n$ column vectors is a basis of $R^n$ is a basis if and only if the matrix they form is a bijective map. Over $\mathbb{Z},$ this means the matrix has determinant $\pm 1$, since these are the only integers whose multiplicative inverse is also an integer.

Problem 1) To find a linearly independent subset, just take the first vector that isn't zero. Maximal linearly independent subset is not really a good concept over $\mathbb{Z}$: for example, in $\mathbb{Z}^1$, the set $8 \mathbb{Z}$ should be considered smaller than $2 \mathbb{Z}$ although $\{8\}$ and $\{2\}$ are both sets of size $1$.

Answer 2

For question 1, write the extended matrix $$\begin{pmatrix} 1&2&0\\ 1&0&2\\ \end{pmatrix}$$ and then bring it to Hermite Normal Form (HNF). The answer will always be of the form $$\begin{pmatrix} c | 0 \end{pmatrix}$$ ie a square lattice c that gives the basis you are asking for, followed by zero columns. You might want to search for "Hermite Decomposition" algorithm if you are not sure how to perform the transformation. Since you are working in $\mathbb{Z}^n$ all the operations of the algorithm can be performed mod n.

For question 2 I am not familiar with any possible way of calculating the determinant without going through step 1 first. The determinant will not be $\pm1$ as written in another answer. Even for the example mentioned here, where $$c=\begin{pmatrix} 1&0\\ 1&2\\ \end{pmatrix}$$ the determinant is 2. Once $c$ is known calculating det$(c)$ is straightforward.