Reviewing Groups, Rings, Fields, Modules, and Vector Spaces Through an Elementary School Math Problem
Haifei0. Introduction to the Problem
With this single college entrance examination mock question, we can review concepts from abstract algebra such as groups, rings, fields, modules, and vector spaces. The problem is shown below:
A college entrance examination mock question from somewhere; in fact, you can figure it out with a little trial and error—it is not difficult.
Simply put, it is a matter of “pulling one hair and moving the surrounding area.” Changing one cell also rotates the surrounding cells. I believe many people have played this puzzle game. Even elementary school students can understand this game.
For this puzzle, we not only want to study the structure of its solutions (for example, when solutions exist, when they do not, and the relationships between solutions), but also find a general algorithm for solving it. These will be discussed one by one below.
Prerequisites for reading this article: familiarity with the basic definitions of groups, rings, fields, and vector spaces; familiarity with the definitions of normal subgroups and quotient groups, as well as their related theorems.
1. Groups
1.1 A Single Switch: A Cyclic Group of Order Two
Let us first briefly analyze this problem: each switch has only two states, so these two states clearly form a cyclic group of order two, namely \(\mathbb{Z}_2=\mathbb{Z}/2\mathbb{Z}\) .
1.2 All Switches: A Direct Sum of Cyclic Groups of Order Two
Can all states of the nine cells as a whole also form a group? The answer is yes.
It is easy to prove that the direct sum of groups forms a group.
All states of the switch array as a whole are \(\mathbb{Z}_2^9=(\mathbb{Z}/2\mathbb{Z})^9\) , that is, the direct sum of the group \(\mathbb{Z}_2\) with itself. Therefore, all states of the nine cells as a whole do indeed form a group. The additive identity of this group is the state in which all cells are zero.
Moreover, this group is also an Abelian group (that is, addition satisfies commutativity); the proof is left to the reader.
1.3 The Group Formed by All Operations
Having studied the states, let us now study the possible operations.
Possible operations are mappings from \(\mathbb{Z}_2^9\) to \(\mathbb{Z}_2^9\) that satisfy the constraints given in the problem (that is, changing the state of one cell also changes the states of the four surrounding cells). Possible operations also include arbitrary superpositions of these operations.
All possible operations can also form a group. This group is generated by the nine basic operations (pressing each of the nine different cells, respectively). Let us denote this group by \(M\) . In addition, let the group formed by all states be \(S\) . We may refer to \(M\) simply as the “operation group” and \(S\) simply as the “state group.”
\(M \)’s additive identity is “performing no operation.”
Moreover, this group is also Abelian; the proof is left to the reader.
1.4 The “Operation Group” Is a Subgroup of the “State Group”
Let \(s_0 \in S\) be the initial state of the switch array, and let \(m_k \in M\) be the (sequence of) operations performed on the switch array.
Clearly, \(m_k(s_0)=s_k\in S\) . Therefore, \(M\) is isomorphic to a subgroup of \(S\) . Or equivalently, \(M\) is a subgroup of \(S\) .
1.5 The “Operation Group” Is a Normal Subgroup of the “State Group”
Since \(S\) and \(M\) are both Abelian groups, \(M\) is not only a subgroup of \(S\) , but also a normal subgroup of \(S\) .
1.6 Quotient Groups
Since there is a normal subgroup, there is a quotient group \(S/M\) .
What does the quotient group represent in this problem? Let me explain.
Suppose \(S\) can be divided into \(n\) subsets \(\{S_k\}\,(k=1,\cdots,n)\) (in other words, \(\{S_k\}\) is a partition of \(S\) ),
such that elements within \(S_k\) can be transformed into one another through operations (that is, \(m\in M\)), while elements of \(S_k\) and elements of \(S_l\,(k\neq l)\) cannot be transformed into one another through operations (that is, \(m\in M\)),
then such \(\{S_k\}\) is a quotient group of \(S\) (by \(M\) ).
Of course, the conditions above are not necessary and sufficient conditions for a quotient group, but rather necessary conditions.
That is, an element of the quotient group is a set consisting of all states obtainable from a particular state in the original group through possible operations (which belong to the normal subgroup).
The preceding statement is rather convoluted. In short, the elements of a quotient group are sets; or, put differently, a quotient group is a set of sets.
As an analogy, if the elements of a group are eggs, then the elements of a quotient group are baskets holding eggs.
If the quotient group has only one element {e}, then all states can be obtained starting from a certain state. In this case, \(M\) is isomorphic to \(S\) .
The purpose of saying so much about quotient groups is to reveal an important structure of this type of puzzle: the set of solvable initial states and its cosets have the same number of elements. In other words,
The number of solvable initial states is 1/n of the total number of states.
There are n distinct types of initial states that cannot be transformed into one another.
As for what this n is, different switch arrays and their rules must be studied and solved on a case-by-case basis.
2. Vector Spaces
Everything discussed in the first section concerned groups. Indeed, groups alone allow us to characterize the entire algebraic structure of this puzzle. But if our goal is to solve it, we may need a more powerful tool. Is this tool a vector space?
As we all know, a vector space consists of an Abelian group \(V\) together with a field \(F\) , equipped with scalar multiplication \(F \cdot V\rightarrow V\).
The field \(F\) allows us to perform “more quantitative” operations, so a vector space is quite likely the tool we need to solve the problem!
The following figure shows a solution provided by a high school teacher:
It does indeed appear to use a vector space. After all, it uses matrices.
The method for finding the inverse matrix is the “elementary method”: simultaneously perform elementary transformations on the original matrix and the identity matrix until the original matrix becomes the identity matrix; at that point, the original identity matrix has become the inverse matrix.
In fact, the group of this vector space is \(\mathbb{Z}_2=\mathbb{Z}/2\mathbb{Z}\) , and its field is also \(\mathbb{Z}_2=\mathbb{Z}/2\mathbb{Z}\).
Now modify the problem: change each switch from having two states to having three states ( \(0,1,2\) ), and require that each press can only cycle through the states ( \(0\rightarrow1\rightarrow2\rightarrow0\) ). A vector space can still be constructed in this case, and both the group and the field of this vector space are \(\mathbb{Z}_3=\mathbb{Z}/3\mathbb{Z}\) (note that in \(\mathbb{Z}_3\), the multiplicative inverse of 2 is itself, namely 2 * 2 = 1 mod 3).
But are vector spaces really the ultimate answer for this type of puzzle? In fact, no—let us continue.
3. Modules
Now modify the problem by changing each switch from having only two states to having four states ( \(0,1,2,3\) ), while requiring that each press can only cycle through the states ( \(0\rightarrow1\rightarrow2\rightarrow3\rightarrow0\) ).
At this point, all states of a single switch form the cyclic group of order four \(\mathbb{Z_4}\). The states of all switches together form \(\mathbb{Z}_4^9\) , denoted by \(S\) .
Likewise, the set of all operations forms a subgroup \(M\) of \(S\) .
But! Here comes the problem: \(\mathbb{Z}_4\) is not a field (because the element 2 has no multiplicative inverse), so we cannot construct a beautiful vector space, since a vector space requires a field.
Fortunately, we have a savior: the elder sister of vector spaces, called a module (Module).
Compared with the definition of a vector space, the definition of a module simply replaces the field with a ring.
That is, a module includes an Abelian group and a ring, as well as scalar multiplication between the group and the ring.
Excellent! Although \(\mathbb{Z_4}\) is not a field, it is a ring.
Moreover, compared with vector spaces, modules can indeed better describe quantitative relationships on discrete groups. You can press a switch once, twice, or n times, but you cannot press it 1.5 times!
That is, a ring is sufficient; there is no need for division over a field to produce fractions (besides, fractions are nonsense in this problem—you cannot press a switch a fractional number of times).
At this point, we have obtained both the algebraic structure needed to describe the entire puzzle and the algebraic structure needed to solve it quantitatively. They are groups and modules, respectively.
In addition, the relationship in which a normal subgroup equals the group can be expressed through “linear independence” over a module. That is, if the elements in the module corresponding to each switch are “linearly independent” of one another, then all states can be obtained starting from the same state. This relationship is also equivalent to the matrix determinant being nonzero (it really is quite like linear algebra!).
4. Summary
For puzzles (brain teasers) of the “pulling one hair and moving the surrounding area” type, we use group theory to study the properties of the solutions to such puzzles, and module theory to obtain a general solution method.
5. Epilogue
Then, for the more general group \(\mathbb{Z}_n^m\), what normal subgroups and quotient groups does it have?
The structure of the quotient group can tell us, for the puzzles above, which initial states are solvable and how many distinct groups of initial states exist such that states in different groups cannot be transformed into one another. I think this question should be quite interesting.
If any readers happen to have studied the normal subgroups of \(\mathbb{Z}_n^m\), please join the discussion in the comments; the author would be very grateful!