\section{  Matrices }

\begin{definition}
An $r\times k$ matrix\index{Matrix} $M=(m^i_j)$ for $i=1, \ldots, r; j=1, \ldots, k$ is a rectangular array of real (or complex) numbers:
\[M = 
\begin{pmatrix}
m_1^1 & m_2^1 & \ldots & m_k^1 \\
m_1^2 & m_2^2 & \ldots & m_k^2 \\
\vdots & \vdots &   & \vdots \\
m_1^r & m_2^r & \ldots & m_k^r \\
\end{pmatrix}
\]

The numbers $m^i_j$ are called \emph{entries}\index{Matrix!entries of}.  The superscript indexes the row of the matrix and the subscript indexes the column of the matrix in which $m_j^i$ appears.
\end{definition}

It is often useful to consider matrices whose entries are more general than the real numbers, so we allow that possibility.

An $r\times 1$ matrix $v = (v^r_1) = (v^r)$ is called a \emph{column vector}\index{Column vector}, written $$v = \colvec{v^1\\v^2\\ \vdots \\ v^r }\, .$$  A $1\times k$ matrix is (perhaps unsurprisingly) called a \emph{row vector}\index{Row vector}. 


Matrices are a very useful and efficient way to store information:

\begin{example}
In computer graphics, you may have encountered image files with a .gif extension.  These files are actually just matrices: at the start of the file the size of the matrix is given, and then each entry of the matrix is a number indicating the color of a particular pixel in the image.

The resulting matrix  then has its rows shuffled a bit: by listing, say, every eighth row, then a web browser downloading the file can start displaying an incomplete version of the picture before the download is complete.

Finally, a compression algorithm is applied to the matrix to reduce the size of the file.
\end{example}

\begin{example}
Graphs occur in many applications, ranging from telephone networks to airline routes.  In the subject of \emph{graph theory}\index{Graph theory}, a graph is just a collection of vertices and some edges connecting vertices.  A matrix can be used to indicate how many edges attach one vertex to another.

\begin{center}
\includegraphics[width=10cm]{notes8-0.png}
\end{center}
For example, the graph pictured above would have the following matrix, where $m^i_j$ indicates the number of edges between the vertices labeled $i$~and~$j$:

\[
M = \begin{pmatrix}
1 & 2 & 1 & 1 \\
2 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 0 & 1 & 3 \\
\end{pmatrix}
\]
This is an example of a \emph{symmetric matrix}, since $m_j^i = m_i^j$.
\end{example}

The space of $r\times k$ matrices $M_k^r$ is a vector space with the addition and scalar multiplication defined as follows:

\begin{eqnarray*}
M+N = (m_j^i) + (n_j^i) = ( m_j^i + n_j^i ) \\
rM = r(m_j^i) = (rm_j^i)
\end{eqnarray*}
In other words, addition just adds corresponding entries in two matrices, and scalar multiplication multiplies every entry.
Notice that $M_1^n = \Re^n$ is just the vector space of column vectors.

Recall that $r\times k$ matrices can be used to represent  linear transformations 
$ \Re^k \rightarrow \Re^r $
via $$MV = (\sum_{j=1}^{k} m_j^iv^j )\, .$$  Here we multiply an $r\times k$ matrix by a $k\times 1$ vector to produce a $r\times1$ vector.

Likewise, we can use matrices $N=(n^i_j)$ to represent linear transformations
\[
M^s_k \stackrel{N}{\longrightarrow} M^r_k
\]
via $(L(M)^i_l) = (\sum_{j=1}^{k} n_j^im^j_l ) $. This rule obeys linearity.

Notice that in order for the multiplication to make sense, the columns and rows must match.  For an $r\times k$ matrix $M$ and an $s\times m$ matrix $N$, then to make the product $MN$ we must have $k=s$.  Likewise, for the product $NM$, it is required that $m=r$.  A common shorthand for keeping track of the sizes of the matrices involved in a given product is: 
\[(r \times k)\times (k\times m) = (r\times m)\]

\begin{example}
Multiplying a $(3\times 1)$ matrix and a $(1\times 2)$ matrix yields a $(3\times 2)$ matrix.

\[
\colvec{1\\3\\2} \rowvec{2 & 3} = 
\begin{pmatrix}
1\cdot 2 & 1\cdot 3 \\
3\cdot 2 & 3\cdot 3 \\
2\cdot 2 & 2\cdot 3 \\
\end{pmatrix}
= \begin{pmatrix}
2 & 3 \\
6 & 9 \\
4 & 6 \\
\end{pmatrix}
\]
\end{example}

\begin{definition}[Matrix Terminology]
The entries $m_i^i$ are called \emph{diagonal}, and the set $\{m_1^1$, $m_2^2$, $\ldots \}$~is called the \emph{diagonal of the matrix}\index{Matrix!diagonal of}.

Any $r\times r$ matrix is called a \emph{square matrix}\index{Square matrix}.  A square matrix that is zero for all non-diagonal entries is called a diagonal matrix\index{Diagonal matrix}.

The $r\times r$ diagonal matrix with all diagonal entries equal to $1$ is called the \emph{identity matrix}\index{Identity matrix}, $I_r$, or just $\1$.  The identity matrix is spacial because $$I_rM=MI_k=M$$ for all $M$ of size $r\times k$.
\end{definition}

In the matrix given by the product of matrices  above, the diagonal entries are $2$ and $9$.
An example of a diagonal matrix is 
$$\begin{pmatrix}
2 & 0 & 0\\
0 & 3 & 0\\
0 & 0 & 0\\
\end{pmatrix}\, .$$

\begin{definition}
The \emph{transpose}\index{Transpose} of an $r\times k$ matrix $M = (m_j^i)$ is the $k\times r$ matrix with entries
\[
M^T = (\bar{m}_j^i)
\]
with $\bar{m}_j^i = m_i^j$. 

A matrix $M$ is \emph{symmetric}\index{Symmetric matrix} if $M=M^T$.
\end{definition}

\begin{example}
$\begin{pmatrix}
2 & 5 & 6\\
1 & 3 & 4\\
\end{pmatrix}^T = 
\begin{pmatrix}
2 & 1 \\
5 & 3 \\
6 & 4 \\
\end{pmatrix}$
\end{example}


\begin{remark}[Observations]

$\phantom{test}$

\begin{itemize}
\item Only square matrices can be symmetric.

\item The transpose of a column vector is a row vector, and vice-versa. 

\item Taking the transpose of a matrix twice does nothing.  \emph{i.e.,} $(M^T)^T=M$.
\end{itemize}
\end{remark}

\begin{theorem}[Transpose and Multiplication]
Let $M, N$ be matrices such that $MN$ makes sense.  Then $(MN)^T = N^TM^T$.
\end{theorem}


\section*{References}
Hefferon, Chapter Three, Section IV, parts 1-3.

Wikipedia:
\begin{itemize}
\item \href{http://en.wikipedia.org/wiki/Matrix_multiplication}{Matrix Multiplication}
\end{itemize}





\section*{Review Questions}
\begin{enumerate}
\item Above, we showed that \emph{left} multiplication by an $r \times k$ matrix $N$  was a linear transformation $M^s_k \stackrel{N}{\longrightarrow} M^r_k$.  Show that \emph{right} multiplication by an $s \times m$ matrix $R$ is a linear transformation $M^s_k \stackrel{R}{\longrightarrow} M^s_m$.  In other words, show that right matrix multiplication obeys linearity.



\item Prove the theorem $(MN)^T = N^TM^T$.

\item Let $M$ be any $m\times n$ matrix.  Show that $M^TM$ and $MM^T$ are symmetric.  What are their sizes?

\item Let $x = \colvec{x_1 \\ \vdots \\ x_n}$ and $y = \colvec{y_1 \\ \vdots \\ y_n}$ be column vectors.  Prove that the dot product $x \dotprod y = x^T\  \1\  y$.


\item Explain what happens to a matrix when:
\begin{itemize}
\item[(i)] You multiply it on the left by a diagonal matrix.
\item[(ii)] You multiply it on the right by a diagonal matrix.
\end{itemize}
Give a few simple examples before you start explaining.



\end{enumerate}


\newpage
