18.06 Spring2019 pset 8

due Wednesday 4/17 at 10:55am

Extended to Friday 4/19 at 10:55am

(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 $1/n$ the volume of the base times the height. Find a determinantal formula for the signed volume of the simplex (triangle, tetrahedron) in $R^n$ with $n+1$ given vertices (not the origin).

For clarity: the goal of this problem is to take two formulas you know and derive a new formula. You already know
(Formula 1) The nxn determinant formula for the volume of a simplex containing the origin and n other points in $R^n$ and
(Formula 2) From (1b) the formula for a generalized cone.
We are asking you to use these two formulas to find
an $n+1$ by $n+1$ determinant formula for the volume of a simplex in $R^n$ with $n+1$ given vertices in general position (no assumption of the origin).

(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?

(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 n×n matrix
    A -= A' # make it skew-symmetric by subtracting its transpose

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

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

(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?

(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.

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

(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.