From Groups to Rings
In the previous pages, we developed the theory of groups — algebraic structures with a single binary operation satisfying closure, associativity, identity, and inverse properties. Groups capture symmetry and have wide applications from cryptography to physics. However, when we consider our most familiar number systems — the integers \(\mathbb{Z}\), the rationals \(\mathbb{Q}\), or the reals \(\mathbb{R}\) — we notice that they come equipped with two operations: addition and multiplication. A group structure alone cannot capture this richer algebraic behavior. This observation motivates the study of rings: algebraic structures that combine an Abelian group under addition with a second operation (multiplication) that interacts with addition through the distributive laws.
For CS people, ring theory is directly relevant to several applications:
- Modular arithmetic: The ring \(\mathbb{Z}_n\) underlies cryptographic systems like RSA, hash functions, and pseudorandom number generators. Understanding when \(\mathbb{Z}_n\) has zero divisors (when \(n\) is composite) versus when it is a field (when \(n\) is prime) is essential for cryptographic security.
- Error-correcting codes: Cyclic redundancy checks (CRC), Reed-Solomon codes, and BCH codes are all built on polynomial rings over finite fields. The algebraic structure enables efficient encoding and decoding algorithms.
- Computer algebra systems: Software like Mathematica, Maple, and SageMath implement algorithms for polynomial factorization, GCD computation, and solving systems of polynomial equations — all of which rely on ring-theoretic foundations.
- Commutativity of addition: \(a + b = b + a\).
- Associativity of addition: \((a + b) + c = a + (b + c)\).
- Additive identity: There is an element \(0\) such that \(a + 0 = a\).
- Additive inverses: There is an element \(-a\) in \(R\) such that \(a + (-a) = 0\).
- Associativity of multiplication: \(a(bc) = (ab)c\).
- Distributive laws: \(a(b + c) = ab + ac\) and \((b + c)a = ba + ca\).
So, a ring is an Abelian group under addition, also having an associative multiplication that is left and right distributive over addition, but multiplication does not have to be commutative. Notice that an identity under multiplication is not required. If a ring has such a nonzero element, we call it a unity. Moreover, a nonzero element of commutative ring with unity need not have a multiplicative inverse (\(a^{-1}\)). When it does, it is called a unit of the ring.
Finally, we can explain what the set of all integers \(\mathbb{Z}\) is. \(\mathbb{Z}\) under ordinary addition and multiplication is a commutative ring with unity \(1\), and the only units of \(\mathbb{Z}\) are \(1\) and \(-1\).
The set \(M_2(\mathbb{Z})\) of \(n \times n\) matrices with integer entries is noncommutative ring with unity \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}. The units of \(M_2(\mathbb{Z})\) are the elements of \(A\) with \(\det A = \pm 1\).
The set \(M_n(R)\) of \(n \times n\) matrices with entries from a ring \(R\) is itself a ring under matrix addition and multiplication. When \(R\) is a ring with unity, \(M_n(R)\) is a ring with unity \(I_n\) (the \(n \times n\) identity matrix). For \(n > 1\), \(M_n(R)\) is noncommutative, even when \(R\) is commutative.
Let \[ A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}. \] Then \[ AB = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}, \quad BA = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}. \] Since \(AB \neq BA\), matrix multiplication is not commutative.
(\(\Leftarrow\)) Suppose \(\det A = \pm 1\). From linear algebra, we know that \(A^{-1}\) exists and is given by \[ A^{-1} = \frac{1}{\det A} \operatorname{adj}(A), \] where \(\operatorname{adj}(A)\) is the adjugate matrix (the transpose of the cofactor matrix). Since \(A\) has integer entries, each cofactor is an integer, so \(\operatorname{adj}(A) \in M_n(\mathbb{Z})\). Because \(\det A = \pm 1\), we have \(\frac{1}{\det A} = \pm 1 \in \mathbb{Z}\), and thus \(A^{-1} \in M_n(\mathbb{Z})\). Therefore, \(A\) is a unit in \(M_n(\mathbb{Z})\).
(\(\Rightarrow\)) Suppose \(A\) is a unit in \(M_n(\mathbb{Z})\), so there exists \(B \in M_n(\mathbb{Z})\) with \(AB = I_n\). Taking determinants of both sides: \[ \det(AB) = \det(I_n) \implies (\det A)(\det B) = 1. \] Since \(\det A\) and \(\det B\) are both integers and their product is \(1\), the only possibilities are \(\det A = \det B = 1\) or \(\det A = \det B = -1\). In either case, \(\det A = \pm 1\).
This result illustrates an important distinction: in \(M_n(\mathbb{R})\), a matrix is invertible if and only if \(\det A \neq 0\). But in \(M_n(\mathbb{Z})\), the inverse must also have integer entries, which forces the stronger condition \(\det A = \pm 1\). The group of units of \(M_n(\mathbb{Z})\) is denoted \(GL_n(\mathbb{Z})\) and is called the general linear group over \(\mathbb{Z}\).