Skip to content

6.2-exam3-2012-b

Quiz 3, 2012 · Section 6.2: Diagonalizing a Matrix Source: exam3_2.pdf, pp. 41-42

Problem

4. (26 pts.)

a) (5 pts.) \(P\) is a three by three permutation matrix. List all the possible values of a singular value. (Explain briefly.)

b) (9 pts.) \(P\) is a three by three permutation matrix. List all the possible values of an eigenvalue. (Explain briefly.)

c) (12 pts.) There are six \(3 \times 3\) permutation matrices. Which are similar to each other? (Explain briefly.)

Solution a) A permutation matrix satisfies \(P^TP = I\), which has all ones as eigenvalues, so all the singular values of \(P\) are \(\sqrt{1} = 1\). b) The possible eigenvalues are the square roots of 1 and the cubed roots of 1 (this is shown while solving part (c)): \(1\), \(-1\), \(\frac{1}{2} \pm i\frac{\sqrt{3}}{2}\). c) Let's list the six matrices. There is the identity matrix: \[ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}. \] There are the three transposition matrices: \[ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, \quad \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}. \] There are the two three-cycles: \[ \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}, \quad \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}. \] If two matrices have different traces, then they must have different eigenvalues and so are not similar. The trace of the identity is 3, the trace of the transpositions is 1, and the trace of the three-cycles is 0. We first show that all of the transpositions are similar to each other. Every permutation matrix \(P\) satisfies \[ P\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \] so they all have eigenvalue \(\lambda_1 = 1\). Note that each of the transposition matrices has a fixed point and so has a standard basis vector as an eigenvector with eigenvalue \(\lambda_2 = 1\). For example, \[ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}. \] Since they all have trace 1, their final eigenvalue \(\lambda_3\) must be \(-1\) so that \(\lambda_1 + \lambda_2 + \lambda_3 = 1\). Thus we have shown that the transposition matrices all have the eigenvalue 1 repeated twice with two linearly independent eigenvectors as well as the eigenvalue \(-1\). Therefore, they are similar, as each of their Jordan canonical forms must be \[ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{bmatrix}. \] Finally, we show the two three-cycles are similar to each other. As before, they have eigenvalue \(\lambda_1 = 1\) corresponding to the all-ones vector. Their other two eigenvalues must satisfy \(\lambda_1 + \lambda_2 + \lambda_3 = 0\), so \(\lambda_2 + \lambda_3 = -1\). However, we must have that \(|\lambda_2| = |\lambda_3| = 1\) since the permutation matrices are orthogonal. Note that if \(\lambda_2, \lambda_3\) were real then they must each be 1 or \(-1\), and it is impossible to have \(\lambda_2 + \lambda_3 = -1\). Therefore, they are complex and must satisfy \(\lambda_2 = \overline{\lambda_3}\). Then their real parts are the same and must add to \(-1\), so they each have real part \(-1/2\). Using that \(|\lambda_2| = |\lambda_3| = 1\), we get that one of \(\lambda_2, \lambda_3\) must be \(1/2 + i\sqrt{3}/2\) and the other must be \(1/2 - i\sqrt{3}/2\). Therefore, the three-cycles both have the same eigenvalues, namely the three different cubed roots of 1 in the complex plane, and so are similar.

Keywords: permutation matrix, eigenvalues, singular values, similar matrices, trace