Subject code/name: MAST20022 Group Theory and Linear AlgebraWorkload: Weekly: 3 x 1-hour lectures, 1 x 1-hour tutorial
Assessment:3 individual assignments | 20% |
3-hour end-of-semester exam | 80% |
Lectopia enabled: Yes, with screen capture, but the document camera may not be used; please see below for more comments.
Past exams available: In 2016 Semester 2, two past exams were available with solutions. More were available on the library website without solutions.
Textbook recommendation: No external texts required. A
very comprehensive set of lecture notes is provided and is certainly sufficient.
Lecturer(s): Dr Alexandru (Alex) Ghitza
Year and semester of completion: 2016 Semester 2
Rating: 5 out of 5 (tempted to deduct something for that fire alarm evacuation... HAHA)
Comments:Just what is
group theory? Why am I learning linear algebra again? And why is it that every time I tell someone about this subject they think I'm talking about two subjects?
MAST20022 Group Theory and Linear Algebra is a second-year subject that is a prerequisite for third-year pure maths subjects. Pure maths, being the obscure field it is, is certainly no less obscure as a maths specialisation, which is probably why your general audience always assumes you are talking about two subjects.
Group theory is the study of a mathematical construct called
groups (surprise surprise). Groups are best motivated by the observation that in mathematics, there are many types of sets that, when endowed with a certain operation (a rule of combining two elements in the set), satisfy some common properties, namely
- associativity: (\(a \cdot (b \cdot c) = (a \cdot b) \cdot c\); tersely, your order of evaluation is irrelevant);
- identity: there is a "do nothing" element; and
- invertibility: every element has an element that "undoes" it.
A common example would be the integers \(\mathbf{Z}\) under addition: addition is associative, permits an identity element (namely \(0\)), and naturally gives rise to an inverse for every integer (just negate the integer). Such properties seem like fairly simple properties to come about, and, indeed, in GTLA you will come across a variety of groups.
Group theory forms a natural foundation for the field of
abstract algebra, which, loosely, is the study of the structure of sets in mathematics. In this sense, GTLA opens students to further studies in algebra at the university. Unfortunately, aside from
MAST30005 Algebra, these subjects are taught at the graduate level. The field of algebra enjoys the reputation of being a rather beautiful field of mathematics, and this same sentiment manifests in the university environment:
MAST30005 Algebra is widely reputed to be one of the most enjoyable undergraduate maths subjects. Personally I believe its beauty lies in the fact that groups are introduced with only the simple properties mentioned above, but as more structure (read: conditions and properties) is imposed on the groups, the results become increasingly rich and eye-opening (at least that happens to be my take on GTLA). If ever there was anything I would call "mathemagic", this would be it.
So far I have yet to mention linear algebra. Why exactly is this subject a combination of both group theory and linear algebra, and where is the relationship between them? The group theory and linear algebra topics in GTLA happen to be fairly disjoint; one could outright label each topic as either "group theory" or "linear algebra" without hesitation. However, there are a few parallels between the structures of vector spaces and groups, the most obvious of which is that a vector space over a field satisfies all the aforementioned properties of being a group! As you will see, there are more parallels (bases and generating sets, (normal) subgroups and linear subspaces, homomorphisms and linear transformations); some of these are mentioned, so rest assured that, despite the abstract nature of the group theory topics, many phenomena you have in fact encountered in earlier linear algebra studies. The only other connection that was obvious to me was that some of the groups we worked with directly involved matrices and their properties.
Being a pure maths subject, you might expect the content in GTLA (particularly the group theory topics) to be quite separated from "real world" applications. To an extent this is true; however, Alex does present some highly intriguing applications of both group theory and linear algebra, such as in computer cryptography, special relativity, chemistry (brief mention), and even stochastic processes! Some of these have entire lectures dedicated to them (but are not examinable), in case a passing mention of applicability is not convincing enough.
I would say that students studying GTLA tended to be maths students (no surprise here) but also physics students who might be considering further studies in quantum physics. Quantum physics, to my knowledge, relies on the theory of metric spaces and Hilbert spaces (cue
MAST30026 Metric and Hilbert Spaces, although it is not a prerequisite for the university subjects on quantum physics), which, in turn, relies on some of the content in GTLA.
The difficulty of GTLA lies in its breadth of content. The lectures are very proof-based, and there are many smaller results and properties presented aside from the main ones, some of which you will need to recall very quickly and use frequently. It is a style of mathematics rarely found outside pure maths and is understandably a struggle for students for which GTLA is a first exposure to pure maths beyond first-year linear algebra and real analysis. Alex takes a very structured approach to this subject (teaching theory and then giving
many examples), and consequently it was far easier learning this subject than one might expect from its content.
Subject content
There are five major areas of discussion in the subject, and they are conveniently allocated (usually) one question in Part B of the examination (more on that later). These are:
- the Jordan normal form;
- an introductory discussion on groups with a slight focus on normal subgroups;
- inner product spaces;
- group actions; and
- the Sylow theorems (or, more generally, classifying groups).
Introductory topics
Alex begins with a short illustration on what sorts of problems motivate the study of abstract algebra. From this short lecture alone it was quite easy to see that this subject was going to be different from first-year maths subjects. With uses in studying symmetry, geometric properties, and number systems, the main theme was that abstract algebra is quite literally the abstraction of ideas that are present in various mathematical objects.
The first point of call (even before the Jordan normal form) is the discussion of the principle of mathematical induction (which should be familiar from
MAST10008 Accelerated Mathematics 1) and something called the
well-ordering property, which states that a non-empty subset of the natural numbers \(\mathbf{N}\) always has a smallest element. The principle of mathematical induction and the well-ordering property are shown in lectures to be equivalent.
At a glance it is probably unclear why the well-ordering property is important or even why it is a result on its own (it sounds "obvious"). Perhaps this is more an example of the fragility of mathematical logic: In AM1 you may have used the principle of mathematical induction several times without questioning its validity. It turns out that when setting up the theoretical environment for studying mathematics, either the principle of mathematical induction or the well-ordering property needs to be introduced as an
axiom, that is, something accepted as true without proof. Once this is done, the other is immediately true due to their equivalence, and you can use them to your heart's desire.
This delicate and rigorous approach to logic is somewhat characteristic of studies in pure mathematics, and at various points throughout GTLA and further pure maths studies, you will probably come across proofs for things which you deemed intuitive or obvious.
Following this is some basic number theory and definitions of some types of groups. Number theory is the theory surrounding integers and investigates aspects such as divisibility or factorisation. Admittedly it is not a very prominent topic in GTLA; the areas discussed are the Euclidean algorithm (arising from the division algorithm), Bezout's identity, some properties regarding divisibility, some modular arithmetic, and the fundamental theorem of arithmetic. The results here are discussed in the context of the integers, but some generalise (to an extent) to other sets, such as the set of polynomials. In fact, you will encounter Bezout's identity applied to polynomials later on.
The \(\mathbf{Z}/n\mathbf{Z}\) class of groups is carefully defined during the discussion of modular arithmetic (even though you have not been told what a group is). This class of groups reappears frequently in GTLA and is probably the type of group with which you will become most familiar.
Following the number theory topics, some types of groups are defined. Starting with the most general, these are:
- rings,
- commutative rings,
- fields, and
- algebraically closed fields.
All algebraically closed fields are fields, and all fields are commutative rings, and so on. The purpose of this short section is to define fields and algebraically closed fields, which is necessary to understand the next topic on the Jordan normal form, as they are mentioned in some definitions and results.
Properties specific to these types of groups are not really discussed in GTLA, but it is important to know what the definitions of these types of groups are. Admittedly it might be easier to revisit these definitions once you are taught the definition of a group (which is yet to take place at this point).
The Jordan normal form
The first major topic, the Jordan normal form, essentially occupies the lectures in Weeks 3 to 6. The main result can be stated quite easily, but there is a myriad of intermediate results leading up to it. In fact, you do not even discuss all the intermediate results completely (an important one is left for
MAST30005 Algebra).
The motivation behind studying the Jordan normal form is that many square matrices, when interpreted as linear transformations, are actually the "same" linear transformation but expressed with respect to a different basis. Equivalently, a linear transformation interpreted for different bases gives you many different matrix representations, but they are fundamentally really one and the same. Imagine, in \(\mathbf{R}^3\)
- a dilation by a factor of 2 from the \(x\)–\(y\) plane; and
- a dilation by a factor of 2 from the \(y\)–\(z\) plane.
These are really quite similar — they are the same linear transformation but for different bases.
The Jordan normal form of a matrix is the simplest square matrix among all those which can be said to be the same linear transformation as the original (the basis will generally be different). Notably, the Jordan normal form is unique up to permutation of the basis vectors, and its simplicity comes in the form of being almost diagonal.
This topic comes under linear algebra, and you will need to be familiar with first-year linear algebra content to understand this topic, as there is
very little time for revision, and new ideas are introduced fairly quickly. Make sure you know what these are: subspaces, spans, bases, row reduction, the rank–nullity theorem, linear transformations, change of basis, eigenvalues, and eigenvectors. Alex includes thorough notes for these first-year topics, but they are hardly discussed in lectures.
The number of intermediate results for this topic is quite remarkable, and it will probably be overwhelming to be familiar with all of them. I would recommend being familiar with properties of
invariant subspaces (subspaces which are invariant under a linear transformation), as they are most easily examined; there are quite a few tricks involved with the other intermediate results.
Overall this topic is a very involved and instructive exposure to the Jordan normal form; there are numerous defined stages, and the way it is delivered certainly feels like you are stepping through history (the stages are something like: square matrices \(\to\) block diagonal matrices \(\to\) upper triangular block diagonal matrices \(\to\) almost diagonal matrices i.e. the Jordan normal form).
The topic concludes with lectures discussing applications of these results to special relativity and Markov chains.
Introduction to groups
After 6 weeks of lectures, you are finally properly introduced to the foreign half of the namesake of this subject. Several definitions and properties are immediately thrown at you; as a completely new mathematical object, it is bound to be overwhelming at the offset.
My recommendation is to study these new definitions, properties, and concepts in the context of a single group. This is done in many examples in lectures, but if you find this to be insufficient in consolidating these concepts, then isolating a single group (maybe a dihedral group or \(\mathbf{Z}/n\mathbf{Z}\)) and studying all the discussed concepts (subgroups, orders, finding generators, finding homomorphisms to other groups, normal subgroups, applying the first isomorphism theorem, and so on) in the context of that group may help.
In becoming familiar with these concepts, I also found it invaluable linking group concepts with those in vector spaces. There are some very obvious parallels, and your greater familiarity with vector spaces may mean that drawing parallels allows you to grasp the group concepts more quickly.
There are several classes of groups appearing frequently throughout GTLA. You definitely need to know what these are by their symbolic representations, as they may not be defined in the questions that use them. These include
- \(\mathbf{Z}/n\mathbf{Z}\) for natural \(n\) under addition (for \(n > 1\) but especially prime \(n\));
- the dihedral group \(D_n\) consisting of symmetries of a regular \(n\)-gon for \(n > 2\);
- the symmetric group \(S_n\) consisting of permutations of \(n\) distinct elements;
- the general linear group \(\mathrm{GL}_n(K)\) consisting of invertible \(n \times n\) matrices with entries in a field \(K\) (with the operation being matrix multiplication); and
- the special linear group \(\mathrm{SL}_n(K)\) consisting of \(n \times n\) matrices with determinant \(1\) with entries in a field \(K\) (with the operation being matrix multiplication).
With algebra being the study of structures of sets, some concepts are introduced in this topic to study the structure of groups. The existence of a
homomorphism between two groups means that their structures are similar (in the way that elements interact with each other). The existence of an
isomorphism between two groups means that their structures are identical.
The main result in this topic is the
first isomorphism theorem, which gives a decomposition of a group's structure if there is a homomorphism with another group. For example, the non-zero complex numbers under multiplication is a group, and, using the first isomorphism theorem, one part of its structure can be identified as the structure of the positive real numbers under multiplication.
Another notion related to the decomposition of group structure is a
normal subgroup. Together with the first isomorphism theorem (in which normal subgroups make an appearance anyway), they make up the majority of the methods used to study group structure in GTLA.
One of the other important sections in this topic is the theory on free groups. A
free group is a type of group where elements have minimal properties (this is not a rigorous description). By imposing properties on certain elements, a free group assumes more structure. Free groups are introduced to discuss
group presentations, which, given a particular group structure, are the ways of changing the structure of a free group to arrive at that particular group structure.
Group presentations are thus bare representations of group structure. They are not used heavily in GTLA, but it is good to know that there is a universal notation for talking about group structures. Sometimes Alex may use a group presentation to denote a group [structure] instead of using its common name, mostly for dihedral groups (the group presentations have the potential to be horrendous). There is also a small section on using group presentations to study homomorphisms between groups.
At the end of this topic is a short example relating group theory to RSA cryptography.
Inner product spaces
After a decent exposure to group theory is a topic on inner product spaces, beginning at around Week 10.
Inner products are no stranger: you have encountered its definition in AM1.
An inner product space is simply a vector space endowed with an inner product. With an inner product, notions like distance, length, orthogonality, and angle come into existence. This topic is (probably) the most important in preparing for future studies in topology (
MAST30026 Metric and Hilbert Spaces).
While inner products were largely studied in the context of real numbers in AM1, the treatment in GTLA is more general. This is important if you remember a part of the definition of an inner product as symmetry — this is not true outside the real numbers.
The Gram–Schmidt process makes a reappearance with the appropriate reassurance that it is indeed an algorithm for finite-dimensional inner product spaces.
The most important concept introduced is the
adjoint of a linear transformation on an inner product space. Its inclusion seems somewhat arbitrary at first but is necessary in discussing the intermediate results leading up to the major result of this topic. Linear transformations can be classified as certain types if conditions involving itself and its adjoint are satisfied. The different ways of characterising these types of linear transformations is the focus of a few of the results in lectures and problems in the tutorials and exams — sometimes you will be asked to prove that two different characterisations are equivalent. This can be quite difficult because of the numerous characterisations (I certainly do not recommend memorising the proofs), but luckily in exam situations hints are given.
The
spectral theorem, the main result of this topic, states the conditions under which matrices can be represented as a diagonal matrix with respect to an orthonormal basis. You may recall in AM1 that this was always possible for real symmetric matrices; that was no coincidence, and the spectral theorem is the more general result.
Group actions
This is a short topic which begins in the middle of Week 11.
A group action is a set of rules dictating how a group interacts with a general set. The set may even be a group itself, which makes for slightly richer results.
There is a bit of terminology to learn, particularly when discussing the conjugation group action (this is a type of group action on a group).
The main result here is the orbit–stabiliser formula, which relates the number of elements in the group involved in a group action to other characteristics of the group action. These characteristics of the group action happen to be relatively easy to determine (at least that is the case in GTLA), so the result is useful when the group is not completely known.
Sylow theorems
This topic is even shorter than the topic on group actions is and only takes one or two lectures — in fact, it is included under the group actions section in the notes, even though the results themselves do not involve group actions. They are, however, a generalisation of Cauchy's theorem, the proof of which relies on group actions.
The Sylow (pronounced sill-low) theorems are results that assert the existence of subgroups of certain sizes in a group. More precisely, there are four results, and you will have to memorise these results, because their proofs are not discussed in GTLA (I gather they are probably far too difficult).
These theorems are the last major tool used to study the structure of groups in GTLA, and the relevant problems in the exam are usually also the harder ones.
The subject ends on a brief note of the massive mathematical work dedicated to classifying group structure. From 1955 to 2004, mathematicians collaborated to classify all finite simple groups — finite referring to the number of elements in the group and simple referring to the fact that the structure is monolithic and cannot be decomposed further. It was a work that required tens of thousands of pages and is just further proof that group theory, though founded on a novel three-part definition of a group, is certainly no simple matter.
Lectures
Alex produces a ridiculously comprehensive set of lectures notes, on which the lectures are based completely. These are incrementally provided on the subject's website at
http://www.ms.unimelb.edu.au/~aghitza@unimelb/teaching/gtla/ (Alex really only used the LMS for some announcement emails). The set of notes is beautifully produced in \(\LaTeX{}\), with numbering and labelling of basically everything (such as Theorem 4.43, Lemma 3.22, or Example 4.9). The notes are even labelled with the dates on which content was discussed in lectures and some estimates of when future content will be covered.
That is not to say that lectures are unnecessary, but it is certainly a relief that basically everything discussed in lectures is written in mathematical prose.
The lectures themselves are of a high quality, and Alex consistently gives clear concise explanations for new concepts. Being an abstract subject, it was brilliant to see so many examples for everything. After introducing new concepts (or sometimes before the introduction, in order to clarify the motivation for studying them), Alex would discuss concrete examples and explain how parts of the definitions were satisfied, how the properties hold, how to apply an algorithm to this case, and so on. It was helpful to see all the theory in action in a lecture, and this made the subject far less intimidating.
Even putting aside the fantastic lecture quality, I would recommend going to lectures simply because Alex makes most of his announcements there. Unless you are stringent in regularly checking the subject website (or watching lecture recordings), it is possible you may be late in finding out important information. Sometimes tutorials also required content from the current week (more on that later), which means even lecture recordings are not timely enough.
Alex does not ask the students many questions during lectures, but keep in mind there is consistently quite a lot of material that needs to be covered, so opportunities for open brainstorming by students are few and far between.
On the note of the amount of content, I would say that in 2016 Semester 2 lectures were slightly behind, given that there was sometimes a bit of rushing at the end of lectures. All content was covered by the end, however.
Alex writes on the whiteboard during lectures, so it is ideal not to sit too far back. Technically both video (for the document camera) and audio are recorded, but the video is inherently not of much use. In 2016 Semester 2, Alex used the document camera for one of the lecturing venues because the students were seated too far from the whiteboard for it to be useful. I assume that this means the whiteboard will always be used unless it is physically infeasible during lectures.
Tutorials
Tutorials follow the traditional format for maths subjects. You are given a tutorial sheet at the start of the tutorial and form groups to solve the problems.
I would say that tutorial problems were generally hard, but this needs qualification: because of the new concepts and definitions that were consistently being introduced in lectures each week, unless you were consistently up to date with a good memory of all the definitions and results, you would not even be able to attempt the more basic problems on the tutorial sheets.
Realistically speaking, there were only ever one or two problems (out of seven or eight) that required innovative ideas or tricks; tutorial problems were by and large computational or simple applications of definitions or results. Sometimes a technique that was used in a proof in lectures would come in use, so it is important not only to know the content delivered in lectures, but also some of the methods and tricks employed in some of the delivered proofs, which Alex may not always explicitly point out. For example, if you are given that an inner product of certain elements in a vector space is always 0, then attempting to make both operands the same expression would mean that the operand has to equal 0 by the definition of an inner product. This is a technique used a few times in the inner product spaces topic.
Tutorial sheets are made available online on the subject's website, and at the end of the week solutions are also made available. The solutions contain fairly comprehensive working, so you should be able to understand solutions to all tutorial problems by the end of the semester.
I am not sure if this was intentional, but sometimes tutorial problems involved content which had only been delivered in lectures occurring in the same week as the tutorial. Older students will know that problem-based tutorials usually only have problems that need content covered up until the end of the previous week. I took this as a further sign that lectures were behind schedule, but even though my own tutorial was in the middle of the week, I never encountered problems in tutorials that needed content that was yet to be covered, so it is possible that the tutorials were deliberately scheduled to make this possible.
Assignments
There are three assignments throughout the semester, all uploaded on the subject's website (not the LMS). These are collectively worth 20% of your final grade; precise information about the breakdown was not provided.
Make sure you know when they are released, because assignment releases were not announced on the LMS; Alex points out in lectures when they are released, although this was sometimes one or two days after it was already available on the website (in case you are very keen).
Assignments are released before the required content has been fully covered, but it is still possible to complete some of it at the time of release. Students are given slightly more than two weeks to submit for each assignment.
Assignments are not very difficult and are fairly short; the difficulty is comparable to those on tutorial sheets, and most assignment problems are also direct computations or simple applications of results. In 2016, there was one question which introduced a new concept, but it was not mentioned again elsewhere.
Be careful to give full justification for everything; rigour is absolutely vital in pure maths.
End-of-semester exam
The exam is 3 hours long and is divided into Parts A and B. As with many maths subjects, it constitutes 80% of your final grade in GTLA. Historically, the exams that Alex has prepared have all been worth 100 marks each, with Parts A and B each worth 50 marks.
Part A is an act of mercy, honestly (given the difficulty of this subject): it consists purely of tutorial questions, many of which are reproduced verbatim, others of which may involve different numbers but otherwise can be dispensed with identically. This is announced by Alex to be the case, so this is not secret information or anything.
The message here is clearly that you should practise and be able to provide solutions to every single tutorial problem. This is not very far from knowing all the definitions and results fairly competently, but as mentioned earlier the more technique-based problems will require more attention. I am not recommending that you memorise solutions to all the tutorial problems; I am, however, advocating in favour of a good knowledge of all the definitions and results (no surprise here) and a reasonable familiarity with the techniques used in some of the harder tutorial problems.
Part A contributes a maximum of 40 to your final grade, so with a reasonable assignment performance, passing GTLA should not be an issue, even if you insist on rote-learning solutions to tutorial problems. Note that this is not a hurdle exam.
Part B is the more involved section of the paper, with a multi-part question dedicated to each of the topics outlined in the subject content above. Group actions and Sylow theorems are treated as one topic, so it is possible that one may not be tested in Part B.
The questions in this section are overall substantially harder than all tutorial problems (even the harder tutorial problems). The difficulty is mitigated in that marks are split between more parts, many of which are clues towards what may be useful in later parts. Sometimes hints are also explicitly included for harder questions.
There is nothing in Part B which requires the reproduction of a proof given in lectures, so there is no need to memorise those proofs. You may be required to prove a simpler version of results in lectures, however. For example, if a proof of the equivalence of statements \(A\), \(B\), and \(C\) was given in lectures by proving \(A \Rightarrow B\), \(B \Rightarrow C\), and \(C \Rightarrow A\), you may be required to prove in Part B of the exam that \(A\) and \(C\) are equivalent, i.e. that \(A \Rightarrow C\) and \(C \Rightarrow A\), noting that \(A \Rightarrow C\) is probably easier to prove than proving both\(A \Rightarrow B\) and \(B \Rightarrow C\).
Some of the question parts in Part B will require original arguments that you may not have encountered before. This is hit-and-miss from student to student, so do not fret about these parts. I found that the hardest question in Part B was usually a question regarding group actions or the Sylow theorems. In particular, classifying group structure with the Sylow theorems was not always very straightforward; Alex does some examples of these in lectures, but it is clear that there is no methodical approach that applies to all groups. (There is also the 50-year classification of finite simple groups in case you are not convinced.)
Occasionally you will be asked in Part B to write down a theorem statement. This is something you should do verbatim, as the wording of mathematical theorems is always very precise, so I recommend memorising all the statements of the major result from each of the topics mentioned earlier. In particular, do not forget smaller details like the requirement for a vector space to be finite-dimensional, a field to be algebraically closed, or whether the existence of something is unique. These are all vital details which taint the accuracy of your statement. Technically, of course, you are simply wrong if you omit anything, because this is maths. On the other hand, do not accidentally add more conditions to restrict the result, because what you state will then not be the required theorem, even though it may still be a true statement.
It helps if you are somewhat familiar with the proofs of these major theorems, because then you may be able to justify the conditions stated in the theorem even if you have not memorised the theorem statement verbatim. For example, the requirement for vector spaces to have finite dimension is because some of the theorems deal with matrices, which are by nature of finite dimension. The requirement for the field to be algebraically closed in the theorem about the Jordan normal form is because we require the minimal polynomial to be factored completely into linear factors, which is not always possible if the field is not algebraically closed.
You should expect to use the major theorem for each topic in Part B for the topics which are assessed, so try and apply the major theorem if you are ever stumped.
GTLA is a long stride away from most other undergraduate maths subjects, but if you are comfortable with abstract theory, then it gives you an insight into a very beautiful area of mathematics. The hard work is there, but so is the satisfaction.