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

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

• What is your underlying field of the vector space $\mathbb{Z}^n$ – user188634 May 25 '16 at 5:17
• I edited the question. But, isn't it implied that $\mathbb{Z}^n$ is over the field of integers? – Hamed May 25 '16 at 5:21
• @Hamed the integers don't form a field - you don't have multiplicative inverses. $\mathbb{Z}^n$ isn't a vector space under any standard definition. You'll need to talk about a generalization of vector spaces, called modules. – Mark May 25 '16 at 5:22
• @Mark Sorry, you are right. Does the question make sense if I say module $\mathbb{Z}^n$ over the ring of integers? – Hamed May 25 '16 at 5:25
• @Hamed - you'd usually phrase that as a module over $\mathbb{Z}$ – Siddharth Bhat May 25 '16 at 5:27

2 Answers

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.

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

• But the basis you wrote doesn't generate the same lattice as the basis that I find from my linearly independent set. – Hamed May 25 '16 at 5:42
• @Hamed Sorry I misread question $1$. – user342127 May 25 '16 at 5:43
• I edited question 2: this linearly independent set does not form a basis for $\mathbb{Z}^n$. But it is basis for an $n$-dimensional lattice. – Hamed May 25 '16 at 5:49
• @Hamed This is the same kind of problem. The lattice $\{v_2,v_3\}$ is contained in $\{v_1,v_3\}$ and yet it has the same rank, so it's not clear whether you can call it smaller. – user342127 May 25 '16 at 7:05
• What do you mean by smaller? – Hamed May 25 '16 at 7:15