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

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Ross Millikan
    Mar 17, 2011 at 15:49
  • 4
    $\begingroup$ 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. $\endgroup$
    – Arturo Magidin
    Mar 17, 2011 at 15:52
  • $\begingroup$ @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. $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 15:58
  • 1
    $\begingroup$ you need the determinant $ad-bc$ to be $\pm1$ $\endgroup$
    – yoyo
    Mar 17, 2011 at 16:14
  • 1
    $\begingroup$ "Bombs away"!.. $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 19:44

3 Answers 3

Reset to default
21
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ A very nice argument. $\endgroup$
    – Ross Millikan
    Mar 17, 2011 at 17:55
  • 1
    $\begingroup$ Shouldn't that be $\mathrm{area}(P) = |\det(x,y)|$? The determinant counts orientation, the area does not. $\endgroup$
    – Arturo Magidin
    Mar 17, 2011 at 18:22
  • 2
    $\begingroup$ Yes, of course. So much for my automagic Emacs TeX macros. $\endgroup$
    – Bill Dubuque
    Mar 17, 2011 at 19:24
  • $\begingroup$ I'm glad this is the case, since it "gels" with my conclusion that +/-1 are the determinants. $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 19:33
  • 3
    $\begingroup$ @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. $\endgroup$
    – Bill Dubuque
    Mar 26, 2011 at 16:53
16
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Is the neat expression $det\begin{bmatrix} a &b \\ c &d \end{bmatrix} \neq 0$??<br> This is where I derived $ad \neq bc$ $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 15:56
  • 1
    $\begingroup$ @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? $\endgroup$
    – Eric Naslund
    Mar 17, 2011 at 16:00
  • 3
    $\begingroup$ @TheChaz: note: invertible in $\mathbb Z$. Which integers are invertible? $\endgroup$
    – lhf
    Mar 17, 2011 at 16:01
  • $\begingroup$ @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!! $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 16:07
  • $\begingroup$ @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. $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 16:08
2
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ $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$ $\endgroup$
    – Ross Millikan
    Mar 17, 2011 at 19:56
  • $\begingroup$ Is it acceptable otherwise? $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 19:59
  • 1
    $\begingroup$ 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)$ $\endgroup$
    – Ross Millikan
    Mar 17, 2011 at 20:10
  • $\begingroup$ @Ross: Will do. from ad - bc = 1, can I let e = d and f = -b? And likewise for... say, g and h? $\endgroup$
    – The Chaz 2.0
    Mar 17, 2011 at 20:32
  • $\begingroup$ 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. $\endgroup$
    – Ross Millikan
    Mar 17, 2011 at 21:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .