11-1100/MATLAB Code for Non-Commutative Gaussian Elimination

I wrote a MATLAB script to carry out the non-commutative Gaussian elimination algorithm. Specifically, I have chosen to use the problem of the 2x2x2 pocket cube; however, this algorithm may be easily adapted for finding the solution to other combinatorial puzzles. The structure of the script is very similar to Dror's code. I call the "Feed" script for each generator of the puzzle, but the built in recursion takes care of finding an empty spot in the table, as well as all the messiness of feeding all products of everything in the table.

My solution is slightly different, however, in that I carry out group operations using matrix representations of the generators. I picked a representation of the group in which every matrix was comprised of only 1's and 0's. This is useful, because it easily allows me to compute products, inverses, and find pivot points. The representation of which I write can be constructed by considering the action of $S_{n}$ on an n-dimensional vector space. As an example, consider the permutation $g=(123)\in S_{3}$. This permutation takes 1 -> 2, 2 -> 3, and 3 -> 1; thus, the matrix representation of this operation is:

$g=\left({\begin{array}{ccc}0&0&1\\1&0&0\\0&1&0\end{array}}\right)$

From a computational standpoint this is kind of a bad idea, but I figured it was something different and no one else was likely to try this.

I split the program into 3 parts: BG2.m is a short script which

</math>