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$.
Best Answer
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.