ATAR Notes: Forum

Uni Stuff => Science => Faculties => Mathematics => Topic started by: QuantumJG on July 27, 2010, 08:22:58 pm

Title: Group Theory and Linear Algebra Thread
Post by: QuantumJG on July 27, 2010, 08:22:58 pm: Hey this is a thread for my Group Theory and Linear Algebra subject.

Anyway:

Prove that if $a,b \in \mathbb{Z} _{>0}$ s.t. $a|b$ & $b|a$ then $a = b$

How I did the proof:

$a|b \Rightarrow b = q_{1} a$ where $q_{1} \in \mathbb{Z}$

$b|a \Rightarrow a = q_{2} b$ where $q_{2} \in \mathbb{Z}$

$\therefore a = q_{2} \times q_{1} a$

$\therefore 1 = q_{1} q_{2}$

Now here is where I'm not sure if I can do this.

$\therefore q_{1} = q_{2} = 1 \because q_{1},q_{2} \in \mathbb{Z}$ & $q_{1} = \dfrac{1}{ q_{2} }$

$\therefore a = b$ //

With the next question I don't know how to show uniqueness.

Show that the remainder $r$ & quotient $q$ in Theorem 1.2.1 are unique.

Theorem 1.2.1:

If $a,d \in \mathbb{Z}$ and $d>0$ . There are unique integers $q$ , $r$ such that

$a = qd + r$ where $0 \le r < d$
Title: Re: Group Theory and Linear Algebra Thread
Post by: kamil9876 on July 27, 2010, 09:03:49 pm: yes, $q_1q_2=1$ is correct. This has two solutions: (1,1) and (-1,-1). You have to rule out the latter. e.g: if a=1, b=-1 then it is true that a|b and b|a in Z (showing the significance of the restriction to positive integers)

To get you started on the next one:

Suppose that qm+r=q'm+r'

therefore

m(q-q')=r'-r

Now you are ready to show that r'-r=0 as u want. (Hint: try to bound r'-r )
Title: Re: Group Theory and Linear Algebra Thread
Post by: TrueTears on July 27, 2010, 09:28:27 pm: Quote from: QuantumJG on July 27, 2010, 08:22:58 pm
Hey this is a thread for my Group Theory and Linear Algebra subject.

Anyway:

Prove that if $a,b \in \mathbb{Z} _{>0}$ s.t. $a|b$ & $b|a$ then $a = b$

How I did the proof:

$a|b \Rightarrow b = q_{1} a$ where $q_{1} \in \mathbb{Z}$

$b|a \Rightarrow a = q_{2} b$ where $q_{2} \in \mathbb{Z}$

$\therefore a = q_{2} \times q_{1} a$

$\therefore 1 = q_{1} q_{2}$

Now here is where I'm not sure if I can do this.

$\therefore q_{1} = q_{2} = 1 \because q_{1},q_{2} \in \mathbb{Z}$ & $q_{1} = \dfrac{1}{ q_{2} }$

$\therefore a = b$ //

With the next question I don't know how to show uniqueness.

Show that the remainder $r$ & quotient $q$ in Theorem 1.2.1 are unique.

Theorem 1.2.1:

If $a,d \in \mathbb{Z}$ and $d>0$ . There are unique integers $q$ , $r$ such that

$a = qd + r$ where $0 \le r < d$
Hi, there, you are correct for your first question.

The 2nd question is a classic, here is how I would attempt it:

The theorem (If a and b are integers with b> 0, then there is a unique pair of integers q and r such that a = qb + r and 0 <= r < b) has 2 parts.

One we must prove existence of a 'r' such that 0<=r<b

Second we must prove uniqueness.

Let us first prove existence.

First we prove existence. Let $S = \{a - nb | n \in Z\} = { a, a \pm b, a \pm 2b,\cdots\}$ . This set of integers contains non-negative elements (take $n = -la|$ ), so $S \cap \mathbb{N}$ is a non-empty subset of $\mathbb{N}$ ; by the well-ordering principle $S \cap \mathbb{N}$ has a least element, which has the form $r = a - qb \ge 0$ for some integer $q$ . Thus $a = qb + r$ with $r \ge 0$ . If $r \ge b$ then $S$ contains a non-negative element
$a - (q + l)b = r - b < r$ ; this contradicts the minimality of $r$ , so we must have $r < b$ .

Now to prove uniqueness

To prove uniqueness, suppose that $a = qb + r = q'b + r'$ with $0 \le r < b$ and $0 \le r' < b$ , so $r - r' = (q' - q)b$ . If $q' \neq q$ then $|q' - q| \ge 1$ , so $|r - r' | \ge |b| = b$ , which is impossible since $r$ and $r'$ lie between $0$ and $b-1$ inclusive. Hence $q' = q$ and so $r' = r$ .
Title: Re: Group Theory and Linear Algebra Thread
Post by: kamil9876 on July 28, 2010, 05:14:48 pm: notice also that this theorem extends to $\mathbb{R}$ ie: if we let $d,r,a$ be real but keep $q$ as an integer.
Title: Re: Group Theory and Linear Algebra Thread
Post by: QuantumJG on July 29, 2010, 06:25:35 pm: I saw my lecturer about this question today, but I forgot how he proved it.

Let [Tex] a,b,c \in \mathbb{Z} with gcd(a,b) = 1. Prove that if a|c and b|c then ab|c.
Title: Re: Group Theory and Linear Algebra Thread
Post by: /0 on July 29, 2010, 06:40:21 pm: Well if you write $a,b$ and $c$ as a products of factors, since $a$ and $b$ share no common factors, you can multiply them together and they must still divide $c$ .
Title: Re: Group Theory and Linear Algebra Thread
Post by: TrueTears on July 29, 2010, 10:04:01 pm: Quote from: QuantumJG on July 29, 2010, 06:25:35 pm
I saw my lecturer about this question today, but I forgot how he proved it.

Let $a,b,c \in \mathbb{Z}$ with $gcd(a,b) = 1$ . Prove that if a|c and b|c then ab|c.
We have ax + by = 1, c = ae and c = bf for some integers x, y, e and f. Then c = cax + cby = (bf)ax + (ae)by = ab(fx + ey), so ab|c.
Title: Re: Group Theory and Linear Algebra Thread
Post by: QuantumJG on July 29, 2010, 11:09:06 pm: Quote from: TrueTears on July 29, 2010, 10:04:01 pm
Quote from: QuantumJG on July 29, 2010, 06:25:35 pm
I saw my lecturer about this question today, but I forgot how he proved it.

Let $a,b,c \in \mathbb{Z}$ with $gcd(a,b) = 1$ . Prove that if a|c and b|c then ab|c.
We have ax + by = 1, c = ae and c = bf for some integers x, y, e and f. Then c = cax + cby = (bf)ax + (ae)by = ab(fx + ey), so ab|c.

Yeah that's how he proved it. Thanks!
Title: Re: Group Theory and Linear Algebra Thread
Post by: QuantumJG on August 21, 2010, 05:19:00 pm: I'm having trouble with this:

Show that if $n \in \mathbb{Z}$ with $n \equiv 7$ (mod 8), then the equation

$n = x^{2} + y^{2} + z^{2}$

has no solutions if $x,y,z \in \mathbb{Z}$

WTF!
Title: Re: Group Theory and Linear Algebra Thread
Post by: brightsky on August 21, 2010, 05:54:41 pm: Actually forget mod 4, do it in mod 8.

We know that given a whole number $a^2$ is odd, then we have $a \equiv 1 \mod 8$ .

Likewise (tweaked from mod 4 case), if $a^2$ is even, then we have two cases:

1. $a \equiv 0 \mod 8$ or

2. $a \equiv 4 \mod 8$

From here, by brute force, we can work out that the possibilities for $x^2 + y^2 + z^2$ can be any number other than 7.
Title: Re: Group Theory and Linear Algebra Thread
Post by: kamil9876 on August 21, 2010, 06:20:48 pm: mod 8:

$x$ :0 1 2 3 4 5 6 7

$x^2$ :0 1 4 1 0 1 4 1

(notice how it is symmetrical since $x^2=(8-x)^2$ , saves you half the time)

so amongst $x^2, y^2, z^2$ you cannot have no 4 or just a single 4 since otherwise the sum would be too small. So you need at least two 4's. But two 4's is 0 so that also makes your sum too small.
Title: Re: Group Theory and Linear Algebra Thread
Post by: pooshwaltzer on August 21, 2010, 06:30:49 pm: Please suggest a possible financial application for said theory. Thanks.
Title: Re: Group Theory and Linear Algebra Thread
Post by: QuantumJG on August 22, 2010, 09:30:23 am: Quote from: kamil9876 on August 21, 2010, 06:20:48 pm
mod 8:

$x$ :0 1 2 3 4 5 6 7

$x^2$ :0 1 4 1 0 1 4 1

(notice how it is symmetrical since $x^2=(8-x)^2$ , saves you half the time)

so amongst $x^2, y^2, z^2$ you cannot have no 4 or just a single 4 since otherwise the sum would be too small. So you need at least two 4's. But two 4's is 0 so that also makes your sum too small.

Thanks Kamil. There was a question earlier where we had to do a multiplication table for 8 and I noticed that symmetry.
Title: Re: Group Theory and Linear Algebra Thread
Post by: QuantumJG on November 21, 2010, 12:22:30 pm: This is a problem from last years exam.

Let V = $P _{2} (\mathbb{R})$ and T: V $\rightarrow$ V be the linear transformation defined as:

T(p(x)) = p(x+1) + 3p'(x)

a) Find the matrix T with respect to the basis { $1,x,x^{2}$ } for V.

So I got:

p(1) = {1,0,0}
p(x) = {2,1,0}
p(x²) = {1,4,1}

So I got T to be:

$ \[ \left( \begin{array}{ccc} 1 & 2 & 1 \\ 0 & 1 & 4 \\ 0 & 0 & 1 \end{array} \right)\] $

I just want to make sure this is right!
Title: Re: Group Theory and Linear Algebra Thread
Post by: kamil9876 on November 21, 2010, 06:25:40 pm: you want to be finding $T(1), T(x), T(x^2)$ . I have no idea what you mean by $p(1)$ etc., typo?
Title: Re: Group Theory and Linear Algebra Thread
Post by: dcc on November 23, 2010, 05:07:59 pm: exam complete. my thoughts:

(http://imgur.com/MF74E.png)
Title: Re: Group Theory and Linear Algebra Thread
Post by: QuantumJG on November 23, 2010, 05:31:30 pm: The exam was alright, although it was harder than last years.

Who are you? Whereabouts in the lecture theatre did you sit?
Title: Re: Group Theory and Linear Algebra Thread
Post by: dcc on November 23, 2010, 09:33:17 pm: Up the back, like a boss.
Title: Re: Group Theory and Linear Algebra Thread
Post by: QuantumJG on November 25, 2010, 05:14:37 pm: Do you know Tom Dutka, Michael Malek and Angus McAndrew? I hang out with Angus and Michael and see Tom every so often and I know they sit up the back. I sit in the front.