16
$\begingroup$

Let $x = (a, b), y = (c, d) \in \mathbb{Z}^2$. What is the condition on $a, b, c, d$ so that ${x, y}$ is a basis?

My answer: $ad\neq bc$ and $gcd(a, c) = gcd(b, d) = 1$.
The first condition ensures that they aren't the same vector; the second ensures that we can actually "get" all of the integer values/lattice points.
Is this correct?

Thanks.

  • 1
    "Bombs away"!..2011-03-17

3 Answers 3

1

For $ (a, b) $ and $ (c, d) $ to be a basis, they must be linearly independent. In other words,
$\det \begin{bmatrix} a &b \\ c& d \end{bmatrix} $ must be invertible. Over a field, this would imply that $\det(A) \neq 0 $, but since we are in $\mathbb{Z}$, we require $\det(A) = \pm 1$ so that each entry in $A^{-1} = \frac{1}{\det(A)} \begin{bmatrix} d &-b \\ -c& a \end{bmatrix}$ is an integer.

Note that $ad - bc = 1$ implies that $\gcd(a,c) = \gcd(b,d) = 1$.

  • 0
    Yes. You can just say "If we let $e=d, f=-b, e(a,b)+f(c,d)=$ (scribble) $=(1,0)$. How much you put into (scribble) depends upon the level of the audience.2011-03-17
21

This has a beautiful geometrical interpretation. Note $\rm\, x,y\, $ is a $\rm\,\mathbb Z$-basis of $\rm\, \mathbb Z^2\, $ iff $\rm\, \mathbb Z^2\, $ is tiled by the fundamental parallelogram $\rm P $ with sides $\rm\,x,y.\, $ But this is true iff the only lattice points that are inside $\rm P $ or on the boundary of $\rm\,P\,$ are its vertices. However, by Pick's area formula, this is true iff

$$\rm\ area\ P =\text{ #interior_points } + \frac{1}2\text{ #boundary_points}- 1\, =\, 0 + \frac{4}2 - 1\, =\, 1\qquad$$

But by basic analytic geometry $\rm\, area\ P\, =\, |\det(x,y)|.\,$ Therefore, combining the two, we conclude that $\rm\, x,y\,$ is a $\rm\,\mathbb Z$-basis of $\rm\, \mathbb Z^2\! \iff |\det(x,y)| = 1.$

In fact it deserves to be much better known that Pick originally applied his area formula in a similar way to give a beautiful geometric proof of the Bezout linear representation of the gcd.

  • 0
    @Bill By the _geometric proof of the Bezout linear representation of the gcd_ you mean the proof which is given (for example) at the end of the paper Maxim Bruckheimer and Abraham Arcavi: [A Visual Approach to Some Elementary Number Theory](http://www.jstor.org/stable/3618072)? Do you have some other interesting references for this proof? (I have access to the above article, but AFAIK it's not freely available.)2011-09-17
16

If that is a basis, then you can write $e_1=(1,0)$ and $e_2=(0,1)$ in terms of the basis using integer coefficients. This implies that the matrix determined by the basis in invertible in $\mathbb Z$. That is your condition. It can be expressed neatly using determinants.

  • 0
    @Eric: After reading about [the determinant](http://math.stackexchange.com/q/668/7850) here on MSE and elsewhere, I realize what you were saying with (1)... finally! "Transform area preserving" means that the determinant is $\pm 1$. Though I still don't get the "signed area of the transformation" part 100% :)2012-04-13