UA-AUG-AUMAT229 Discovery guide

Section 6.1 Discovery guide

Let's examine the symmetries of a different kind of shape.

🔗
Figure 6.1.1. A colour-coded reference shape.

Assume each of the three endpoint vertices is one unit from the origin, so that these three vertices are placed at the heads of the standard basis vectors:

\begin{aligned} red & = e_{1} = [\begin{array}{c} 1 \\ 0 \\ 0 \end{array}], & blue & = e_{2} = [\begin{array}{c} 0 \\ 1 \\ 0 \end{array}], & yellow & = e_{3} = [\begin{array}{c} 0 \\ 0 \\ 1 \end{array}] . \end{aligned}

🔗

Let's load these vertex vectors into Sage. (This time we'll just call them

e_{1}, e_{2}, e_{3}

instead of by their colours.)


    
        
xxxxxxxxxx
 
1
e1 = vector((1, 0, 0))
2
e2 = vector((0, 1, 0))
3
e3 = vector((0, 0, 1))
4
print("e1 =", e1)
5
print()
6
print("e2 =", e2)
7
print()
8
print("e3 =", e3)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Clearly the origin vertex must always end up in the same location, so all we can do is permute the three arms of the shape. A matrix that permutes the standard basis vectors is called a permutation matrix.

🔗

Subsection Permutation matrices

🔗

Discovery 6.1. Cycles.

Here is a permutation matrix for you to load into Sage:

P = [\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}] .


    
        
xxxxxxxxxx
 
1
P = matrix( [ [0, 0, 1], [1, 0, 0], [0, 1, 0] ] )
2
print("P =")
3
print(P)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

(a)

Use the Sage cell below to multiply $P$ against each of the three standard basis vectors, and study the results. (Don't forget the print commands.)

Do you agree that $P$ is a permutation matrix?

🔗

(b)

Study your results of Task a even closer. What is the pattern between how the standard basis vectors were permuted and the $P$ matrix itself? (There are two different ways you could answer this ….)

🔗

(c)

The permutation represented by matrix $P$ is called a cycle — do you see why?

(More precisely, this permutation is called a $3$ -cycle.)

🔗

(d)

Use the Sage cell below to evaluate $P^{2},$ then use the pattern you identified in Task b to determine how that result matrix will permute the standard basis vectors without doing any matrix-times-vector calculations. What do you notice?

🔗

(e)

Modify your input in the Sage cell above to calculate $P^{3} .$ Surprised? What does this say about the order of $P ?$

🔗

(f)

If we are to consider $P$ as an element in a multiplicative group, it had better be invertible. Is it?

Hint.

You don't need to perform any Sage calculations for this, though you may if you wish: the Sage syntax is P.inverse(). Just consider the result of Task e.

🔗

(g)

Geometrically, do you think any other cycles of our shape in Figure 6.1.1 are possible?

🔗

Discovery 6.2. Transpositions.

Here is another permutation matrix for you to load into Sage and analyze:

T = [\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}] .


    
        
xxxxxxxxxx
 
1
T = matrix( [ [0, 1, 0], [1, 0, 0], [0, 0, 1] ] )
2
print("T =")
3
print(T)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

(a)

Either using the pattern you identified in Task 6.1.b or by inserting some matrix-times-vector calculations into the Sage cell above, determine how $T$ acts on our shape from Figure 6.1.1.

🔗

(b)

The permutation represented by $T$ is called a transposition — do you see why?

🔗

(c)

What do you think the order of $T$ is?

🔗

(d)

What other transpositions of our shape are possible, and what are their corresponding matrices?

🔗

(e)

Permutation $P$ from Discovery 6.1 can be decomposed as a product of two transpositions. Experiment in the Sage cell below to determine how.

🔗

The group of permutations of the three standard basis vectors is too small to expose all the patterns we would like to see, but it is not possible to insert a four-dimensional picture here. So we will just have to proceed by algebra alone.

🔗

Discovery 6.3.

🔗

(a)

Create a $4 \times 4$ permutation matrix $Q$ that has action

\begin{aligned} e_{1} & \mapsto e_{2}, \\ e_{2} & \mapsto e_{3}, \\ e_{3} & \mapsto e_{1}, \\ e_{4} & \mapsto e_{4} . \end{aligned}

For convenience, $Q$ has initially been set up in the Sage cell below to the zero matrix. Edit it by entering ones in the right places to create the action above.


    
        
xxxxxxxxxx
 
1
Q = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
print("Q =")
3
print(Q)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

(b)

Is $Q$ a cycle? If so, what kind of cycle? (i.e. a $2$ -cycle? a $3$ -cycle? a $4$ -cycle? a $24$ -cycle? etc.)

🔗

Discovery 6.4.

🔗

(a)

Create a $4 \times 4$ permutation matrix $R$ that is a $4$ -cycle. Again, for convenience, $R$ has initially been set up in the Sage cell below to the zero matrix. Edit it by entering ones in the right places to create the action above.


    
        
xxxxxxxxxx
 
1
R = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
print("R =")
3
print(R)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

(b)

Is a group of $4 \times 4$ permutations Abelian? Calculate both $Q R$ and $R Q$ in the Sage cell below as a test.

🔗

Discovery 6.5.

🔗

(a)

Create a $4 \times 4$ permutation matrix $S$ that is not any kind of cycle.


    
        
xxxxxxxxxx
 
1
S = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
print("S =")
3
print(S)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

(b)

What is the action of your permutation on the four standard basis vectors? (Express your action in $e_{i} \mapsto e_{j}$ formulas, as in the description of $Q$ in Discovery 6.3.)

🔗

(c)

I'm going to guess that your non-cycle $S$ is actually a product of two simpler permutation matrices. Am I right? I think I am, so fill in two “factors” $S_{1}, S_{2}$ that make up $S$ below.


    
        
xxxxxxxxxx
 
1
S1 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
S2 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
3
print("S =")
4
print(S)
5
print("S2 * S1 =")
6
print(S2 * S1)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

Note: Remember that transformations are applied in right-to-left order, which is why they are multiplied in the order $S_{2} S_{1}$ in the Sage cell.

🔗

(d)

Wait, check this out:


    
        
xxxxxxxxxx
 
1
print("S2 * S1 =")
2
print(S2 * S1)
3
print("S1 * S2 =")
4
print(S1 * S2)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

You should have found in Task 6.4.b that this group of $4 \times 4$ permutations is non-Abelian. Give a geometric reason (that is, in terms of transformations of standard basis vectors) why your particular two permutation matrices $S_{1}, S_{2}$ commute with each other.

🔗

(e)

What kind of permutations are $S_{1}, S_{2} ?$ What are their orders? Based on the fact that $S_{1}, S_{2}$ commute, you should be able to determine the order of $S = S_{1} S_{2}$ from the orders of $S_{1}$ and $S_{2} .$ Use the Sage cell below to check your answer by increasing the exponent until you know the order.


    
        
xxxxxxxxxx
 
1
print("S^2")

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Discovery 6.6.

What is the order of the group of $4 \times 4$ permutation matrices?

Hint.

Don't try to create them all. If at least one person in your group has taken AUMAT 250, that person should know how to answer this question.

🔗

Subsection Decompositions

🔗

Discovery 6.7.

🔗

(a)

Create a $4 \times 4$ $4$ -cycle matrix $U$ that has the effect

e_{1} \mapsto e_{2} \mapsto e_{3} \mapsto e_{4}

on the standard basis vectors. (Note: Since this is a cycle, we assume $e_{4}$ wraps back around to $e_{1} .$ )


    
        
xxxxxxxxxx
 
1
U = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
print("U =")
3
print(U)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

(b)

Attempt to decompose $U$ into a product of three transposition matrices. As you try to do this, keep in mind the following.

Compositions of transformations are applied in right-to-left order.
Permutation matrices further to the left don't “know” that matrices to the right have already mixed things up.

As usual, $U_{1}, U_{2}, U_{3}$ have been initialized to zero matrices for you in the Sage cell below. You are aiming for

U = U_{3} U_{2} U_{1}

to be true, which is what the formula in the final print command is checking — if

U = U_{3} U_{2} U_{1}

then

U^{- 1} (U_{3} U_{2} U_{1})

should be equal to the identity matrix.


    
        
xxxxxxxxxx
 
1
U1 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
U2 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
3
U3 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
4
print(U.inverse() * (U3 * U2 * U1))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Discovery 6.8.

Figure out the pattern of what you did for $U$ in Discovery 6.7, then repeat for $4 \times 4$ $4$ -cycle matrix $W$ that has the effect

e_{1} \mapsto e_{3} \mapsto e_{2} \mapsto e_{4}

on the standard basis vectors.


    
        
xxxxxxxxxx
 
1
W = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
W1 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
3
W2 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
4
W3 = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
5
print("W =")
6
print(W)
7
print("W.inverse * (W3 * W2 * W1) =")
8
print(W.inverse() * (W3 * W2 * W1))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Conjecture 6.1.2.

Every cycle can be decomposed into a product of transpositions.

🔗

Discovery 6.9.

What do you think: is Conjecture 6.1.2 true or false?

🔗

Subsection Sign of a permutation matrix

🔗

Hopefully by now you've figured out that a permutation matrix is really just a permutation of the columns of the identity matrix. (Or maybe you've been thinking of it as a permutation of the rows of the identity matrix, which is fine.)

🔗

Discovery 6.10.

🔗

(a)

What is the determinant of the identity matrix?

🔗

(b)

What does linear algebra say about the effect on the determinant if two columns (or two rows) are swapped?

🔗

Conjecture 6.1.3.

Every permutation matrix has determinant .

🔗

Discovery 6.11.

🔗

(a)

Complete the statement of Conjecture 6.1.3.

🔗

(b)

Test your version of Conjecture 6.1.3 below. (First, evaluate the Sage cell as-is, then modify it to swap $P$ out for other permutation matrices we've encountered today: $T, Q, R, S, \dots,$ and re-evaluate.)


    
        
xxxxxxxxxx
 
1
print(P.determinant())

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Definition 6.1.4. Sign of a permutation.

The determinant of the corresponding permutation matrix is called the sign of the permutation.

🔗

Does Definition 6.1.4 make sense in light of how you completed the statement of Conjecture 6.1.2?

🔗

Discovery 6.12.

🔗

(a)

What is the sign of a transposition? Is it always the same?

🔗

(b)

Test out your guess from Task a on some transpositions below:

Make $V$ a transposition by adding ones in the appropriate places, then evaluate to compute its determinant.
Edit $V$ to a different transposition, evaluate again.
Repeat until you're satsified that you've guessed correctly in Task a.


    
        
xxxxxxxxxx
 
1
V = matrix( [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] )
2
print("V =")
3
print(V)
4
print("det V =", V.determinant())

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Discovery 6.13.

Consider the collection of all permutation matrices of a particular size that have even sign (i.e. sign $1$ ). Use the Subgroup Test (Version 1 or Version 2, your choice) and properties of the determinant to verify that the even permutations form a subgroup of the permutations.

🔗

Subsection Disjoint cycles

🔗

Definition 6.1.5. Disjoint cycles.

A collection of cycles is called disjoint in the following situation: whenever one of the cycles in the collection “acts” non-trivially on one of the standard basis vectors, then each of the other cycles must act trivially on that vector.

🔗

Once again we'll have to move up in size to see more of the patterns of permutations.

🔗

Discovery 6.14.

Here is an 8×8 permutation matrix.

X = [\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{matrix}]

By now you should be pretty good at reading the columns (or rows, if you prefer) of permutation matrices to figure out their action, without actually multiplying them against standard basis vectors.

Since $X$ so big, let's get it into Sage in its own cell.


    
        
xxxxxxxxxx
 
1
X = matrix([ [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0 ],  [ 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0, 0 ],  [ 0, 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0, 0 ] ])
2
print("X =")
3
print(X)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

See if you can decompose $X$ as a product of two disjoint cycles. Once you're done, try to describe the pattern of how you did it. (Once again, you are looking for the print(X.inverse() * (X2 * X1)) statement to return the identity matrix.)


    
        
xxxxxxxxxx
 
1
X1 = matrix([ [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ],  [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ],  [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ] ])
2
X2 = matrix([ [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ],  [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ],  [ 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ] ])
3
print("X1 =")
4
print(X1)
5
print("X2 =")
6
print(X2)
7
print("X.inverse * (X2 * X1) =")
8
print(X.inverse() * (X2 * X1))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Conjecture 6.1.6.

Every permutation can be decomposed into a product of disjoint cycles.

🔗

Discovery 6.15.

What do you think: is Conjecture 6.1.6 true or false?

🔗

Discovery 6.16.

Wait, the decomposition of $X$ in Discovery 6.14 seems similar to an earlier activity. Let's try the other order again … (Evaluate the Sage cell below. Note that in Discovery 6.14 we were trying to get $X = X_{2} X_{1},$ but below we are testing whether $X = X_{1} X_{2}$ as well.)


    
        
xxxxxxxxxx
 
1
print(X.inverse() * (X1 * X2))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

Why do you think this happened? Will this happen in general for products of disjoint cycles?

🔗

Subsection Signs of decompositions

🔗

Let's put a few things together now.

We think a transposition always has odd sign, i.e. a sign of $- 1$ (Discovery 6.12).
We think every cycle can be decomposed into transpositions (Conjecture 6.1.2).
We think every permutation can be decomposed into a product of (disjoint) cycles (Conjecture 6.1.6).

🔗

Discovery 6.17.

Combining Statement b and Statement c, every permutation should decompose into a product of transpositions. Combine this with Statement a to make a conjecture about the nature of a permutation's decomposition into transpositions based on the sign of the permutation.