What is a mathematical group? (Part 2)

In my previous post, I gave the definition of a group. In this post, I will identify some examples of groups. My objective for this post is to show that many different objects (not just numbers) fit the bill for a group, and so it may be easier to prove things for a group abstractly (that is, without any particular group in mind) using just the properties of the definition of a group.

Example 1: As in the previous post, the integers form a group under addition.
Proof: A general property of addition of integers is that the sum of two gives another. The operation can also be taken for granted to be associative. Previously, I identified 0 as the identity element, and the negative of an element to be its inverse.

(Non) Example: The integers under multiplication do not form a group.
Proof: The operation of multiplication is indeed a binary operation, and it is associative. The identity element is 1 because for every . However, no element other than 1 itself has an inverse. Indeed, when multiplication is the operation, the inverse of is , but the only for which this is an integer is . Furthermore, 0 does not even have an inverse in any set of numbers since . Hence is not a group.

Example 2: To fix the previous problem, consider the set , that is, the set of all rational numbers (fractions) minus the number 0, with the operation of multiplication. I will leave it to the reader to verify that this does indeed form a group.

Example 3: Consider the set of all non-singular (that is, invertible) matrices, together with matrix multiplication. The reader familiar with matrix algebra will be able to easily show that these form a group.

Example 4: One can also form groups out of objects that aren’t necessarily numbers. For example, consider the symmetries of an equilateral triangle, as shown below in the picture.

The picture on the left involves flipping the triangle around the axis indicated. The picture on the right involves rotating the triangle, by either 120°, 240°, or 360°. Any of these operations will return an equilateral triangle in the same orientation as the original.

Call rotation by 120° the element , rotation by 240° . Clearly, rotation by 360° leaves the triangle unchanged, so let’s call that , the identity operation. Call the flip furthest left , the middle flip , and the right flip . By labeling the vertices, we can then combine the operations to get a new orientation. For example, a rotation by 120° followed by a rotation by 240° gives a total rotation by 360°. That is, . Notice that the operations in this notation are applied right to left – that is, first we applied followed by . The set with these operations has the “multiplication table” shown below:

The table is read by taking the row times the column. So for the row marked and the column marked , the result is . That is, rotating first by 120° and then flipping along the centerline of the result is the same as flipping the triangle about the line.

One can check using this table that these operations form a group. Clearly, rotations and flips give another rotation or flip, so the operation is indeed a binary operation. The indentity is rotation by 360°, and each element does indeed have an inverse (for example, since ; this can be checked for each and every element). And the operations are associative, though to show this is left as an exercise to the reader.

One beautiful thing about groups is that a very broad spectrum of objects can be shown to exhibit the properties of a group. It is much more attractive, then, to show things about a group abstractly than it is to show it for a certain set of objects.

For example, notice that in each of the groups in the above examples only had one identity element. This is actually true of any structure that is a group. Hence, the following theorem.

Theorem: In a group, the identity element is unique.
Proof: Suppose that there are two identity elements, and . Then by applying properties of the identity element, we have

Because there was no reference to integers with addition, rationals with multiplication, invertible matrices, or symmetries of a triangle, I have simultaneously proven that the identity element of each of these structures is unique! Indeed, I have shown it for the countless numbers of groups that one can construct. That is the power of working abstractly!

Next time I’ll start proving a few other useful properties of groups.

(Part 1)(Part 3)

What is a mathematical group? (Part 1)

Last semester, a friend of mine (who has now graduated with his B.S. in physics) asked me the question, “What exactly is a group?”

I was able to answer his question because I had already taken a course in elementary group theory. But I had also taken a course in particle physics, in which the Standard Model relies on groups, and I had not heard anything about defining a group in this class. For the uninformed student, it seemed like the lecturer was doing weird magic with groups and “adding” them together.

I will be writing this short introduction with the physics student in mind. Especially if the student is interested in any type of particle physics, this may be an interesting read.

To begin on the odyssey that is in store for a student of abstract algebra, it pays to know a bit of terminology.

Definition: A binary operation (sometimes law of composition) on a set is a function . That is, this function takes two elements of the set and produces another in . A more familiar way of looking at this for a physicist that has taken a course in linear algebra is that the set is closed under this operation, just as in a vector space – the sum of two vectors in a vector space is another vector in that same set.

For example, addition (and subtraction as well) is a binary operation on the set of all integers , for if one adds (or subtracts) two integers, the result is another integer.

Typically, this binary operation is not written in the usual fashion of writing a function of multiple variables , but rather . Normally, unless it leads to confusion, the is dropped in favor of just writing as in normal multiplication.

Definition: The binary operation is associative if for every in the set on which the operation is defined, . That is, the order of applying the binary operation has no effect on the outcome.

For example, if we examine the example of integers with addition as the binary operation, this binary operation is associative. However, if one takes the operation as subtraction, this is not associative (take, for example, 1 – (2 – 3) = 1 – (-1) = 2, but (1 – 2) – 3 = -1 – 3 = -4).

Definition: An identity element of a set with a binary operation is an element where for any .

Note: Mathematicians like to use shorthand (hence all of the symbols used for different operations). The symbol is read “is an element of”. So the previous line is read “…for any that is an element of .”

Going back to the example of integers with addition, 0 acts as the identity here, because for every .

Definition: Given an element in a set with a binary operation and identity element , the inverse of (usually denoted by where appropriate) is one such that .

One last reference to the integers under addition shows that the inverse of an integer is since .

The punchline from all of this is the definition of a group:

Definition: A group is a set together with a binary operation that has the property of associativity, an identity element, and inverses for each element in the set.

Next time, I’ll give some examples of groups and start proving some elementary theorems about them.

(Part 2)(Part 3)

Physics of GPS relativistic time delay

So I realized today I’ve been posting quite a bit about GNU/Linux and mathematics, but I haven’t really done much with physics. So here’s my first physics post!

This problem is actually one assigned in the undergraduate general relativity course I took in the spring 2008. It’s from James B. Hartle’s book Gravity: An Introduction to Einstein’s General Relativity, chapter 6, problem 9.

A GPS satellite emits signals at a constant rate as measured by an onboard clock. Calculate the fractional difference in the rate at which these are received by an identical clock on the surface of Earth. Take both the effects of special relativity and gravitation into account to leading order in . For simplicity, assume the satellite is in a circular equatorial orbit, the ground-based clock is on the equator, and that the angle between the propagation of the signal and the velocity of the satellite is 90° in the instantaneous rest frame of the receiver.

The problem is very simplified as to make the calculations doable at the undergraduate level. Thus it is using the simplified Geometric Newtonian gravity, that is, the line element given by

One could, of course, use Schwarzchild coordinates (and this is, in effect, what I did for the general relativistic part). The solution is broken into three parts: orbital information, the special relativistic effects, and the general relativistic effects.

Orbital Information

The key here (that’s not given in the problem) is that the time that it takes satellites to orbit Earth is 12 hours. Recalling that the speed of an orbit in Newtonian gravity is , where is the radius of the orbit and is the mass of the object being orbited, we get that

Plugging in the appropriate values gives =26,605 km and =3871.0 m/s.

Special Relativistic Effects

Let denote the ground observer and denote the satellite. Then we can use time dilation to get that

General Relativistic Effects

For general relativistic effects, note that the frequencies are related by

The derivation of this formula is beyond the scope of chapter 6 and uses Killing Vectors and photon geodesics introduced in a later chapter. However, an approximation to this result is given in equation 6.12 of Hartle. Plugging in the appropriate results gives the ratio to be 1+5.2873 x 10^-10, very nearly 1.

Putting things together, the whole shift is

As a check, suppose that a day passes on Earth (in other words, = 24 hours = 86,400 s). Then for the satellite, (86,400 s)(4.4573 x 10^-10) = 38.511 μs more have passed every day. According to Wikipedia, this number is 38 μs.

Also according to Wikipedia, the desired frequency on Earth is =10.23 MHz. This leaves to be 0.0045598 Hz less (compare this to Wikipedia’s claim of 0.0045700 Hz less).

The problem of course is not as simple as it was made to be. Difficulties arise when one takes into account that Earth is rotating (so the metric is more complicated), that the observer is not necessarily orbiting in the same plane as the satellite, and the orbit is not perfectly circular. However, these corrections are minute and don’t affect the problem very much.

Hope this was an interesting read!

MAC Address Spoofing

I had always thought that spoofing a MAC address was difficult. After all, one security precaution to wireless routers is to only let certain MAC addresses into the router.

Today I wanted to spoof a MAC address, though not for illegal purposes such as hacking into a wireless network. The university that I’m working at for the summer requires that you activate ports in the research labs by sending a request to the department’s ITS people containing the MAC address of the computer you’re trying to hook up and waiting a few days. Unfortunately I didn’t have a few days because the hard drive on the computer that we used had crapped out. It’s an old computer (pre-2000) so booting a live cd of Ubuntu was out of the question. I had my laptop and needed to connect to the internet but I couldn’t connect using the dead computer’s ethernet port since my MAC didn’t match. On top of that, we were in the sub-basement of the building, so there were no Wifi points around.

Reading through the man pages for ifconfig, I found out it’s extremely simple to spoof a MAC, at least in Linux. All commands need to be run as root, so either su to root or prefix each command with sudo.

First, disable your device (mine was eth0) by using

ifconfig eth0 down

Then, enter the line

ifconfig eth0 hw ether 00:01:02:03:04:05

and of course substitute in the MAC address that you desire. Then, just do

ifconfig eth0 up
dhclient eth0

and you’re done! You’ll now connect with your new MAC. Don’t worry, your MAC will reset on the next boot.

So anyway, I was online and looked up external hard drive enclosures to see if it would be reasonable to try one out just to make sure it wasn’t the motherboard or cables that was fried. After looking, I decided to take off the computer’s cover and poke around a bit, but didn’t actually change anything other than unplugging and replugging a few cables. Next boot it found the drive! Strange, but at least I was able to make a last backup of the data on the hard drive before we replace the computer within the next few days.

Auto Gordian-Knot v2.40 in Wine 0.9.59

I’ve had some trouble in the past getting AutoGK running in Wine on Kubuntu, but it had been a while since I tried so I decided to give it a go again to see how much Wine has progressed.

The Wine HQ profile for AutoGK claims that version 2.40 runs fine on Wine 0.9.53, so I went ahead downloaded it from AfterDawn after some searching. It installed just fine, and I downloaded the DLL files suggested by this site (it’s in German but is basic enough to be able to make out). Even after doing this I was having problems – as soon as I started it, I got the errors below:

followed by,

After these errors it would start, but every time I tried to open an IFO file, it told me that it was unable to parse, and if I opened a VOB directly, it said it was an invalid stream.

Just by chance, I cd’d to the Wine directory where wine installed it to check out the files in the directory. After poking about for a bit, I tried one last time…and it started just fine!

Not sure what I did, I went ahead and added it to my dock (using a hi-res icon found here). I went about encoding a DVD file that I had ripped using DVDFab (which works beautifully right away in Wine!) and watched it afterwards in Kaffeine. Satisfied, I decided to encode some more.

But starting the launcher from my dock, I got the same errors as before. Confused, I tried poking around my winecfg settings and got nothing. I decided to run the program in the same setting as before, so I cd’d again to the install directory and ran it from there. It worked again! It seems that, for whatever reason, running AutoGK in Wine requires that you be in the install directory.

I wrote a very simple bash script to put on my dock icon.

#!/bin/bash
cd ~/.wine/drive_c/Program\ Files/AutoGK
wine "C:\Program Files\AutoGK\AutoGK.exe"

Save this to any directory you’d like and chmod it to 755 so that it is executable. Then run it any time you want!

If this was helpful, please drop me a line through e-mail or a comment.

UPDATE: To install AutoGK, you have to use a virtual desktop in your winecfg settings. Once you’re done installing you can remove the virtual desktop.

Circumference of a Circle

So I was thinking about my previous area problem and the thought occurred to me that the same method could also be used to derive the circumference of the circle.

Using the same setup as before, the perimeter of the polygon is just . So again if we let we should get the circumference of a circle.

Recall that I found the formula for in terms of the number of sides and the radius: it was

The circumference of a circle is then

which is again exactly as expected.

And now with that out of the way, I can get some sleep. Good night!

LaTeX Tests

So I just imported my (few) files from Blogger.com because I was unhappy with how it handled math equations. I did some research and found out that WordPress handles them natively with , so I was quick to switch since I’ll probably be using mathematics quite a bit.

For example, did you know that if, for a function of one variable,

implies that is actually a constant function?

The geodesic equation that test particles follow in a given metric is

,

where the Christoffel symbols are given by

There are a few things missing such as equation arrays, but I’ve been able to figure out how to emulate such things using arrays. For example, in a commutative ring with elements and ,

Overall, some things are a bit annoying, but it’s definitely workable!

Codecogs images render mathematics

So I was a little upset at how poorly Blogger.com handled math, so I did a little searching. I found a website called codecogs.com which has a LaTeX image generator. One can just direct an img tag to that website and get images such as this one:

It seems that in-line variables, such as a variable called , look fine as well.

This code is open-source, so it would be very helpful if Blogger.com would install it so that it can be used without relying on CodeCogs’ website to be up. With my luck, I’ll start using this as my sole method of rendering math and they’ll go out of business…

Interesting way to derive the area formula for a circle

I was bored today and looking through some old notebooks of mine and came across an interesting derivation of the circle area formula using some geometry and the concept of a limit. This idea dates back to my freshman or sophomore year.

Consider an N-gon that is broken up into N identical isosceles triangles with their unique angle touching the center. Let the side that is shared by each triangle have length r. This description might be difficult to understand, so I drew the case for N=5, a pentagon.

Clearly if we let N approach infinity, we get smoother and smoother polygons until we finally get a circle, as shown in the picture below.

So, if we’d like to find the area of the N-gon, we can find the area of each triangle we’ve created and multiply by N. Using that and letting N approach infinity should give us the area of a circle.

Now the inner angle on each of these pentagons is radians, which leaves each of the outer angles to be

,

in radians. As a sanity check, as N goes to infinity here, the angle goes to , which is expected.

Recall that the area for a triangle is , where b is the base width and h is the height of the triangle. We can find the base by the law of sines. That is:

.

This gives us b, but we still don’t have h. Luckily, we can form a right triangle out of half of each isosceles triangle. This new triangle has hypotenuse r and legs h and b/2. Thus

.

Putting things together, we get that

,

or after rearrangement,

If we now take the limit as N goes to infinity, we get an indeterminate form. We can, however, apply L’Hopital’s rule after some rearrangement:

Taking the limit gives the familiar formula.

Part of my purpose for this posting is to test out how Blogspot handles mathematical formulas. As far as I can tell, there’s no easy way to do so. I had to use an image renderer here to render the formulas, and I’m not too impressed with it. I’ll be experimenting with MathML here in the next few days to see how it renders.

Update: Fixed all of the math to go with WordPress’s built in capabilities. Looks pretty nice.

KDE Superkaramba Themes

Well, I was hesitant at first to put time into learning even basic Python commands, but in one evening I learned enough to be able to write two themes for Superkaramba. Both are very similar: the first fetches Garfield comics, and the second fetches xkcd. I’ve uploaded them to KDE-Look.org, and they can be found here and here.

My motivation for creating them was two-fold. First, there were already a few Garfield fetchers for Superkaramba. One seemed to work only when it was the first theme opened in Superkaramba; the other didn’t resize itself for Sunday comics which are a few more panels. Second, there wasn’t an xkcd fetcher for Superkaramba, so I thought I’d make the first!

The Garfield theme does have a small “bug” if you will. The file names change from day to day, and it’s actually a predictable pattern so I’m just using this pattern for now. Unfortunately, it seems the newest comic isn’t posted right at 12:00 AM EST. In fact, it’s almost 1 AM here now, and it still hasn’t been posted. So the theme searches and searches for the file, but it’s not there. I’m not sure when it’s uploaded, but as soon as it is uploaded it should grab it and update itself. I guess the easiest way to fix this is to wait until, say 5:00 AM EST to get it. I’ll work on it soon.

The xkcd grabber, on the other hand, shouldn’t have this problem since I have it reading the newest url right from xkcd’s RSS feed.

If you enjoy them, I’d like to hear from you!