Intro to Abstract Algebra

Linear Algebra to Algebraic Foundations

← Back to Section I Overview
Part 1: Linear Equations Part 2: Linear Transformation Part 3: Matrix Algebra Part 4: Determinants Part 5: Vector Spaces Part 6: Eigenvalues & Eigenvectors Part 7: Orthogonality Part 8: Least-Squares Problems Part 9: Symmetry Part 10: Trace and Norms Part 11: Kronecker Product & Tensor Part 12: Woodbury Matrix Identity Part 13: Stochastic Matrix Part 14: Graph Laplacians and Spectral Methods Part 15: Intro to Abstract Algebra Part 16: More Finite Groups Part 17: Structural Group Theory Part 18: Classification of Finite Abelian Groups
Abstract Algebra Intro to Groups Abelian The Group of Units Modulo \(n\) Multiplicative Group vs Additive Group Subgroups Cyclic Subgroups Center of a Group Centralizer of an element in a Group

Introduction

At this point, we are already familiar with the rules of linear algebra, and we have encountered many mathematical objects and operations in our school life. What we have done is essentially studying operations constrained by a particular environment, or structure. Now, we would like to discuss the "structure" of our mathematical world more formally. From now on, the term "algebra" expands beyond algebraic computation to mean the study of these underlying structures. In abstract algebra, we learn the fundamental laws that govern operations across mathematics. Our goal is to categorize these mathematical structures (Groups, Rings, and Fields), giving us a clear, unified view of the mathematical world. This rigorous approach is not just theoretical, which will contribute directly to advancements in computer science and engineering.

We start with a special kind of set, which is called a group.

Intro to Groups

Groups:

A set \(G\) is said to be a group under a binary operation if the following three properties are satisfied:

  1. Associativity
    2. \[ \forall a, b, c \in G, \, (ab)c = a(bc). \]
  2. Identity
    3. \[ \exists \, e \in G \text{ s.t. } \forall a \in G, \, ae = ea = a. \]
  3. Inverses
    4. \[ \forall a \in G, \exists \, b \in G \text{ s.t. } ab = ba = e. \]

Note that the binary operation assigns to each ordered pair \(a, b\) of elements of \(G\) an element in \(G\). We deonte it by \(ab \in G\). This condition is called closure.

For example, consider a square matrix: \[ A = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \] assuming \(\det(A) = ad -bc \neq 0\) where \(a, b, c, d \in \mathbb{R}\). Then we know that we have the identity matrix: \[ I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} \] such that \[ IA = AI = A \] and the inverse of \(A\): \[ A^{-1} = \begin{bmatrix} \frac{d}{\det (A)} & \frac{-b}{\det (A)} \\ \frac{-c}{\det (A)} & \frac{a}{\det (A)} \\ \end{bmatrix} \] such that \[ AA^{-1} = A^{-1}A = I \] We would like to say that this set of all \(2 \times 2\) invertible matrices forms the group under matrix multiplication: \[ GL(2, \mathbb{R}) = \left\{ \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \mid a, b, c, d \in \mathbb{R}, \, ad-bc \neq 0 \right\}. \] This group, the general linear group of degree 2 over the real numbers, is a fundamental object in abstract algebra.

Abelian

The general linear group is a typical example of a non-Abelian group.

Abelian Group:

If a group \(G\) satisfies the commutative property for every pair of its elements \(a\) and \(b\), the group \(G\) is called an Abelian group. \[ \forall a, b \in G, \, ab = ba \in G. \]

As we know, in matrix multiplication, for matrices \(A\) and \(B\), \[ AB \neq BA. \] Thus, \(GL(2, \mathbb{R})\) is a non-Abelian group.

For example, a simple Abelian group can be the set of nonzero real numbers under ordinary multiplication, denoted by \(\mathbb{R}^*\). Let \(x \in \mathbb{R}^*\), then the identity is \(1\), the inverse is \(\frac{1}{x}\). Moreover, for every \(x, y \in \mathbb{R}^*\), \(xy = yx \in \mathbb{R}^*\).

The Group of Units Modulo \(n\)

In Computer Science, we frequently use modular arithmetic, which is fundamental to cryptography (e.g., RSA), hashing algorithms, and how computers handle integer representations. Here we introduce the Group of Units Modulo \(n\), denoted by \(U(n)\).

First, let's briefly review the definition of the modulo operation, which is based on the Division Algorithm:

Modular Arithmetic:

Given integers \(a\) (dividend) and \(n\) (divisor), we write \(a \bmod n = r\) if: \[ a = qn + r \] where \(q\) is the quotient and \(r\) is the remainder, and the remainder must satisfy the condition \(0 \leq r < n\).

For example, \[ \begin{align*} 11 \bmod 2 &= 1 \text{ since } 11 = 2 \cdot 5 + 1, \\\\ 24 \bmod 8 &= 0 \text{ since } 24 = 8 \cdot 3 + 0, \\\\ 9 \bmod 12 &= 9 \text{ since } 9 = 0 \cdot 12 + 9, \\\\ -5 \bmod 2 &= 1 \text{ since } -5 = (-3) \cdot 2 + 1, \\\\ \end{align*} \]

An important property in modular arithmetic is that an integer \(a\) has a multiplicative inverse modulo \(n\) if and only if \(a\) and \(n\) are relatively prime (i.e., their greatest common divisor is 1, \(\gcd(a, n) = 1\)).

For any positive integer \(n\), we define \(U(n)\) to be the set of all positive integers less than \(n\) that are relatively prime to \(n\). This set \(U(n)\) forms a group under the operation of multiplication modulo \(n\).

For example, when \(n = 12 = 2^2 \cdot 3\), we eliminate multiples of 2 and 3 from \(\{1, 2, \cdots, 10, 11\}\), we obtain \(U(12) = \{1, 5, 7, 11\}\). Moreover, Cayley Table for \(U(12) = \{1, 5, 7, 11\}\) is as follows:

\(\bmod \mathbf{12}\) \(\mathbf{1}\) \(\mathbf{5}\) \(\mathbf{7}\) \(\mathbf{11}\)
\(\mathbf{1}\) 1 5 7 11
\(\mathbf{5}\) 5 1 11 7
\(\mathbf{7}\) 7 11 1 5
\(\mathbf{11}\) 11 7 5 1

In this table, for example, \((5 \cdot 7) \bmod 12 = 11 \in U(12)\), and as you can see, this is an example of finite Abelian group.

The number of elements of a group \(G\) is called its order denoted by \(|G|\). For example, \(|U(12)| = 4\), and \(|GL(2, \mathbb{R})| = \infty\). So, \(GL(2, \mathbb{R})\) is said to be the infinite non-Abelian group.

Multiplicative Group vs Additive Group

So far we have seen multiplicative groups whose binary operation is some sort of multiplication (like matrix multiplication or modular multiplication), but sometimes binary operation can be addition. A simple additive group is the set of integers: \[ \mathbb{Z} = \{\cdots, -2, -1, 0, 1, 2, \cdots\} \] This set forms a group under standard addition, which is a valid binary operation since the sum of two integers is an integer. For any \(a, b, c \in \mathbb{Z}\): \[ \begin{align*} &(a + b) + c = a + (b + c), \\\\ &a + 0 = 0 + a = a, \\\\ &a + (-a) = (-a) + a = 0. \\\\ \end{align*} \] In addition, this group is Abelian since standard addition is commutative: \(a + b = b + a\).

In abstract algebra, the choice of operation impacts notation, which can be initially confusing.

In "additive" groups, the notation \(a^m\) is written by \(ma\). For instance, \(a^3\) means repeated addition: \[ a^3 \rightarrow \quad a + a + a = 3a. \] Note that the multiplier \(3\) here is NOT an element being combined with \(a\) under the group operation. Similarly, \(-3a\) represents the sum of three inverses \((-a)+(-a)+(-a)\).

In "multiplicative" groups, we use exponent rules familiar from algebra, such as \(a^m a^n = a^{m+n}\) and \((a^m)^n = a^{mn}\). However, the definition of the group structure requires careful expansion, especially in non-Abelian groups: \[ (ab)^2 = abab \quad \text{NOT} \quad a^2b^2 \text{ (unless the group is Abelian)}. \] Note that the expression \( (ab)^2 = a^2b^2 \) is valid if and only if the group is Abelian. This is because commutativity (\(ab = ba\)) allows for the rearrangement: \[ \begin{align*} (ab)^2 &= a \cdot b \cdot a \cdot b \\\\ &= a \cdot a \cdot b \cdot b \\\\ &= a^2b^2. \end{align*} \]

Similarly, for negative exponents: \[ (ab)^{-2} = ((ab)^{-1})^2 = (b^{-1}a^{-1})(b^{-1}a^{-1}). \] Note that for \(a^n \in G\), if \(n\) is negative, \(a^n = (a^{-1})^{|n|}\). Also, the exponent \(n\) is always an integer (unlike exponents used in the field of real numbers). The zero exponent represents the identity element: \(\mathbf{a^0 = e}\).

Moreover, we define the order of an "element" \(a \in G\) denoted by \(|a|\) as the smallest positive integer \(n\) such that \(a^n =e\). (In additive notation, \(na = 0\).) If there is no such integer, the element \(a\) has infinte order.

For example, in \(U(12) = \{1, 5, 7, 11\}\), \[ \begin{align*} \text{ The order of 1 is 1 since } 1^1 &= 1 = (0 \cdot 12) + 1, \\\\ \text{ The order of 5 is 2 since } 5^2 &= 25 = (2 \cdot 12) + 1,\\\\ \text{ The order of 7 is 2 since } 7^2 &= 49 = (4 \cdot 12) + 1,\\\\ \text{ The order of 11 is 2 since } 11^2 &= 121 = (10 \cdot 12) + 1. \\\\ \end{align*} \]

Subgroups

Subgroups:

If a subset \(H\) of a group \(G\) is itself a group under the same operation of \(G\), \(H\) is said to be a subgroup of \(G\) denoted as \(H \leq G\). (Also, we write \(H < G\) to denote a proper subgroup.)

For example, consider the group of integers under addition, \(\mathbb{Z}\). Let \(H\) be the set of all even integers: \[ H = \{\dots, -4, -2, 0, 2, 4, 6, \dots\}, \] This subset \(H\) forms a group under the same standard addition because the sum of two even integers is always an even integer, which holds commutativity, the identity \(0 \in H\), and the inverse of any even integer is also an even integer. Thus, \(H \leq \mathbb{Z}\).

Checking all group axioms every time can be tedious. A way to show that a subset \(H\) of a group \(G\) is a subgroup of \(G\) is One-Step Subgroup Test:

One-Step Subgroup Test:

A nonempty subset \(H\) of a group \(G\) is a subgroup if for all \(a, b \in H\), the element \(a b^{-1} \in H\). (In additive notation, check \( (a - b) \in H\)).

Proof:

We must verify that \(H\) possesses the identity element, inverses for every element, and closure. First, associativity is inherited automatically from \(G\).

Since \(H\) is nonempty, there exists at least one element \(x \in H\). Applying the hypothesis with \(a = x\) and \(b = x\), we get: \[ a b^{-1} = x x^{-1} = e. \] Since the result must be in \(H\), the identity element \(\mathbf{e \in H}\).

Now we know \(e \in H\), let \(x\) be any element in \(H\). Apply the hypothesis with \(a = e\) and \(b = x\): \[ a b^{-1} = e x^{-1} = x^{-1}. \] Since the result must be in \(H\), for every \(x \in H\), its inverse \(\mathbf{x^{-1} \in H}\).

Finally, we must show that \(H\) is closed. Let \(x\) and \(y\) be any two elements in \(H\). We must show that \(xy \in H\). We have already shown that if \(y \in H\), then \(y^{-1} \in H\). Now, apply the hypothesis with \(a = x\) and \(b = y^{-1}\): \[ a b^{-1} = x (y^{-1})^{-1} = xy \] Since the result must be in \(H\), \(\mathbf{xy \in H}\).

Therefore, \(H\) is a subgroup of \(G\).

Cyclic Subgroups

To construct a subgroup for a group \(G\), we start with a single element \(a \in G\) and keep applying the group operation to it. This generates a special set called a cyclic subgroup.

Cyclic Subgroup: Let \(G\) be a group and let \(a\) be any element of \(G\). The set of all integer powers of \(a\) is called the cyclic subgroup of \(G\) generated by \(a\), denoted by \(\langle a \rangle\): \[ \langle a \rangle = \{ a^n \mid n \in \mathbb{Z} \} \] (For additive operation, \(\langle a \rangle = \{ na \mid n \in \mathbb{Z} \}\)).

Is this really a subgroup of \(G\)? We can prove it easily using the One-Step Subgroup Test.

Proof:

Since \(a \in \langle a \rangle\), \(\langle a \rangle\) is not empty. For any integers \(m , n\), let \(a^m\) and \(a^n\) be any two elements in \(\langle a \rangle\).

We apply the One-Step Test condition: \[ a^m (a^n)^{-1} = a^m a^{-n} = a^{m-n}. \] Since \(m\) and \(n\) are integers, their difference \(m-n\) is also an integer. Therefore, \(a^{m-n}\) is another power of \(a\), so it must be in \(\langle a \rangle\).

Thus, \(\langle a \rangle\) is a subgroup of \(G\).

Let's revisite the group \(U(12) = \{1, 5, 7, 11\}\) under multiplication modulo 12. We can generate subgroups by picking elements and computing their powers modulo 12.

Probably, a more interesting group can be \(U(10) = \{1, 3, 7, 9\}\).

Note that when \(G = \langle a \rangle\), the group \(G\) is called cyclic and the element \(a\) is called a generator of \(G\). So, in this case, \(U(10)\) is cyclic, and the elements \(3\) and \(7\) are generator of \(U(10)\), whereas since no single element generates all four elements of \(U(12)\) the group \(U(12)\) is not cyclic.

Center of a Group

Here, we introduce another important subgroup.

Center of a Group: The center of a group \(G\) is the subset of elements in \(G\) that commute with every element of \(G\): \[ Z(G) = \{a \in G \mid ax = xa, \, \forall x \in G\}. \] (Note: The notation "\(Z(G)\)" comes from the German word for center, "Zentrum.")

Indeed, the center of a group \(G\) is a subgroup of \(G\):

Proof: The identity element \(e \in G\) commutes with every element \(x \in G\): \[ ex = xe = x. \] So, \(e \in Z(G)\) and thus \(Z(G)\) is nonempty. Now, Let \(a, b \in Z(G)\), and \(x \in G\). Since \(a, b \in Z(G)\), \[ \begin{align*} ax &= xa, \\\\ bx &= xb. \\\\ \end{align*} \] We must show that if \(a, b \in Z(G)\), then \(c = ab^{-1} \in Z(G)\). So we must show that \(c\) commutes with every element \(x \in G\): \[ cx = xc. \] From the left hand side of this equation: \[ \begin{align*} cx &= (ab^{-1})x \\\\ &= a(b^{-1}x) \\\\ &= a(xb^{-1}) && \text{(Since } b \in Z(G) \text{ implies } xb^{-1} = b^{-1}x \text{)} \\\\ &= (ax)b^{-1} \\\\ &= (xa)b^{-1} \\\\ &= x(ab^{-1}) \\\\ &= xc. \end{align*} \] Thus, \(ab^{-1} \in Z(G)\), which satisfies the one-step subgroup test. Therefore, \(Z(G) \leq G\).

Note that the Center \(Z(G)\) is always an Abelian subgroup:
The definition of \(Z(G)\) requires an element \(a\) to commute with all elements in \(G\). If we take any two elements, \(a\) and \(b\), from \(Z(G)\), \(a\) must commute with \(b\). Thus, \(ab = ba\), which satisfies the definition of an Abelian group.

Ultimately, a group \(G\) is Abelian if and only if its Center is the entire group.

\[ G \text{ is Abelian } \iff Z(G) = G. \]
The reasoning also comes from their definition. If \(G\) is Abelian \(\Rightarrow \), every element commutes with every other element, so every element must be in the Center \(Z(G) = G\). Conversely, if \(Z(G) = G\) \(\Leftarrow \), the definition of the Center dictates that every element must commute with every other element, making \(G\) Abelian.

For example, \(U(12) = \{1, 5, 7, 11\} = Z(U(12))\), whereas \(GL(2, \mathbb{R}) \neq Z(GL(2, \mathbb{R}))\) since \[ Z(GL(2, \mathbb{R})) = \left\{ \begin{pmatrix} c & 0 \\ 0 & c \end{pmatrix} \mid c \in \mathbb{R}, c \neq 0 \right\}. \]

Centralizer of an element in a Group

It is possible that some elements in a non-Abelian group commute with only a proper subset of the group. The centralizer is a generalization of the Center \(Z(G)\) that allows us to precisely identify and study the set of elements that commute with a single, fixed element \(a \in G\). It is in non-Abelian groups that the centralizer becomes a powerful tool for exploring internal group structure.

Centralizer of \(a\) in \(G\): Let \(a \in G\) be fixed. The centralizer of \(a\) in \(G\) is the set of all elements in \(G\) that commute with \(a\): \[ C(a) = \{g \in G \mid ga = ag\}. \]

An important result is as follows:

\[ \forall a \in G, \, C(a) \leq G. \]
Proof:

The identity element \(e\) is in \(C(a)\) since \(ea = ae = a\), so \(C(a)\) is nonempty.

Let \(x, y \in C(a)\). We must show \(xy^{-1} \in C(a)\), meaning \((xy^{-1})a = a(xy^{-1})\).

We know \(xa = ax\) and \(ya = ay\). From the latter, we derive that \(y^{-1}\) also commutes with \(a\): From \(ya = ay\), applying left and right multiplications by \(y^{-1}\) on both sides of the equation: \[ y^{-1}(ya)y^{-1} = y^{-1}(ay)y^{-1} \implies ay^{-1} = y^{-1}a. \]

Now we verify that \(xy^{-1}\) commutes with \(a\): \[ \begin{align*} (xy^{-1})a &= x(y^{-1}a) \\\\ &= x(ay^{-1}) && \text{(Since } y \in C(a) \text{)} \\\\ &= (xa)y^{-1} \\\\ &= (ax)y^{-1} && \text{(Since } x \in C(a) \text{)} \\\\ &= a(xy^{-1}) \end{align*} \] Thus, \(xy^{-1}\) commutes with \(a\), and by the one-step subgroup test, \(C(a) \leq G\).

Note that:

\[ \forall a \in G, \, Z(G) \subseteq C(a). \]

This inclusion follows directly from the definitions:
an element that commutes with every element of \(G\) certainly commutes with \(a\) in particular. On the other hand, , if an element \(g\) lies in every \(C(a)\), then \(g\) commutes with all elements of \(G\), hence \(g \in Z(G)\). Therefore, the center is precisely the intersection of all centralizers: \[ Z(G) = \bigcap_{a \in G} C(a). \]

Another important fact is as follows:

\[ G \text{ is Abelian } \iff \forall a \in G, \, C(a) = G. \]

This is also straightforward: if \(G\) is Abelian, every element commutes with every other, so \(C(a) = G\) for all \(a\). Conversely, if \(C(a) = G\) for all \(a \in G\), then every element of \(G\) commutes with \(a\), and since \(a\) is arbitrary, every pair of elements commutes, so \(G\) is Abelian.


Remember, the General Linear Group \(G = GL(2, \mathbb{R})\) is non-Abelian. We have shown that its center \(Z(G)\) consists only of scalar matrices. To verify the intersection formula, consider a non-scalar matrix \(A \in G\), for instance, the shear matrix: \[ A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}. \] Its centralizer \(C(A)\) is the set of all matrices \(M \in G\) that commute with \(A\) (\(MA = AM\)). Solving for \[ M = \begin{pmatrix} x & y \\ z & w \end{pmatrix} \] shows that \(C(A)\) requires \(z=0\) and \(w=x\): \[ C(A) = \left\{ \begin{pmatrix} x & y \\ 0 & x \end{pmatrix} \mid x, y \in \mathbb{R}, x \neq 0 \right\}. \] Notice that \(C(A)\) is a subgroup of \(G\), which fits the hierarchy \(Z(G) \subsetneq C(A) \subsetneq G\). If we calculate the centralizer for a different non-scalar matrix, say \[ B = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \] we get a different subgroup \(C(B)\). The intersection of all such centralizers removes elements that fail to commute with some matrix, leaving only the center \(Z(G)\).

In contrast, for the Abelian group \(U(12)\), every element commutes with every other element. This means the centralizer of every element is the entire group: \[ C(1) = C(5) = C(7) = C(11) = U(12). \] Therefore, the intersection of all centralizers is simply the intersection of the set \(U(12)\) with itself, confirming that \(Z(U(12)) = U(12)\).