
\documentclass[12pt]{amsart}

\usepackage{241}

\title{21-241 Matrices and Linear Transformations \\
       Summer 1 2012 \\
       Course notes \\
       June 8}
\author{Paul McKenney}


\begin{document}

\maketitle

\begin{thm}
  Let $A,B\in M_n(\CC)$.  Then $\det(AB) = \det(A)\det(B)$.
\end{thm}
\begin{proof}
  By your homework, $AB$ is invertible if and only if both $A$ and $B$ are.  Hence if $\det(AB) = 0$ (ie, $AB$ is not invertible) then one of $\det(A)$, $\det(B)$ must be zero as well, so the equation holds.

  So let's assume $AB$ is invertible, and hence that $A$ and $B$ are too.  Then there are elementary matrices $E_1,\ldots,E_k$ and $F_1,\ldots,F_\ell$ such that
  \[
    A = E_k\cdots E_1\qquad\mbox{and}\qquad B = F_\ell\cdots F_1
  \]
  (These are the \emph{reverse} of the row operations used to reduce $A$ and $B$ to $I$.)  We've seen that
  \[
    \det(A) = \det(E_k)\cdots\det(E_1)\qquad \det(B) = \det(F_\ell)\cdots\det(F_1)
  \]
  and hence
  \[
    \det(AB) = \det((E_k\cdots E_1)(F_\ell\cdots F_1)) = \det(E_k)\cdots\det(E_1)\det(F_\ell)\cdots\det(F_1) = \det(A)\det(B)
  \]
\end{proof}

\begin{defn*}
  A \emph{permutation matrix} is an $n\times n$ matrix $P$ such that
  \begin{enumerate}
    \item  every entry in $P$ is either $0$ or $1$, and
    \item  there is exactly one $1$ in each row and column of $P$.
  \end{enumerate}
\end{defn*}

If $P$ is a permutation matrix then there is an associated permutation of $[n] = \{1,\ldots,n\}$;
\[
  \pi(i) = j \iff P_{ij} = 1
\]
We write $P = P_\pi$.  Note that $\det(P) = \pm 1$, depending on the number of swaps needed to reduce $P$ to $I$.  (Which it turns out is the number of transpositions needed to produce $\pi$.)

For convenience we often use a row vector in $\CC^n$ to describe a permutation $\pi$ of $[n]$.  Specifically, in the $i$th entry of the row vector we write $\pi(i)$; e.g. $(3 1 2)$ denotes the permutation $\pi$ such that $\pi(1) = 3$, $\pi(2) = 1$, and $\pi(3) = 2$.

\begin{defn*}
  Let $\perm(n) = \set{\pi : [n]\to [n]}{\mbox{$\pi$ is a bijection}}$.
\end{defn*}

\begin{fact}
  If $A$ is an $n\times n$ matrix, then
  \[
    \det(A) = \sum_{\pi\in\perm(n)} \det(P_\pi) \prod_{i=1}^n A_{i\pi(i)}
  \]
\end{fact}

\begin{example*}
  Say $A$ is the $3\times 3$ matrix
  \[
    A = \begin{pmatrix}
      a & b & c \\
      d & e & f \\
      g & h & i \\
    \end{pmatrix}
  \]
  The $3! = 6$ permutations of $[3]$ are listed below, along with the determinant of the associated permutation matrix;
  \[
    \begin{matrix}
      (1 & 2 & 3) & & 1 \\
      (1 & 3 & 2) & & -1 \\
      (2 & 1 & 3) & & 1 \\
      (2 & 3 & 1) & & -1 \\
      (3 & 1 & 2) & & 1 \\
      (3 & 2 & 1) & & -1 \\
    \end{matrix}
  \]
  Hence we have
  \[
    \det(A) = +aei + bdi + cdh - afh - bfg - ceg
  \]
\end{example*}
\begin{example*}
  Say $A$ is the $4\times 4$ matrix
  \[
    A = \begin{pmatrix}
      a & b & 0 & 0 \\
      c & d & 0 & 0 \\
      0 & 0 & e & f \\
      0 & 0 & g & h \\
    \end{pmatrix}
  \]
  There are a total of $4! = 24$ permutations of $[4]$, but not very many of them produce a nonzero term in the sum, for this matrix at least.  Which ones do?
\end{example*}

\begin{thm}
  Let $A$ be any $n\times n$ complex matrix.  Then $\det(A) = \det(A^\top)$.
\end{thm}
\begin{proof}
  Let's look at our formula for $\det(A)$, and the same for $\det(A^\top)$, and compare;
  \[
    \det(A) = \sum_{\pi\in\perm(n)} \det(P_\pi) \prod_{i=1}^n A_{i\pi(i)}
  \]
  and
  \[
    \det(A^\top) = \sum_{\pi\in\perm(n)} \det(P_\pi) \prod_{i=1}^n A_{\pi(i)i}
  \]
  Now let $\pi\in\perm(n)$ be given.  Note that
  \[
    \prod_{i=1}^n A_{\pi(i)i} = \prod_{i=1}^n A_{i\pi^{-1}(i)}
  \]
  Let's rewrite our formula accordingly and see if it gets us anywhere.
  \[
    \det(A^\top) = \sum_{\pi\in\perm(n)} \det(P_\pi) \prod_{i=1}^n A_{i\pi^{-1}(i)}
  \]
  Notice that the map $\pi\mapsto \pi^{-1}$ is a bijection; ie, we may reorder the above sum (by relabeling $\sigma = \pi^{-1}$, so $\sigma^{-1} = \pi$) to get
  \[
    \det(A^\top) = \sum_{\sigma\in\perm(n)} \det(P_{\sigma^{-1}}) \prod_{i=1}^n A_{i\sigma(i)}
  \]
  By a problem to be seen on the exam 2 preview, $\det(P_\sigma) = \det(P_{\sigma^{-1}})$ for all $\sigma\in\perm(n)$.  This completes the proof.
\end{proof}

\end{document}
