\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{multicol}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{cancel}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}

\input{preamble.tex}

\begin{document}

\homework{7: Similar/Elementary/Permutation Matrices}{Due Wednesday, March 5, by 1:30pm}


Homework problems need to show work and contain proofs in order to receive full credit.  Simply stating an answer is only half of the problem in mathematics; you also need to include an argument that persuades your audience that your answer is correct!  If you have any questions, feel free to contact either Yihan or I via email or office hours.  Have fun!

\begin{enumerate}
\item Take the matrix
\begin{align*}
A = \begin{bmatrix}
1 & 2 & 3\\
0 & 2 & 3\\
0 & 0 & 3\\
\end{bmatrix}_.
\end{align*}
Find some sequence of elementary matrices $E_1, E_2, E_3$ such that 
\begin{align*}
(E_1 \cdot E_2 \cdot E_3) \cdot A \cdot (E_3^{-1} \cdot E_2^{-1} \cdot E_1^{-1}) = \begin{bmatrix}
1 & 0 & 0\\
0 & 2 & 0\\
0 & 0 & 3\\
\end{bmatrix}_.
\end{align*}
In other words, show that $A$ is similar to a matrix made out of just its diagonal entries!
\item Suppose that $P_{\sigma_1}, P_{\sigma_2}$ are a pair of $n \times n$ permutation matrices.  Prove that $P_{\sigma_1} \cdot P_{\sigma_2}$ is also a permutation matrix.
\item Suppose that $P_\sigma$ is a $n \times n$ permutation matrix.  Show that there is some value of $k$ such that $(P_\sigma)^k = I$.
\item Show that if $P_\sigma$ is a permutation matrix, it has $1$ as an eigenvalue.  Also, prove that if $P_\sigma$ is a permutation matrix, it does not have any eigenvalues $\lambda$ with $|\lambda| \neq 1$.
\item\begin{enumerate}
\item Let $P_{\sigma}$ be the following permutation matrix:
\begin{align*}
P_{\sigma} = \begin{bmatrix}
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
1 & 0 & 0& 0\\
\end{bmatrix}_.
\end{align*}
Find three elementary matrices $E_1, E_2, E_3$ of the form $E_{\textrm{switch entry }i\textrm{ and entry }j}$, such that $E_1 \cdot E_2 \cdot E_3 = P_\sigma$.
\item In general, suppose that $P_\sigma$ is a $n \times n$ permutation matrix of the form
\begin{align*}
P_{\sigma} = \begin{bmatrix}
0 & 1 & 0 & \ldots & 0\\
0 & 0 & 1 & \ldots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
0 & 0 & 0 & \ldots & 1\\
1& 0 & 0 & \ldots & 0\\
\end{bmatrix}_.
\end{align*}
Find $n-1$ elementary matrices $E_1, E_2, \ldots E_{n-1}$ of the form $E_{\textrm{switch entry }i\textrm{ and entry }j}$, such that $E_1 \cdot E_2 \cdot \ldots \cdot E_{n-1} = P_\sigma$.
\end{enumerate}
\end{enumerate}





\end{document}