Non-commutative gaussian elimination (from the course “groups, rings and fields” - taught by Prof. Dror Bar-Natan)

NCGE Rubik's Cube Numbering (1-54)

This 2D net shows how the 54 stickers are mapped to natural numbers.
Notice how the Front (White) face contains stickers 13-15, 22-24, and 31-33.

Context

Non-commutative gaussian elimination (which I will refer to as NCGE from here on out) was taught to us in the beginning of “groups, rings and fields” (aka MAT347). We were introduced to the problem like so: consider a standard 3 x 3 x 3 Rubik’s Cube. Label each sticker on the cube by the natural numbers from 1 to 54. Now, consider a group $G = \langle g_1, g_2, g_3, g_4, g_5, g_6 \rangle$, where each of the six generators constitutes one of the six 90 degree turns that are on unique axes. As we can express each $g_i$ as a cycle of natural numbers (for example, turning the white face 90 degrees clockwise would be expressed as (13, 15, 33, 31)(14, 24, 32, 22)(7, 16, 39, 30)(8, 25, 38, 21)(9, 34, 37, 12)), each $g_i$ is a member of the permutation group $S_54$.

Having defined a subgroup of $S_{54}$ with an unknown size, an obvious question is: if we pick a random element of $S_{54}$, how can we find out whether it is an element of $G$ or not? In other words, which permutations of the 54 stickers are valid Rubik’s Cube combinations that can be achieved by using the six unique-axis turns, and which can only be achieved by peeling off the stickers and placing them where we want them to go?

In comes NCGE (how the method works)

Prepare a lower-half-left triangular table with 54 columns and 54 rows. Naturally, the left most column will be the tallest (54 boxes), while the right most column has just one box. Label each box $(i, j)$, with $i$ being the column number, and $j$ being the row number. Based on how we define the table, $i \leq j$.

Start by feeding in each of the generator elements into the table. This “feeding” process for non-identity elements works as follows:

find the pivotal position $i$ in that generator element $g_k$ (this is the first number from 1 to 54 that is mapped to a number that is not itself in the permutation; the reason we know it must be mapped to a number ahead of it is: if $i > j$, then $g_k(i) = j$ and $g_k(j)=j$, contradicting it being a permutation (bijection))
if box $(i, j)$ is empty, place $g_k$ in that box. If not, go to step 3.
go back to step 1 and feed $g’ = \sigma g_k$, where $\sigma$ is the element already in $(i, j)$ (you do this over and over until you either place the new permutation in a box of reach the identity).
professor Bar-Natan called this “the twist”: Having done all the generators, for every occupied $(i, j)$ and $(r, s)$, go back to step 1 and feed in $\sigma_{i, j} \sigma_{r, s}$ (these of course refer to the permutation stored in those boxes after step 3). Repeat this process until the table stops changing.

In class, we covered several interesting claims about this process and the resulting table. I want to focus on the claim I found the most interesting:

Claim: Feed any element of $S_{54}$ into the table. If it eventually becomes the identity permutation, it is a valid Rubik’s Cube permutation. If it reaches an empty box, it is not a valid Rubik’s Cube permutation.

Proof

1. If feeding ends at the identity, then $\sigma \in G$.

The algorithm produces a sequence
$\sigma = \tau_1 \tau_2 \cdots \tau_k \cdot (\text{identity})$ where each $\tau_m$ is the element taken from a box $(i_m, j_m)$ during the reduction.
By construction, every box in $T$ is obtained from the generators $g_1,\dots,g_6$ using only multiplication and inversion (the “feeding” and “twist” steps). Hence every $\tau_m \in G$.
Therefore $\sigma = \tau_1 \tau_2 \cdots \tau_k \in G$.

2. If feeding reaches an empty box, then $\sigma \notin G$.

Suppose for contradiction that $\sigma \in G$.
Because the table $T$ is closed under the operations that built it (proved during lecture - I will add a short proof of this later), every element of $G$ can be written as a monotone product.
$\sigma = \sigma_{1,j_1}\, \sigma_{2,j_2} \cdots \sigma_{54,j_{54}}$ where each $\sigma_{i,j_i}$ belongs to box $(i,j_i)$ of $T$ (or is the identity if the box is empty).
Now feed this product into the table. The algorithm will read the factors from left to right, reducing the pivot at each step. If some box $(i,j_i)$ were empty, the reduction would stop before consuming all factors, contradicting the assumption that $\sigma$ reduces completely to the identity (since $\sigma \in G$ must reduce to identity by the first part of the claim). Hence all needed boxes must be non‑empty. Therefore, if the feeding ever encounters an empty box, $\sigma$ cannot be in $G$.

Thus, the feeding test is both necessary and sufficient for membership in the Rubik’s cube group $G$.

Mini-example with $S_4$ instead of $S_{54}$

NCGE for S₄ - Step-by-Step

Taking it further (my personal additions/interests)

The order of the group $G$

I will start with something fairly simple, that being finding how many elements the group $G = \langle g_1, g_2, g_3, g_4, g_5, g_6 \rangle$ has. Although I did not state this as an objective in the initial sections, I touched upon it being an unknown. Conveniently, the NCGE process gives us a simple way of finding the order of $G$. If we add up the number of filled boxes in each column, and multiply the totals for each column together, we get $|G|$.

Well, why is this the case? The answer lies in a concept that could be called the “stabilizer chain”, although it really relies on the more commonly known “orbit-stabilizer theorem”.

Let $G_1 = G$ be the entire group. Now, define $G_2$ as the subgroup of $G_1$ containing all permutations that fix the number 1 in its place (in other words, $\sigma(1) = 1$). Next, define $G_3$ as the subgroup of $G_2$ that also fixes 2 (a quick justification for these being subgroups - they are trivially subsets, and satisfy the subgroup tests since composition and inverse will both fix the same elements).

Continuing this process, let $G_i$ be the subgroup of elements in $G$ that fix all numbers from 1 to $i - 1$. This creates a nested chain of subgroups until we eventually reach the identity element (or trivial subgroup that fixes every number from 1 to 54):

\[G = G_1 \geq G_2 \geq G_3 \geq \dots \geq G_{54} = \{e\}\]

Having established this, we can now use the orbit-stabilizer theorem. For the purpose of recall (partially so I get this right as well haha), if a group $H$ acts on a set, then for any element $x$ in that set:

\[|H| = |\text{Orbit}_H(x)| \times |\text{Stabilizer}_H(x)|\]

Applying this to the subgroup $G_i$ acting on the number $i$:

The stabilizer of $i$ in $G_i$ is the set of elements that fix $1, \dots, i - 1$ and also fix $i$. This is the same as the next subgroup in the chain defined above: $G_{i + 1}$.
The orbit of $i$ under $G_i$, which we can call $\text{Orb}_{G_i}(i)$, is the set of all possible destinations $j$ that $i$ can be sent to by elements of $G_i$.

Substituting this into the orbit-stabilize equation gives us the following recursive formula:

\[|G_i| = |\text{Orb}_{G_i}(i)| \times |G_{i + 1}|\]

Now, we connect this to the NCGE table. To do this, we must ask the question: what is column $i$ in the table? By the NCGE rules established earlier, any permutation placed in column $i$ has $i$ as its pivot position, meaning it fixes every number strictly less than $i$. Therefore, every element in column $i$ belongs to $G_i$. In addition to this, we may say that a box $(i, j)$ is filled iff there is some permutation in $G_i$ that maps $i$ to $j$. Hence, the number of occupied boxes in column $i$ is exactly the size of the orbit $|\text{Orb}_{G_i}(i)|$.

Using all of this, we may do the final computation as follows:

\[\begin{flalign*} |G_1| &= |\text{Orb}_{G_1}(1)| \times |G_2|&&\\ |G_1| &= |\text{Orb}_{G_1}(1)| \times |\text{Orb}_{G_2}(2)| \times |G_3|&&\\ \dots&&\\ |G_1| &= |\text{Orb}_{G_1}(1)| \times |\text{Orb}_{G_2}(2)| \times \dots \times |\text{Orb}_{G_{54}}(54)| \times |\{e\}|&&\\ \end{flalign*}\]

Since the size of each orbit is the number of filled boxes in that column, $|{e}|$ is 1, and $G = G_1$, we get that:

\[|G| = \prod_{i=1}^{54} \text{Number of occupied boxes in column i}\]

and we are done.

back