Non-Commutative Gaussian Elimination Prepare a mostly-empty table,

I

I

I

I

(1, 1)

(1, 2) (2, 2)

(1, 3) (2, 3) (3, 3)

(1, n) (2, n) (3, n) (n, n)

⋮

⋯

(i, j)

... goes wild afterwards, and sends “the pivot” i to j and

Space for a σ_{i,j} ∈ S_{n} of the form

(1, 2, …, i − 2, i − 1, j, ∗, ∗, …, ∗)

So σ_{i,j} fixes 1, …, i − 1,

σ_{i,j}^{−1} “does sticker j”.

15 14 13 12 11 10 9

8 7 5 3

2

6 1 4 Can you do categories (groupoids)?

Homework Problem 2.

The Problem. Let G = ⟨g_{1}, …, g_{α}⟩ be a subgroup of S_{n}, with n = O(100). Before you die, understand G:

1. Compute |G|.

2. Given σ ∈ S_{n}, decide if σ ∈ G.

3. Write a σ ∈ G in terms of g_{1}, …, g_{α}.

4. Produce random elements of G. The Commutative Analog. Let V = span(v_{1}, …, v_{α}) be a subspace of ℝ^{n}. Before you die, understand V. Solution: Gaussian Elimination. Prepare an empty table,

1 2 3 4 n n−1 ⋯

Space for a vector u_{4} ∈ V, of the form u_{4} = (0, 0, 0, 1, ∗, …, ∗); 1 :=“the pivot”. Feed v_{1}, …, v_{α} in order. To feed a non-zero v, find its pivotal position i.

1. If box i is empty, put v there.

2. If box i is occupied, find a combination v′ of v and u_{i} that eliminates the pivot, and feed v′.

54

3

10 11 12 14 15

18

23

26 33

36

37 38 39 42

48 49 51 1

2 4 5

6 7 8

9 13 16

17

19 20 21 22 24 25

27

28 29 30 31 32 34

35

40 41 44 43

45 46 47 50

52 53

Dror Bar-Natan: Talks: Cambridge-1301:

Feed g_{1}, …, g_{α} in order. To feed a non-identity σ, find its pivotal position i and let j := σ(i).

1. If box (i, j) is empty, put σ there.

2. If box (i, j) contains σ_{i,j}, feed σ′ := σ_{i,j}^{−1}σ. The Twist. When done, for every occupied (i, j) and (k, l), feed σ_{i,j}σ_{k,l}. Repeat until the table stops changing. Claim 1. The process stops in our lifetimes, after at most O(n^{6}) operations. Call the resulting table T. Claim 2. Every σ_{i,j} in T is in G. Claim 3. Anything fed in T is now a monotone product in T: f was fed ⇒ f ∈ M_{1} :={σ_{1,j_{1}}σ_{2,j_{2}} ⋯ σ_{n,j_{n}}: ∀i, j_{i} ≥ i & σ_{i,j_{i}} ∈ T }

Non-Commutative Gaussian Elimination and Rubik’s Cube

 http://www.math.toronto.edu/~drorbn/Talks/Cambridge-1301/

Claim 4. If two monotone products are equal,

σ_{1,j_{1}} ⋯ σ_{n,j_{n}} = σ_{1,j′_{1}} ⋯ σ_{n,j′_{n}}, then all the indices that appear in them are equal, ∀i, j_{i} = j′_{i}. Claim 5. Let M_{k} denote the set of monotone products in T starting in column k: M_{k} := {σ_{k,j_{k}} ⋯ σ_{n,j_{n}}: ∀i ≥ k, j_{i} ≥ i and σ_{i,j_{i}} ∈ T } . then for every k, M_{k}M_{k} ⊂ M_{k} (and so each M_{k} is a subgroup of G). Proof. By backwards induction. Clearly M_{n}M_{n} ⊂ M_{n}. Now assume that M_{5}M_{5} ⊂ M_{5} and show that M_{4}M_{4} ⊂ M_{4}. Start with σ_{8,j}M_{4} ⊂ M_{4}:

σ_{8,j}(σ_{4,j_{4}}M_{5}) =^{1} (σ_{8,j}σ_{4,j_{4}})M_{5} ⊂^{2} M_{4}M_{5}

=^{3} ∪_{j}σ_{4,j}(M_{5}M_{5}) ⊂^{4} ∪_{j}σ_{4,j}M_{5} ⊂ M_{4}

(1: associativity, 2: thank the twist, 3: associativity and tracing i_{4}, 4: induction). Now the general case (σ_{4,j′_{4}}σ_{5,j′_{5}} ⋯)(σ_{4,j_{4}}σ_{5,j_{5}} ⋯)

falls like a chain of dominos.

Theorem. G = M_{1} and we have achieved our goals.

Can you do cosets?

Homework Problem 1.

O. Schreier C. Sims

D. Knuth

See also Permutation Group Algorithms by Á. Seress, Efficient Representation of Perm Groups by D. Knuth.

A Demo Program

In Inuit:

Enter

The Results

Enter Enter

The Generators

{43, 252, 003, 274, 489, 856, 000 \atop = \frac{8! 3^{8} 12! 2^{12}}{12}}

Rubik’s magic

Based on algorithms by

?