What happens when the basis vectors of an integer lattice are not linearly independent?

The definition of a lattice requires basis vectors that are linearly independent.

Why?

For example, the following three vectors are linearly independent and form the basis of a lattice:

$$\begin{array}{ccc} 0 & 0 & 1 \\ 0 & 2 & -2 \\ 1 & -2 & 1 \end{array}$$

But what if we add a fourth vector such that they're not linearly independent anymore. For example:

$$\begin{array}{ccc} 0 & 0 & 1 & 4\\ 0 & 2 & -2 & 2\\ 1 & -2 & 1 & 3\end{array}$$

Are the four vectors the basis of a lattice? Why or why not? And, if it is, why does the definition require linear independence? Is there an equivalent basis that is linearly independent?

• Taking the last question, the first three vectors form a basis of that lattice, and they are linearly independent. – Gerry Myerson Jan 31 '13 at 10:31
• Yes but it's not the same lattice I don't think. Since the lattice whose basis is the first three only contains integer combinations of these 3. Even though they're not linearly independent when we add the fourth, this doesn't mean(I don't think) that there are integer coefficients that produce the fourth. Is there an integer combination of the first three that get you the fourth vector?Thanks! – user60389 Jan 31 '13 at 10:35
• $(4,2,3)=4(1,-2,1)+5(0,2,-2)+9(0,0,1)$. – Gerry Myerson Jan 31 '13 at 10:47
• By the way, if you want to be sure I see a reply to something I have written, you have to write @Gerry. – Gerry Myerson Jan 31 '13 at 10:48
• @GerryMyerson Good point--Okay So I gave a bad example. But say the fourth vector was (1,1,1). Now there's no way to get this point from integer combinations of the first three. So adding this fourth vector would add points to the lattice(if this indeed is a lattice) and the lattice given by the first three vectors is not the same as when we add the fourth vector. – user60389 Jan 31 '13 at 11:19

Maybe your definition of a lattice is stated as such in order to keep terms as reduced as possible. Your original lattice obviously does not include every integer vector, but the addition of $\pmatrix{1 & 1 & 1}^\top$ does indeed "fill out" all the integer points of the lattice, as the following attempts to show.

Let us column reduce using only integer operations ($C_4 \leftarrow C_4 - C_3$ means column $4$ gets $1$ of column $3$ subtracted): $$\pmatrix{0 & 0 & 1 & 1 \\0 & 2 & -2 & 1 \\1 & -2 & 1 & 1\\ } \overset{C_4 \leftarrow C_4 - C_3}{\longrightarrow} \pmatrix{0 & 0 & 1 & 0 \\0 & 2 & -2 & 3 \\1 & -2 & 1 & 0\\ }$$

$$\pmatrix{0 & 0 & 1 & 0 \\0 & 2 & -2 & 3 \\1 & -2 & 1 & 0\\ } \overset{C_4 \leftarrow C_4 - C_2}{\longrightarrow} \pmatrix{0 & 0 & 1 & 0 \\0 & 2 & -2 & 1 \\1 & -2 & 1 & 2\\ }$$

Now it is apparent that if the third, fourth, and first columns are chosen as the basis that the new lattice has a determinant of one, thus any integer vector is within the span. You can see this from the lower triangular form here, as it has all ones along the diagonal: $$\pmatrix{1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 2 & 1 }$$

Any integer matrix with a determinant of $\pm1$ has an integer inverse. That means all integer vectors are within its span, using only integer combinations of its columns. Thus your new lattice with the additional vector is the lattice of all integer vectors.

Since the definition of a lattice uses all integer combinations of the basis vectors, your new lattice as defined by four columns of three elements is valid, but it is not the most reduced basis to use. It would be an obfuscated form, as the identity itself is also a valid basis to use in this example. The identity would be the best basis to use here, unless of course you want to obfuscate the form for some reason.

• Wow thank you for a great answer. As a follow-up question: Say we dropped the requirement for it to be an integer lattice. Then can adding a fourth column actually make it not a lattice--say by adding a vector of irrationals? – user60389 Feb 1 '13 at 3:39
• So if not an integer lattice, it would be a rational lattice? Any rational combination of the basis vectors? You could have irrationals as the basis for an integer lattice, it would still have only the integer multiples of the basis as lattice points. – adam W Feb 1 '13 at 3:47
• I guess what I'm trying to figure out is are there any four vectors (whose componenents are reals) such that they do not form the basis of a lattice? – user60389 Feb 1 '13 at 3:54
• It depends on what constitutes being or not being a lattice. You mention linear dependency, four vectors in $3$ dimensional space are necessarily dependent by the general definition of dependency, but if integer combinations only are allowed, then they could still be independent. By definition of lattice (unless the definition itself restricts the basis vectors to be only integer) any number of vectors could be a basis. As I understand the definition of a lattice, any set of (not necessarily unique) vectors as basis, any vector written as an integer combination of that set is in the lattice. – adam W Feb 1 '13 at 4:11

The definition of a lattice is that it is a discrete additive subgroup of $\mathbb{R}^n$. The requirement that it be discrete gives us the answer to your question!

The "discrete" bit means that there is some $\epsilon > 0$ such that for any two distinct lattice points $x, y \in \Lambda$, $||x-y|| > \epsilon$.

In English: there has to be some minimum distance by at least which all lattice points are separated.

What would happen if we tried to define a lattice with the following basis:

$\begin{pmatrix} 1 & 0 & \sqrt{2}\\ 0 & 1 & \sqrt{2} \end{pmatrix}$

There's no way we're ever going to get $C_3$ from integer multiples of $C_1$ and $C_2$, so why isn't this a valid lattice basis?

Note that $\begin{pmatrix}1 \\ 1\end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 1\end{pmatrix}$ will be in $\Lambda$, as will $\begin{pmatrix} 0.4142135...\\ 0.4142135...\end{pmatrix} = \begin{pmatrix} \sqrt{2} \\ \sqrt{2} \end{pmatrix} - \begin{pmatrix} 1 \\ 1\end{pmatrix}$

as will $\begin{pmatrix}0.5857864... \\ 0.5857864... \end{pmatrix}= \begin{pmatrix} 1 \\ 1\end{pmatrix} - \begin{pmatrix} 0.4142135...\\ 0.4142135...\end{pmatrix}$ and so on and so forth.

So if I came to you claiming that our set of 3 vectors forms a basis for a 2-D lattice, I would have to offer up some minimum distance between lattice points, $\epsilon$, per the definition of a lattice. However, you would always be able to find two lattice points $x, y \in \Lambda$ such that $|| x - y || < \epsilon$ for any value of $\epsilon$ that I proposed, proving that I was a liar and our set of vectors doesn't form a lattice basis after all.

• Technically, the discrete in the definition means "such that the subset topology induced on it is discrete", which a priori does not mean $\inf_{x,y\in\Lambda} \lVert x-y\rVert\ge \varepsilon$. It does in this cases, thanks to the algebraic structure of $\Bbb Z$-module with which $\Lambda$ is endowed. – user228113 May 30 '16 at 0:04
• You should make a distinction between fullrank lattices and discrete subgroups – reuns Jun 6 at 18:23