Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You need to show that given any $(e,f) \in \mathbb{Z}^2$, you can write $(e,f)=g(a,b)+h(c,d)$. The Chinese Remainder Theorem says you can do it in one coordinate, can you do it in both coordinates at once? –  Ross Millikan Mar 17 '11 at 15:49
2  
Take $x=(2,4)$, $y=(3,9)$. Then $ad=18\neq 12=bc$, $\gcd(a,c)=1$, $\gcd(b,d)=1$. Can you get $(0,1)$ using $x$ and $y$? If $\alpha x + \beta y = (0,1)$, then $2\alpha+3\beta = 0$, and $4\alpha+9\beta=1$. But if $4\alpha = -6\beta$, then $3\beta = 1$, so $\beta=\frac{1}{3}$. Oops. Your conditions are necessary, but not sufficient. –  Arturo Magidin Mar 17 '11 at 15:52
    
@Ross: I appreciate you listing what needs to be shown. Sometimes that isn't clear to me. I believe your claim about the CRT, but we haven't explicitly referred to (or learned) that. –  The Chaz 2.0 Mar 17 '11 at 15:58
1  
you need the determinant $ad-bc$ to be $\pm1$ –  yoyo Mar 17 '11 at 16:14
1  
"Bombs away"!.. –  The Chaz 2.0 Mar 17 '11 at 19:44
show 3 more comments

3 Answers

up vote 14 down vote accepted

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.

share|improve this answer
1  
Is the neat expression $det\begin{bmatrix} a &b \\ c &d \end{bmatrix} \neq 0$??<br> This is where I derived $ad \neq bc$ –  The Chaz 2.0 Mar 17 '11 at 15:56
1  
@The Chaz: Two hints: (1) What happens if the transform is area preserving? (2) In the formula for an inverse where does $\det$ come up, and what should we want it to be when working in the integers? In short, what if the determinant was equal to 1? –  Eric Naslund Mar 17 '11 at 16:00
3  
@TheChaz: note: invertible in $\mathbb Z$. Which integers are invertible? –  lhf Mar 17 '11 at 16:01
    
@Eric: I don't know what (1) is... linear algebra was a LONG time ago for me! (2) Oooooooooooh! Nice. So it must be a unit!! –  The Chaz 2.0 Mar 17 '11 at 16:07
    
@Ihf: Ok, now I'm making some headway. The determinant must be 1 or -1? Let me work on justifying this and I'll be back. Thanks. –  The Chaz 2.0 Mar 17 '11 at 16:08
show 2 more comments

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\: =\: $ #interior_points $\ +\ 1/2\ $ #boundary_points $\:-\ 1\ =\ 0 + 4/2 - 1 = 1\:.\ $ But by basic analytic geometry $\rm\: area\ P\: =\: |det(x,y)|\:.\: $ Therefore $\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.

share|improve this answer
    
A very nice argument. –  Ross Millikan Mar 17 '11 at 17:55
    
Shouldn't that be $\mathrm{area}(P) = |\det(x,y)|$? The determinant counts orientation, the area does not. –  Arturo Magidin Mar 17 '11 at 18:22
1  
Yes, of course. So much for my automagic Emacs TeX macros. –  Bill Dubuque Mar 17 '11 at 19:24
    
I'm glad this is the case, since it "gels" with my conclusion that +/-1 are the determinants. –  The Chaz 2.0 Mar 17 '11 at 19:33
2  
@Adrián: I learned about these ideas after being inspired by either Rota or Stanley's discussion of higher-dimensional analogues of Pick's theorem, e.g. see Erhart polynomials. For some references see my sci.math post on 1998.6.3. If memory serves correct Arcavi and Bruckheimer discuss the history in the Intelligencer paper cited there, or another joint paper. –  Bill Dubuque Mar 26 '11 at 16:53
show 3 more comments

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

share|improve this answer
    
$ad-bc=1 \implies gcd(a,c)=gcd(b,d)=1$, but is not equivalent. Arturo Magidin's example of (2,4) and (3,9) has $gcd(a,c)=gcd(b,d)=1$, but $ad-bc=6$ –  Ross Millikan Mar 17 '11 at 19:56
    
Is it acceptable otherwise? –  The Chaz 2.0 Mar 17 '11 at 19:59
    
It is a correct statement of the required condition, but you have not proven that it is correct. As lhf said, if you can show that you can express (1,0) and (0,1) you can appeal to linearity to show you can express all of $\mathbb{Z}^2$. So I would explicitly find $e$ and $f$ such that $(1,0)=e(a,b)+f(c,d)$, show that your condition makes sure they are integers, then do the same for $(0,1)$ –  Ross Millikan Mar 17 '11 at 20:10
    
@Ross: Will do. from ad - bc = 1, can I let e = d and f = -b? And likewise for... say, g and h? –  The Chaz 2.0 Mar 17 '11 at 20:32
    
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. –  Ross Millikan Mar 17 '11 at 21:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.