Pset 7 Due April 13

(1) GS p.216 17. If $P^2=P$ show that $(I-P)^2=I-P$. When $P$ projects onto the column space of $A$$, what does $I-P$ project onto?

A) $(I-P)^2 = I - 2P + P^2 = I - 2P + P = I - P$. So $I-P$ is another projection matrix.

If $P$ is a projection onto $\text{col}(A)$, $P = U_1U_1^T$ and since $U = \begin{bmatrix}U_1 & | & U_2\end{bmatrix}$ and $UU^T = I$ , we have $U_1U_1^T + U_2U_2^T = I$ so $I-P = U_2U_2^T$, a projection onto $\text{null}(A^T)$.

(2) GS p.217 22. Knowing that the inverse of a symmetric matrix is symmetric, prove that projection matrices are symmetric by showing that $P=A(A^TA)^{-1}A^T$ is symmetric. Do this by showing that $P^T=P$.

A) Let $B = A^TA$, a symmetric matrix. Then, $P^T = (A(A^TA)^{-1}A^T)^T = (A^T)^T (B^{-1})^T A^T = AB^{-1}A^T = P$ since $B^{-1}$ is symmetric(given)

(3) GS p. 214 1. Project the vector $b$ onto the line through $a$. Check that $e$ is perpendicular to $a$.

(a) b=[1;2;2] and a=[1;1;1] (semicolons indicate column vectors)
(b) b=[1;3;1] and a=[-1;-3;-1]

A) (a) $a(a^Ta)^{-1}a^Tb = a*(3)^{-1}a^Tb = a*\frac{1}{3}*5= \begin{pmatrix}5/3\\5/3\\5/3\end{pmatrix}$. $e = \begin{pmatrix}2/3\\-1/3\\-1/3\end{pmatrix}, e^Ta = 0$.

(b) $a(a^Ta)^{-1}a^Tb = a*11^{-1}*(-11) = -a = \begin{pmatrix}1\\3\\1\end{pmatrix}. e = 0$ and $e^Ta = 0$.

(4) GS p. 254 3. True or False, with a reason if true or a counterexample if false
(Notation: $|A|=\det(A)$.)
(a) The determinant of $I+A$ is $1+\det A$.
(b) The determinant of $ABC$ is $|A||B||C|$.
(c) The determinant of $4A$ is $4 |A|$.
(d) The determinant of $AB-BA$ is always zero. (Maybe try A=[0 0;0 1])

A) (a) False. counterexample $A = \begin{pmatrix}1&1\\0&1\end{pmatrix}$

(b) True. $|ABC| = |AB||C| = |A| |B| |C|$

(c) False. counterexample $I_2$.

(d) False. counterexample $A = \begin{pmatrix}0&0\\0&1\end{pmatrix}, B = \begin{pmatrix}0&1\\1&1\end{pmatrix}$

(5) GS p 255 12. The inverse of a 2x2 matrix seems to have determinant = 1: $$ \det A^{-1} = \det \frac{1}{ad-bc} \left[ \begin{array}{rr} d & -b \\ -c & a \end{array} \right]= \frac{ad-bc}{ad-bc}=1.$$ What is wrong with this calculation? What is the correct $\det A^{-1}$?

A) determinant of $kA$ is $k^n\det(A)$, not $k\det(A)$. So the right calculation is

$$\det\frac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix} = \frac{1}{ad-bc}^2\det\begin{bmatrix}d&-b\\-c&a\end{bmatrix} = \frac{1}{ad-bc}$$

(6) A Hadamard matrix H is a matrix with entries ±1 and orthogonal columns. What is the determinant of H as a function of n? (Hadamard matrices are conjectured to exist for every n that is a multiple of 4, but nobody knows if there is such a matrix even for n=668) (See mathoverflow for example.) If you stumble on a Hadamard matrix of size 668 please let us know. (Extremely unlikely don't waste much time looking.)

A) Orthogonal columns mean $H^TH = cI$ and since $c$ is the squared norm of each columns, $c = n$. So we have $\det(H)^2 = n^n, \det(H) = \pm\sqrt{n^n}$. Since for any Hadamard matrix $H_1$, we can switch columns to obtain another Hadamard matrix $H_2$ and $\det(H_1) = -\det(H_2)$, we have both cases. $\det(H) = \pm\sqrt{n^n}$

(7a) 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}.$$

A) Three. 4<->3, 3<->2, 2<->1

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

A) Do similarly as we did in 15 puzzle. Create 12 by 12 matrix with rows being current position of the edge pieces and columns being initial(solved state) position. Start with $I_{12}$.

(7c) A move is defined as a quarter turn of a face. (A half turn is thus two moves.) Use the result in (7a) 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.

A) Any move exchanges four rows, and fixes other eight rows. Pretend a single move is a multiplication by a permutation matrix. Then the permutation matrix has 8 ones on the diagonal and other 4 ones permuted as in 7(a). Any permutation matrix corresponding to a move will have determinant -1 because it needs 3 row exchanges to reach identity. So from solved state, we cannot reach solved state again with odd numbers of multiplications of permutation matrices.

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

A) We use similar 8 by 8 matrix from the corner pieces, note that a move will also permute four rows of them, and those four rows are will need 3 row exchanges to return back to identity matrix, so a move will multiply another determinant -1 permutation matrix on the left of corner piece state matrix. Without exchanging, the determinant of two state matrices are the same. If two edge pieces are exchanged in one point, the determinant of edge piece state is multiplied by -1 and the determinant of corner piece state stays the same. So from there, any move will simultaneously multiply -1 on each states, and they can never be 1 together, so we can solve the cube.

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

A) Yes. Same but -1 is multiplied on corner piece state matrix.

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

A) No. Because we never had any discussion about the orientation of the edge pieces. The same argument is not enough to say the cube becomes unsolvable, since exchanging the sticker will keep two state matrices the same. \

However, if one uses 24 by 24 matrix to mark the positions of the stickers, the same argument works. A move becomes multiplying permutation matrix of determinant 1 (so it stays determinant 1) but when we switch the stickers, we have -1 determinant state matrix so it can't be solvable

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

A) No as above, and even if one uses 24 by 24 matrix we can't prove it because switching the stickers will not change the state matrix determinant.(Two row exchanges)

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

A) No. counterexample $\begin{pmatrix}1&2\\1&1\end{pmatrix}$