18.06 Spring2019 pset 8 - Solutions

Problem 1

(1a) Suppose we are given three points on the $z=1$ plane: $(x_1,y_1,1)$, $(x_2,y_2,1)$,$(x_3,y_3,1)$ give a formula for the signed volume of the tetrahedron that connects the origin to these three points.

(1b) A general formula that you may have seen for generalized cones, pyramids and cones is that the volume in 3d is always one third the base times the height. I found a writeup you can quickly look at. Use this formula to get the area of a triangle given three vertices in the plane.

(1c) Generalize. Suppose you are given $n+1$ points in $R^n$. By going up one dimension, you can add the origin and get a simplex in $R^{n+1}$ along in the hyperplane with last element $1$. The generalization of half base length times height from precollege, and one third base area times height from (1b) is $\frac{1}{n+1}$ the volume of the base times the height. Find a determinantal formula for the signed volume of the tetrahedron in $R^n$ with $n+1$ given vertices (not the origin),

Solution

(1a) The signed volume is given by $$ \frac{1}{3!} \begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{vmatrix}. $$

(1b) Let $T$ be the triangle with vertices $(x_1,y_1), (x_2,y_2), (x_3,y_3)$. Then the tetrahedron with vertices $(x_1,y_1,1), (x_2,y_2,1), (x_3,y_3,1), (0,0,0)$ is a generalized cone with base $T$ shifted up to the $z = 1$ plane and height $h = 1$. If $V$ is the volume of this tetrahedron, then we have the formula $$ V = \frac{1}{3} \mathrm{Area}(T) \times h = \frac{1}{3} \mathrm{Area}(T). $$ By solving for $\mathrm{Area}(T)$, and using the formula for $V$ from the previous problem, we have $$ \mathrm{Area}(T) = \frac{1}{2} \left| ~\begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{vmatrix}~ \right|. $$ Note the absolute value, since the quantity inside is signed.

(1c) Let $T$ be the $n$-simplex with vertices given by vectors $\vec{v}_1,\ldots,\vec{v}_{n+1}$ in $R^n$. Given $\vec{x} = (x_1,\ldots,x_n) \in R^n$, let $(\vec{x},1)$ be the vector $(x_1,\ldots,x_n,1)$ in $R^{n+1}$. Then the signed volume of the $(n+1)$-simplex $S$ with vertices $(\vec{v}_1,1),\ldots,(\vec{v}_{n+1},1), \vec{0}$ is related to the signed volume of $T$ by the formula $$ \mathrm{vol}(S) = \frac{1}{n+1} \mathrm{vol}(T).$$ Then $$ \mathrm{vol}(T) = \frac{1}{n!} \begin{vmatrix} \vec{v}_1^T & 1 \\ \vdots & \vdots \\ \vec{v}_{n+1}^T & 1 \end{vmatrix}. $$

Problem 2

(2a) How many row exchanges would turn this "4-cycle" permutation matrix into I:

$$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}.$$

(2b)There are 12 edge pieces on a Rubik's cube: An edge piece always has two colored stickers on the two visible faces.
There are also 8 corner pieces The corners always have three colored stickers on the three visible faces.

Imagine numbering the edge pieces on a solved cube from 1 to 12. Propose a method to encode the position with a 12x12 permutation matrix when the puzzle has evolved. (You may also start to think, but no need to write anything down, how you can do the same with corner pieces numbered 1 to 8 using an 8x8 permutation matrix.)

(2c) A move is defined as a quarter turn of a face. (A half turn is thus two moves.) Use the result in (2a) and what you know about determinants to prove that if you start with a solved cube and apply $k$ moves to return to the solved state, then $k$ must be even.

(2d) Argue that if you plucked out two edge pieces, interchanged them, and put them back in, the cube would be unsolvable. (Hint: Argue that the determinants are the same for the 12x12 and 8x8 permutation matrices for the edges and the corners. Therefore if the edge determinant tells us that we need an odd number of moves to solve the cube, the corner would tell us we simultaneously need an even number, which is impossible.)

(2e) Does the same argument work for the eight corner pieces (you'll need an 8x8 permutation matrix)? (A corner piece has three exposed color faces.) Explain briefly?

(2f) Does the same argument work if you would interchange the two colored stickers on any one edge?

(2g) Does the same argument work if you would permute the three colored stickers on any one corner?

Solution

(2a) We show that three row exchanges is the minimal required to reach the identity. Since the determinant of this matrix is $-1$ and the identity is $1$, we require an odd number of row exchanges by parity. Note that the $1$ in each row is off-diagonal, thus each row needs to be exchanged with another. This reasoning implies that one row exchange is not sufficient to get the identity. Therefore we need at least $3$ row exchanges. If we flip rows $3$ and $4$, then rows $2$ and $3$, then rows $1$ and $2$, this gives the identity. Thus three is the minimal number of row exchanges.

(2b) The solved position of an edge can be defined in terms of its position relative to the center faces. Therefore, once the puzzle is shuffled, we may encode the position with a $12 \times 12$ permutation matrix $(P_{i,j})$ where $P_{i,j} = 1$ if edge $i$ is in the solved position of edge $j$.

(2c) Let $P$ be the permutation matrix from the previous part. A move corresponds to taking four distinct rows $i_1,i_2,i_3,i_4$ and moving row $i_1$ to row $i_2$, row $i_2$ to row $i_3$, row $i_3$ to row $i_4$, and row $i_4$ to row $i_1$. This changes the determinant by a sign. Therefore, if we start with a solved cube and apply $k$ moves to return to the solved state, then the resulting determinant is $(-1)^k = 1$. Therefore $k$ must be even.

(2d) Note that just as a move rotates $4$ edges, a move also rotates $4$ corners. Therefore, the $8\times 8$ permutation matrix corresponding to the corner positions also flips the determinant sign each move. In particular, since both corner and edge matrices start with determinant $1$ and change sign with a move, we have that the determinants of both matrices remain the same. If we remove two edge pieces, interchange them, and put them back in then this changes the sign of the determinant of the edge matrix. However, the corner matrix remains unchanged, thus the two matrices will have determinants of opposite sign. Since each move flips the sign of the determinants, we can never return to a solved position.

(2e) Yes, flipping two corner pieces flips the sign of the corner determinant but preserves the sign of the edge determinant.

(2f) No, our matrices do not keep track of orientation of an edge, only the position. So interchanging the colored stickers would not change either determinants.

In fact if you consider the 24x24 permutation matrix of the edge stickers, the argument would in fact work.

(2g) No, our matrices do not keep track of orientation of an corner, only the position. So permuting the colored stickers would not change either determinants.

Problem 3

(3) The following code generates 7 random 5×5 "anti-symmetric" (or "skew-symmetric") matrices, and prints their determinants. This is a square matrix $A$ with $A^T=−A$. Explain what you observe using the properties of determinants.

using LinearAlgebra
n = 5  # you can try changing this too if you want

for i = 1:7
    A = randn(n,n) # a random m×m matrix
    A -= A' # make it skew-symmetric by subtracting its transpose

    println(round(det(A),digits=13)) # print determinant, rounded to 13 digits
end

0.0
0.0
-0.0
-0.0
0.0
-0.0
0.0

(Note: this problem only asks you write up n=5)

Solution

If $A$ is a $5\times 5$ matrix and $c$ is a constant, then $$ \det(cA) = c^5 \det (A).$$ Therefore, if $A^T = -A$, then $$\det(A) = \det(A^T) = \det(-A) = (-1)^5 \det(A) = -\det(A)$$ which implies $\det(A) = 0$.

Problem 4

(4) Consider the image of the unit circle in the plane: $\{Ax:\|x\|=1,x\in R^2 \}$. The image is an ellipse. What is the area of the ellipse?

Solution

The linear transformation $A$ scales area by $|\det(A)|$. Since $\{x:\|x\| = 1, x \in R^2\}$ has area $\pi$, we have $\{Ax:\|x\|=1,x\in R^2\}$ has area $|\det(A)|\pi$.

Problem 5

(5) Julia has a "cumsum" operator that computes the cumulative sum.

cumsum(1:10)'

1×10 Adjoint{Int64,Array{Int64,1}}:
 1  3  6  10  15  21  28  36  45  55

An algorithm for the cumulative sum of the vector x is x[1]=y[1]
for i=2:n
y[i] = y[i-1] + x[i]
end

(5a) It is possible to write y = cumsum(x) with linear algebra: y = Lx for some unit lower triangualr matrix L. What is this L? (If you forgot what unit lower triangular means it does not matter, but it means the diagonals are all 1)

(5b) Should you use the matrix L on a computer to compute the cumsum?

(5c) (Tricky?) Somehow find a way to use the result in (5a) to compute the determinant of the matrix $$A_{ij}=\min(i,j)$$

Hint: It might help to ask what each column is a cumsum of, but it's not the only way.

n=5
A = [min(i,j) for i=1:n,j=1:n]

5×5 Array{Int64,2}:
 1  1  1  1  1
 1  2  2  2  2
 1  2  3  3  3
 1  2  3  4  4
 1  2  3  4  5

Notice (no need to write anything) that having the matrix is still useful even if you would not use it on a computer.

Solution

(5a) Yes, take $L$ to be the unit lower triangular matrix with all entries $1$ along and below the diagonal.

(5b) No, this gives $O(n^2)$ operations versus the $O(n)$ recursive algorithm.

(5c) Consider $$ L^T = \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 1 & \cdots & 1 \\ 0 & 0 & 1 & \cdots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{pmatrix}. $$ The cumulative sum of the $i$th vector is given by $(1,2,3,\ldots,i-1,i,i,\ldots,i)$. Thus, $LL^T = A$. This implies $$ \det(A) = \det(L) \det(LL^T) = 1. $$

Problem 6

(6) If $\det A = -1$, does that mean that $A$ is orthogonal? Explain why or provide a counterexample if it is false.

Solution

It is not the case that $\det A = -1$ implies $A$ is orthogonal. Consider $$A = \begin{pmatrix} 1 & 1 \\ 0 & -1 \end{pmatrix}.$$ The determinant of this matrix is $-1$, but the second column vector is not a unit vector.

Problem 7

(7) Find a 2x2 matrix A with |det(A)|<1 but some entry in $A^n$ goes to infinity as n goes to infinity. Here $A^n$ denotes multiplication of $A$ n times.

Solution

Let $$ A = \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix}.$$ Then $$ A^n = \begin{pmatrix} 2^n & 0 \\ 0 & 0 \end{pmatrix}.$$ However, $\det(A) = 0$.