chapter_2.2.lyx

#LyX 2.0 created this file. For more info see http://www.lyx.org/
\lyxformat 413
\begin_document
\begin_header
\textclass scrbook
\begin_preamble
\setcounter{chapter}{2}
\usepackage{graphicx}
\usepackage{pict2e}
\usepackage{graphpap}
\usepackage{color}
\usepackage{bm}
\end_preamble
\use_default_options false
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\use_mhchem 1
\use_mathdots 1
\cite_engine basic
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\use_refstyle 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Section
Matrices
\end_layout

\begin_layout Standard
Matrices are really nothing but a very convenient notation for (linear)
 transformations on vectors.
 For example, the transformations of stretching a vector, or rotating it,
 or reflecting it can all be written as matrix products.
\end_layout

\begin_layout Paragraph
Example 1
\end_layout

\begin_layout Standard
In the photoreceptors of the retina, color is represented by the activation
 of L, M and S cones (which are selective to 'red', 'green' and 'blue' light,
 respectively.) In a crude approximation, the classical view of color vision
 is that, at later processing stages, the color of a stimulus is rather
 represented by two 'color-opponent' channels, and a 'luminance' channel.
 Luminance could be computed by simply adding the activities of all cones:
 
\begin_inset Formula $Lum=L+M+S.$
\end_inset

 the 'red-green' channel could be computed by subtracting the M cone activity
 from the S cones, 
\begin_inset Formula $RG=L-M,$
\end_inset

 and the 'blue yellow' channel by subtracting a combination of M and L from
 S: 
\begin_inset Formula $BY=S-(M+L).$
\end_inset

 To sum up: 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\]

\end_inset


\begin_inset Formula 
\begin{eqnarray*}
RG & = & L-M+0\cdot S\\
BY & = & -L-M+S\\
Lum & = & L+M+S.
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
This can be written in matrix notation as
\begin_inset Formula 
\[
\left(\begin{array}{c}
RG\\
BY\\
Lum
\end{array}\right)=\left(\begin{array}{ccc}
1 & -1 & 0\\
-1 & -1 & 1\\
1 & 1 & 1
\end{array}\right)\left(\begin{array}{c}
L\\
M\\
S
\end{array}\right).
\]

\end_inset


\end_layout

\begin_layout Standard
So, multiplying the vector of cone-activities by this matrix returns the
 vector of channel-activities.
 This mapping from one 
\begin_inset Formula $3$
\end_inset

 dimensional vector to another 
\begin_inset Formula $3$
\end_inset

 dimensional vector can be summarized succinctly by a matrix product.
\end_layout

\begin_layout Standard
Now, we will formally define what we mean by a matrix, and by a matrix-vector
 product:
\end_layout

\begin_layout Subsubsection*
Definition (Matrix and matrix-vector product)
\end_layout

\begin_layout Standard
A matrix 
\begin_inset Formula $A$
\end_inset

 of size 
\begin_inset Formula $m$
\end_inset

 by 
\begin_inset Formula $n$
\end_inset

 is a collection of numbers of the form
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{A}=\left(\begin{array}{cccc}
A_{11} & A_{12} & \cdots & A_{1n}\\
A_{21} & A_{22} &  & A_{2n}\\
\vdots & \vdots & \dots & \vdots\\
A_{m1} & A_{m2} & \dots & A_{mn}
\end{array}\right).
\]

\end_inset


\end_layout

\begin_layout Standard
The matrix product 
\begin_inset Formula $y=Ax$
\end_inset

 between an 
\begin_inset Formula $m\times n$
\end_inset

 matrix and an 
\begin_inset Formula $n$
\end_inset

 dimensional vector x is defined to be
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
y=Ax=\left(\begin{array}{c}
\sum_{i=1}^{n}A_{1i}x_{i}\\
\sum_{i=1}^{n}A_{2i}x_{i}\\
\vdots\\
\sum_{i=1}^{n}A_{mi}x_{i}
\end{array}\right).
\]

\end_inset


\end_layout

\begin_layout Standard
We often say that 
\begin_inset Formula $x$
\end_inset

 is 'pre-multiplied' by 
\begin_inset Formula $A.$
\end_inset

 
\end_layout

\begin_layout Subsubsection*
Note
\end_layout

\begin_layout Itemize
We can see that multiplying a vector by a matrix is really nothing but a
 couple of dot products: To compute the first element of 
\begin_inset Formula $y,$
\end_inset


\begin_inset Formula $ $
\end_inset

 we simply compute the dot product between 
\begin_inset Formula $x$
\end_inset

 and the first row of 
\begin_inset Formula $A:$
\end_inset

 
\begin_inset Formula $y_{1}=\sum_{i=1}^{n}A_{1i}x_{i}=\langle A_{(1)},x\rangle,$
\end_inset

 where we define 
\begin_inset Formula $A_{(1)}=(A_{11},A_{12},\ldots,A_{1n}).$
\end_inset


\begin_inset Formula $ $
\end_inset


\end_layout

\begin_layout Itemize
For matrix-vector multiplication to make sense, the sizes have to match:
 If 
\begin_inset Formula $x$
\end_inset

 has 
\begin_inset Formula $n$
\end_inset

 elements, we can only compute 
\begin_inset Formula $Ax$
\end_inset

 if 
\begin_inset Formula $A$
\end_inset

 is of size 
\begin_inset Formula $m\times n$
\end_inset

! Thus, if 
\begin_inset Formula $m\neq n,$
\end_inset

 
\begin_inset Formula $Ax$
\end_inset

 is defined, but 
\begin_inset Formula $xA$
\end_inset

 would not be defined!
\end_layout

\begin_layout Itemize
The result of multiplying an 
\begin_inset Formula $m\times n$
\end_inset

 matrix to a vector of size 
\begin_inset Formula $n\times$
\end_inset

1 is always a vector of size 
\begin_inset Formula $m\times1$
\end_inset

.
 
\end_layout

\begin_layout Subsection
Reading a matrix
\end_layout

\begin_layout Standard
The 'canonical basis vectors' are defined to be those vectors that have
 exactly one entry equal to 
\begin_inset Formula $1$
\end_inset

, and 
\begin_inset Formula $0$
\end_inset

 everywhere else.
 For example, in 
\begin_inset Formula $2D,$
\end_inset

 the canonical basis vectors are 
\begin_inset Formula $e_{1}={1 \choose 0}$
\end_inset

 and 
\begin_inset Formula $e_{2}={0 \choose 1},$
\end_inset

 i.e the vectors that define the 
\begin_inset Formula $x$
\end_inset

 and 
\begin_inset Formula $y-$
\end_inset

axis, respectively.
 If we multiply a matrix 
\begin_inset Formula $M$
\end_inset

 by 
\begin_inset Formula $e_{1},$
\end_inset

 we get back the first column of 
\begin_inset Formula $M:$
\end_inset

 For example, 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{eqnarray*}
\left(\begin{array}{cc}
2 & 3\\
1 & 1
\end{array}\right){1 \choose 0} & = & {2 \choose 1}\\
\left(\begin{array}{cc}
2 & 3\\
1 & 1
\end{array}\right){0 \choose 1} & = & {3 \choose 1}.
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
Therefore, the columns of a matrix are exactly the 'images' of the canonical
 basis vectors under matrix multiplication.
 From these images, we can calculate the image of any arbitrary vector 
\begin_inset Formula $x,$
\end_inset

 as 
\begin_inset Formula $ $
\end_inset


\begin_inset Formula 
\[
x={x_{1} \choose x_{2}}=x_{1}{1 \choose 0}+x_{2}{0 \choose 1}.
\]

\end_inset


\end_layout

\begin_layout Standard
Therefore, 
\begin_inset Formula 
\begin{eqnarray*}
Mx & = & M\left(x_{1}{1 \choose 0}+x_{2}{0 \choose 1}\right)\\
 & = & x_{1}{2 \choose 1}+x_{2}{3 \choose 1}.
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
Hence, the image of any vector 
\begin_inset Formula $x$
\end_inset

 under multiplication by the matrix 
\begin_inset Formula $M$
\end_inset

 can always be written as a linear combination of the columns of 
\begin_inset Formula $M.$
\end_inset


\begin_inset Formula 
\[
\]

\end_inset


\end_layout

\begin_layout Subsection*
Examples of matrices
\end_layout

\begin_layout Itemize
The identify matrix is a boring matrix which does not do anything.
 Multiplying any vector by it leaves it unchanged:
\begin_inset Formula 
\begin{eqnarray*}
\\
\mathbf{I} & = & (\mathbf{e}_{1},\mathbf{e}_{2},...,\mathbf{e}_{n})\\
 & = & \left(\begin{array}{cccc}
1 & 0 & \dots & 0\\
\vdots & 1 & \ddots & 0\\
0 & \vdots & \dots & \vdots\\
0 & 0 & \dots & 1
\end{array}\right).
\end{eqnarray*}

\end_inset

Despite its boringness, this matrix occurs so frequently that we give it
 its own symbol, namely uppercase 
\begin_inset Formula $\mathbf{I}$
\end_inset

.
 This should not be confused with images, that we also denote by 
\begin_inset Formula $\mathbf{I}$
\end_inset

.
 However, it should be clear from the context what we mean by 
\begin_inset Formula $\mathbf{I}$
\end_inset

.
\begin_inset Newline newline
\end_inset

The result of multiplying a vector 
\begin_inset Formula $\mathbf{x}$
\end_inset

 with the identity matrix is just the vector itself:
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{Ix} & = & \left(\begin{array}{cccc}
1 & 0 & \dots & 0\\
\vdots & 1 & \ddots & 0\\
0 & \vdots & \dots & \vdots\\
0 & 0 & \dots & 1
\end{array}\right)\left(\begin{array}{c}
x_{1}\\
\vdots\\
x_{n}
\end{array}\right)\\
 & = & \left(\begin{array}{c}
\mathbf{e}_{1}^{\top}\mathbf{x}\\
\vdots\\
\mathbf{e}_{n}^{\top}\mathbf{x}
\end{array}\right)\\
 & = & \left(\begin{array}{c}
x_{1}\\
\vdots\\
x_{n}
\end{array}\right)=\mathbf{x}.
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
Matrices that look very similar to the identity matrix, are 
\emph on

\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
permutation matrices
\end_layout

\end_inset

permutation matrices
\emph default
.
 A permutation simply changes the order of coordinates of a vector 
\begin_inset Formula $\mathbf{x}$
\end_inset

.
 Let us look at a 3D example.
 Let 
\begin_inset Formula $\mathbf{x}=(x_{1},x_{2},x_{3})^{\top}$
\end_inset

 and let 
\begin_inset Formula $f$
\end_inset

 be the permutation that swaps 
\begin_inset Formula $x_{1}$
\end_inset

 and 
\begin_inset Formula $x_{2}$
\end_inset

, i.e.
 
\begin_inset Formula $f(\mathbf{x})=(x_{2},x_{1},x_{3})$
\end_inset

.
 The corresponding permutation matrix is given by
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{P} & = & \left(\begin{array}{ccc}
0 & 1 & 0\\
1 & 0 & 0\\
0 & 0 & 1
\end{array}\right).
\end{eqnarray*}

\end_inset


\begin_inset Newline newline
\end_inset

Multiplying a three dimensional vector 
\begin_inset Formula $\mathbf{x}=(x_{1},x_{2},x_{3})^{\top}$
\end_inset

 with our example of a permutation matrix yields 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{Px} & = & \left(\begin{array}{ccc}
0 & 1 & 0\\
1 & 0 & 0\\
0 & 0 & 1
\end{array}\right)\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)\\
 & = & \left(\begin{array}{c}
\mathbf{e}_{2}^{\top}\mathbf{x}\\
\mathbf{e}_{1}^{\top}\mathbf{x}\\
\mathbf{e}_{3}^{\top}\mathbf{x}
\end{array}\right)\\
 & = & \left(\begin{array}{c}
x_{2}\\
x_{1}\\
x_{3}
\end{array}\right).
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
In geometry, 
\emph on

\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
rotation matrices
\end_layout

\end_inset

rotation matrices
\emph default
 play an important role: For a fixed a rotation angle 
\begin_inset Formula $\varphi$
\end_inset

, rotating vectors is linear mapping, since it does not matter if we add
 two vectors, rotate the result by 
\begin_inset Formula $\varphi$
\end_inset

, or do it the other way around.
 In 2D there is only one rotation matrix for a given angle 
\begin_inset Formula $\varphi$
\end_inset

:
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R} & = & \left(\begin{array}{cc}
\cos\varphi & -\sin\varphi\\
\sin\varphi & \cos\varphi
\end{array}\right).
\end{eqnarray*}

\end_inset

In 3D we have three coordinate planes where we can rotate a vector in, i.e.
 the 
\begin_inset Formula $x_{1}x_{2}$
\end_inset

-, the 
\begin_inset Formula $x_{1}x_{3}$
\end_inset

- and the 
\begin_inset Formula $x_{2}x_{3}$
\end_inset

-plane.
 In ND we have even more.
 However, the corresponding rotation matrices are easy to remember.
 You can build them by taking the identity matrix and replacing the entries
 corresponding to the coordinate plane you want to rotate in by the entries
 that you would use for the 2D rotation matrix.
 For example, the rotation matrix for the 
\begin_inset Formula $x_{1}x_{2}$
\end_inset

-plane in 3D is given by 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R} & = & \left(\begin{array}{ccc}
\cos\varphi & -\sin\varphi & 0\\
\sin\varphi & \cos\varphi & 0\\
0 & 0 & 1
\end{array}\right),
\end{eqnarray*}

\end_inset

the matrix for a rotation in the 
\begin_inset Formula $x_{1}x_{3}$
\end_inset

-plane is given by 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R} & = & \left(\begin{array}{ccc}
\cos\varphi & 0 & -\sin\varphi\\
0 & 1 & 0\\
\sin\varphi & 0 & \cos\varphi
\end{array}\right).
\end{eqnarray*}

\end_inset


\begin_inset Newline newline
\end_inset

Multiplying a vector with a rotation matrix, means rotating this vector.
 Let us look at one simple example in detail: Rotating the vector 
\begin_inset Formula ${1 \choose 0}\in\mathbb{R}^{2}$
\end_inset

 about 
\begin_inset Formula $90^{\circ}$
\end_inset

.
 From their definition, we can get the appropriate rotation matrix: 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R} & = & \left(\begin{array}{cc}
\cos90^{\circ} & -\sin90^{\circ}\\
\sin90^{\circ} & \cos90^{\circ}
\end{array}\right)\\
 & = & \left(\begin{array}{cc}
0 & -1\\
1 & 0
\end{array}\right).
\end{eqnarray*}

\end_inset

Now we can apply it to our vector 
\begin_inset Formula $(1,0)^{\top}$
\end_inset

:
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R}{1 \choose 0} & = & {0 \choose 1}.
\end{eqnarray*}

\end_inset

We see that the resulting vector has been rotated by 
\begin_inset Formula $90^{\circ}$
\end_inset

.
 Multiplying it again with 
\begin_inset Formula $\mathbf{R}$
\end_inset

, yields 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R}\mathbf{R}{1 \choose 0} & = & \mathbf{R}{0 \choose 1}\\
 & = & {0 \choose -1},
\end{eqnarray*}

\end_inset

which is indeed a rotation about 
\begin_inset Formula $2\cdot90^{\circ}=180^{\circ}$
\end_inset

.
 In general this choice of 
\begin_inset Formula $\mathbf{R}$
\end_inset

 will rotate any vector in 
\begin_inset Formula $\mathbb{R}^{2}$
\end_inset

 about 
\begin_inset Formula $90^{\circ}$
\end_inset

 around the origin.
 If we choose 
\begin_inset Formula $\varphi$
\end_inset

 differently, the resulting matrix will rotate any vector in 
\begin_inset Formula $\mathbb{R}^{2}$
\end_inset

 about 
\begin_inset Formula $\varphi$
\end_inset

.
 
\begin_inset Newline newline
\end_inset

In 3D the example works just the same.
 You might want to try it with a few examples in order to get used to multiplyin
g vectors with matrices.
\end_layout

\begin_layout Itemize
The matrix that corresponds to the projection of a vector 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{3}$
\end_inset

 onto the 
\begin_inset Formula $x_{1}x_{2}$
\end_inset

-plane, is given by
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{P}_{12} & = & \left(\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0
\end{array}\right).
\end{eqnarray*}

\end_inset

Note, that the third column is zero since projecting the vector 
\begin_inset Formula $(0,0,1)^{\top}$
\end_inset

 onto the 
\begin_inset Formula $x_{1}x_{2}$
\end_inset

-plane yields the vector 
\begin_inset Formula $(0,0)^{\top}$
\end_inset

.
\begin_inset Newline newline
\end_inset

Applying the matrix, that projects every vector 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{3}$
\end_inset

 onto the 
\begin_inset Formula $x_{1}x_{2}$
\end_inset

-plane, to an arbitrary vector 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{3}$
\end_inset

 yields
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{P}_{12}\mathbf{x} & = & \left(\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0
\end{array}\right)\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)\\
 & = & {x_{1} \choose x_{2}},
\end{eqnarray*}

\end_inset

which is indeed the projection of 
\begin_inset Formula $\mathbf{x}=(x_{1},x_{2},x_{3})^{\top}$
\end_inset

 onto the 
\begin_inset Formula $x_{1}x_{2}$
\end_inset

-plane.
\end_layout

\begin_layout Itemize
Any scalar product can be thought of as a matrix product: The scalar product
 between two vectors 
\begin_inset Formula $v$
\end_inset

 and 
\begin_inset Formula $w$
\end_inset

 is defined to be
\begin_inset Formula 
\[
\langle v,w\rangle=\sum_{i}v_{i}w_{i}.
\]

\end_inset

 We can see that this is equivalent to 
\begin_inset Formula $v^{\top}w=\sum_{i}v_{i}w_{i},$
\end_inset

 i.e.
 of pre-multiplying 
\begin_inset Formula $w$
\end_inset

 be the transpose of 
\begin_inset Formula $v,$
\end_inset


\begin_inset Formula $v^{\top}.$
\end_inset


\end_layout

\begin_layout Subsection
Every linear function can be written as a matrix product:
\end_layout

\begin_layout Paragraph
Example 
\end_layout

\begin_layout Standard
Remember our very simple linear response model for a V1 simple cell.
 Since the number of pixels of the presented image does not really matter,
 let us only consider 
\begin_inset Formula $2\times2$
\end_inset

 input images.
 As shown in one of the examples above, we can represent any of those input
 images by a four-dimensional vector 
\begin_inset Formula $\mathbf{v}=(I_{11},I_{21},I_{12},I_{22})^{\top}$
\end_inset

.
 In contrast to the previous example, we now consider the spiking rate of
 three instead of only one neuron.
 By assuming that the relation between input image and spiking rate of our
 neurons is linear, our model for the spiking rates given an image is a
 linear function 
\begin_inset Formula $f:\mathbb{R}^{4}\rightarrow\mathbb{R}^{3}$
\end_inset

.
\end_layout

\begin_layout Standard
Assume now that we measured the response of our three neurons for the four
 images 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{I}_{1} & = & \left(\begin{array}{cc}
1 & 0\\
0 & 0
\end{array}\right)\\
\mathbf{I}_{2} & = & \left(\begin{array}{cc}
0 & 0\\
1 & 0
\end{array}\right)\\
\mathbf{I}_{3} & = & \left(\begin{array}{cc}
0 & 1\\
0 & 0
\end{array}\right)\\
\mathbf{I}_{4} & = & \left(\begin{array}{cc}
0 & 0\\
0 & 1
\end{array}\right),
\end{eqnarray*}

\end_inset

which yielded us four spike rate measurements 
\begin_inset Formula $\mathbf{r}_{1}=\left(\begin{array}{c}
r_{11}\\
\vdots\\
r_{31}
\end{array}\right)$
\end_inset

, 
\begin_inset Formula $\mathbf{r}_{2}=\left(\begin{array}{c}
r_{12}\\
\vdots\\
r_{32}
\end{array}\right)$
\end_inset

, 
\begin_inset Formula $\mathbf{r}_{3}=\left(\begin{array}{c}
r_{13}\\
\vdots\\
r_{33}
\end{array}\right)$
\end_inset

 and 
\begin_inset Formula $\mathbf{r}_{4}=\left(\begin{array}{c}
r_{14}\\
\vdots\\
r_{34}
\end{array}\right)$
\end_inset

.
 
\end_layout

\begin_layout Standard
Note that the vectors 
\begin_inset Formula $\mathbf{v}_{1},...,\mathbf{v}_{4}$
\end_inset

, which correspond to the four input images 
\begin_inset Formula $\mathbf{I}_{1},...,\mathbf{I}_{n}$
\end_inset

, are really just the canonical basis of 
\begin_inset Formula $\mathbb{R}^{4}$
\end_inset

.
 Assume now that we get another image 
\begin_inset Formula $\tilde{\mathbf{I}}$
\end_inset

 and we are asked to predict the responses of our three neurons.
 In the linear model, we can use the already measured responses 
\begin_inset Formula $\mathbf{r}_{1},...,\mathbf{r}_{4}$
\end_inset

 to predict the response 
\begin_inset Formula $\tilde{\mathbf{r}}$
\end_inset

.
 The strategy for that is as follows: First we express the vector notation
 
\begin_inset Formula $\tilde{\mathbf{v}}$
\end_inset

 of the new image as a linear combination of the vector notations 
\begin_inset Formula $\mathbf{v}_{1},...,\mathbf{v}_{4}$
\end_inset

 of the images 
\begin_inset Formula $\mathbf{I}_{1},...,\mathbf{I}_{4}$
\end_inset

:
\begin_inset Formula 
\begin{eqnarray*}
\tilde{\mathbf{v}} & = & \sum_{i=1}^{4}\tilde{v}_{i}\mathbf{v}_{i}\\
 & = & \tilde{I}_{11}\left(\begin{array}{c}
1\\
0\\
0\\
0
\end{array}\right)+\tilde{I}_{21}\left(\begin{array}{c}
0\\
1\\
0\\
0
\end{array}\right)+\tilde{I}_{12}\left(\begin{array}{c}
0\\
0\\
1\\
0
\end{array}\right)+\tilde{I}_{22}\left(\begin{array}{c}
0\\
0\\
0\\
1
\end{array}\right).
\end{eqnarray*}

\end_inset

Then we compute the response of our three neurons via:
\begin_inset Formula 
\begin{eqnarray*}
f\left(\sum_{i=1}^{4}\tilde{v}_{i}\mathbf{v}_{i}\right) & \stackrel{f\mbox{ linear}}{=} & \sum_{i=1}^{4}\tilde{v}_{i}f\left(\mathbf{v}_{i}\right)\\
 & = & \sum_{i=1}^{4}\tilde{v}_{i}\mathbf{r}_{i}\\
 & = & \left(\begin{array}{c}
\sum_{i=1}^{4}\tilde{v}_{i}r_{1i}\\
\sum_{i=1}^{4}\tilde{v}_{i}r_{2i}\\
\sum_{i=1}^{4}\tilde{v}_{i}r_{3i}
\end{array}\right).
\end{eqnarray*}

\end_inset

As we can see, using the linearity of 
\begin_inset Formula $f$
\end_inset

, four measurements of linear independent inputs are enough to determine
 the output of an arbitrary four dimensional image.
 Therefore, our linear function is completely determined by our four measurement
s.
\end_layout

\begin_layout Standard
\align right
\begin_inset Formula $\lhd$
\end_inset


\end_layout

\begin_layout Standard
This example shows a very important aspect of 
\begin_inset Formula $n$
\end_inset

-dimensional linear functions.
 Now, we state this observation in a more general way.
\end_layout

\begin_layout Standard
We can always define the matrix of a mapping with respect to any basis:
 Let 
\begin_inset Formula $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$
\end_inset

 be a linear function which takes in an 
\begin_inset Formula $n$
\end_inset

 dimensional vector and returns an 
\begin_inset Formula $m$
\end_inset

 dimensional one.
 We know that each 
\begin_inset Formula $n$
\end_inset

-dimensional vector 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{n}$
\end_inset

 can be described in terms of a linear combination 
\begin_inset Formula $\mathbf{x}=\sum_{i=1}^{n}\lambda_{i}\mathbf{b}_{i}$
\end_inset

 of 
\begin_inset Formula $n$
\end_inset

 basis vectors 
\begin_inset Formula $\mathbf{b}_{1},...,\mathbf{b}_{n}$
\end_inset

.
 Since we can exchange the summation and function symbol for linear functions
 we can do the same operation as for the one-dimensional case:
\begin_inset Formula 
\begin{eqnarray*}
f_{k}(\mathbf{x}) & = & f_{k}\left(\sum_{i=1}^{n}\lambda_{i}\mathbf{b}_{i}\right)\\
 & = & \sum_{i=1}^{n}\lambda_{i}f_{k}(\mathbf{b}_{i}),\,\mbox{for}\, k=1,...,n.
\end{eqnarray*}

\end_inset

Here, 
\begin_inset Formula $f_{k}(\mathbf{x})$
\end_inset

 denotes the 
\begin_inset Formula $k$
\end_inset

th coordinate of the output vector 
\begin_inset Formula $f(\mathbf{x})$
\end_inset

.
 Therefore, we can determine the function value of an arbitrary vector 
\begin_inset Formula $\mathbf{x}$
\end_inset

 by first expressing 
\begin_inset Formula $\mathbf{x}$
\end_inset

 in terms of the 
\begin_inset Formula $\mathbf{b}_{1},...,\mathbf{b}_{n}$
\end_inset

, therefore getting the coordinates 
\begin_inset Formula $\lambda_{1},...,\lambda_{n}$
\end_inset

, and then building a linear combination 
\begin_inset Formula $\sum_{i=1}^{n}\lambda_{i}f_{k}(\mathbf{b}_{i})$
\end_inset

 of the known function values 
\begin_inset Formula $f_{k}(\mathbf{b}_{i})$
\end_inset

.
 This is the basic mathematical mechanic behind matrices.
\end_layout

\begin_layout Paragraph
Definition (Matrix of a linear mapping)
\end_layout

\begin_layout Standard
Given an 
\begin_inset Formula $n$
\end_inset

-dimensional linear function 
\begin_inset Formula $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$
\end_inset

 and a basis for 
\begin_inset Formula $\mathbf{b}_{1},...,\mathbf{b}_{n}\in\mathbb{R}^{n}$
\end_inset

, the matrix of the function 
\begin_inset Formula $f$
\end_inset

 according to the basis 
\begin_inset Formula $\mathbf{b}_{1},...,\mathbf{b}_{n}$
\end_inset

 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{A} & = & \left(\begin{array}{cccc}
f_{1}(\mathbf{b}_{1}) & f_{1}(\mathbf{b}_{2}) & f_{1}(\mathbf{b}_{n-1}) & f_{1}(\mathbf{b}_{n})\\
\vdots & f_{2}(\mathbf{b}_{2}) &  & f_{2}(\mathbf{b}_{n})\\
f_{m-1}(\mathbf{b}_{1}) & \vdots & \dots & \vdots\\
f_{m}(\mathbf{b}_{1}) & f_{m}(\mathbf{b}_{2}) & \dots & f_{m}(\mathbf{b}_{n})
\end{array}\right)
\end{eqnarray*}

\end_inset

stores the function values 
\begin_inset Formula $f_{k}(\mathbf{b}_{i})$
\end_inset

 for 
\begin_inset Formula $i=1,...,n$
\end_inset

 and 
\begin_inset Formula $k=1,...,m$
\end_inset

, i.e.
 the 
\begin_inset Formula $j$
\end_inset

th column is the output of 
\begin_inset Formula $f$
\end_inset

 on the 
\begin_inset Formula $j$
\end_inset

th basis vector.
 These function values are everything that is needed to compute the outcome
 of the linear function for an arbitrary input.
 
\end_layout

\begin_layout Standard
\align right
\begin_inset Formula $\Diamond$
\end_inset


\end_layout

\begin_layout Standard
This means that each 
\begin_inset Formula $n$
\end_inset

-dimensional linear function 
\begin_inset Formula $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$
\end_inset

 can be expressed in terms of a 
\begin_inset Formula $m\times n$
\end_inset

 matrix if we choose a basis 
\begin_inset Formula $\mathbf{b}_{1},...,\mathbf{b}_{n}$
\end_inset

.
 On the other hand, each 
\begin_inset Formula $m\times n$
\end_inset

 matrix, i.e.
 an arbitrary 
\begin_inset Formula $m\times n$
\end_inset

 grid of numbers, determines a linear function for a given basis 
\begin_inset Formula $\mathbf{b}_{1},...,\mathbf{b}_{n}$
\end_inset

.
 
\end_layout

\begin_layout Standard
It is important to understand that a matrix is always with respect to a
 certain basis.
 If the basis changes, the matrix changes.
 The linear function, however, does not.
\end_layout

\begin_layout Standard
From now on, unless explicitly noted, we use the canonical basis of 
\begin_inset Formula $\mathbf{e}_{1},...,\mathbf{e}_{n}\in\mathbb{R}^{n}$
\end_inset

 when dealing with matrices, i.e.
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{A} & = & \left(\begin{array}{cccc}
f_{1}(\mathbf{e}_{1}) & f_{1}(\mathbf{e}_{2}) & f_{1}(\mathbf{e}_{n-1}) & f_{1}(\mathbf{e}_{n})\\
\vdots & f_{2}(\mathbf{e}_{2}) & \ddots & f_{2}(\mathbf{e}_{n})\\
f_{m-1}(\mathbf{e}_{1}) & \vdots & \dots & \vdots\\
f_{m}(\mathbf{e}_{1}) & f_{m}(\mathbf{e}_{2}) & \dots & f_{m}(\mathbf{e}_{n})
\end{array}\right).
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Subsection
Multiplying two matrices
\end_layout

\begin_layout Standard
\align right
\begin_inset Formula $\lhd$
\end_inset


\end_layout

\begin_layout Subsubsection
Matrix-Matrix Product
\end_layout

\begin_layout Standard
In the above example about the rotation matrices, we rotated a vector by
 
\begin_inset Formula $180^{\circ}$
\end_inset

 degrees by rotating it twice by 
\begin_inset Formula $90^{\circ}$
\end_inset

 degrees with our rotation matrix 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R} & = & \left(\begin{array}{cc}
\cos90^{\circ} & -\sin90^{\circ}\\
\sin90^{\circ} & \cos90^{\circ}
\end{array}\right)\\
 & = & \left(\begin{array}{cc}
0 & -1\\
1 & 0
\end{array}\right).
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
The way we did this was multiplying a vector with 
\begin_inset Formula $\mathbf{R}$
\end_inset

 and doing the same operation with the outcome again.
 However, there is also another way for computing this outcome: By multiplying
 the matrix 
\begin_inset Formula $\mathbf{R}$
\end_inset

 with itself and obtain a new matrix 
\begin_inset Formula $\mathbf{R}'$
\end_inset

 that corresponds to a rotation about 
\begin_inset Formula $180^{\circ}$
\end_inset

 degrees.
 Speaking in terms of functions, the matrix 
\begin_inset Formula $\mathbf{R}'=\mathbf{R}\cdot\mathbf{R}$
\end_inset

 corresponds to the linear function 
\begin_inset Formula $rot_{180}(\mathbf{x})=rot_{90}(rot_{90}(\mathbf{x}))$
\end_inset

 if 
\begin_inset Formula $rot_{\varphi}$
\end_inset

 denotes the function that rotates a vector by 
\begin_inset Formula $\varphi$
\end_inset

.
 This means that we obtain the matrix of a composition of two functions
 by multiplying their matrices.
 Multiplying two matrices is fairly easy: We just treat each of its columns
 as a vector on its own and multiply it with the matrix.
 The result of this multiplication determines one column of the matrix-matrix
 product.
 
\end_layout

\begin_layout Paragraph
Definition (Matrix-Matrix Product)
\end_layout

\begin_layout Standard
The product of a matrix 
\begin_inset Formula $\mathbf{A}\in\mathbb{R}^{m\times n}$
\end_inset

 with another matrix 
\begin_inset Formula $\mathbf{B}^{n\times k}$
\end_inset

 is given by 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{A}\cdot\mathbf{B} & = & \left(\begin{array}{cccc}
\sum_{i=1}^{n}\mathbf{A}_{1i}\mathbf{B}_{i1} & \sum_{i=1}^{n}\mathbf{A}_{1i}\mathbf{B}_{i2} & \dots & \sum_{i=1}^{n}\mathbf{A}_{1i}\mathbf{B}_{in}\\
\sum_{i=1}^{n}\mathbf{A}_{2i}\mathbf{B}_{i1} & \ddots &  & \vdots\\
\vdots &  & \ddots & \sum_{i=1}^{n}\mathbf{A}_{(m-1)i}\mathbf{B}_{in}\\
\sum_{i=1}^{n}\mathbf{A}_{mi}\mathbf{B}_{i1} & \dots & \sum_{i=1}^{n}\mathbf{A}_{mi}\mathbf{B}_{i(n-1)} & \sum_{i=1}^{n}\mathbf{A}_{mi}\mathbf{B}_{in}
\end{array}\right)\\
 & = & \left(\begin{array}{cccc}
\langle\mathbf{a}^{1},\mathbf{b}_{1}\rangle & \langle\mathbf{a}^{1},\mathbf{b}_{2}\rangle & \dots & \langle\mathbf{a}^{1},\mathbf{b}_{n}\rangle\\
\langle\mathbf{a}^{2},\mathbf{b}_{1}\rangle & \ddots &  & \vdots\\
\vdots &  & \ddots & \langle\mathbf{a}^{m-1},\mathbf{b}_{n}\rangle\\
\langle\mathbf{a}^{m},\mathbf{b}_{1}\rangle & \dots & \langle\mathbf{a}^{m},\mathbf{b}_{n-1}\rangle & \langle\mathbf{a}^{m},\mathbf{b}_{n}\rangle
\end{array}\right),
\end{eqnarray*}

\end_inset

where 
\begin_inset Formula $\mathbf{a}^{i}$
\end_inset

 denotes the 
\begin_inset Formula $i$
\end_inset

th row and 
\begin_inset Formula $\mathbf{b}_{j}$
\end_inset

 the 
\begin_inset Formula $j$
\end_inset

th column of 
\begin_inset Formula $\mathbf{A}$
\end_inset

 and 
\begin_inset Formula $\mathbf{B}$
\end_inset

, respectively.
 We can see from the definition of the matrix-matrix product that the number
 of columns of 
\begin_inset Formula $\mathbf{A}$
\end_inset


\series bold
 
\series default
and the number of rows of 
\begin_inset Formula $\mathbf{B}$
\end_inset

 must match.
\end_layout

\begin_layout Standard
\align right
\begin_inset Formula $\Diamond$
\end_inset


\end_layout

\begin_layout Subsubsection*
Notes
\end_layout

\begin_layout Itemize
We can multiply two matrices if the 'length' of the first matches the 'height'
 of the second: 
\begin_inset Formula $C=AB$
\end_inset

 is only defined if 
\begin_inset Formula $A$
\end_inset

 is of size 
\begin_inset Formula $m\times n$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

 is of size 
\begin_inset Formula $n\times k.$
\end_inset

 Then, the outcome 
\begin_inset Formula $C$
\end_inset

 will be of size 
\begin_inset Formula $m\times k.$
\end_inset

 ('Inner dimensions must match and drop out').
 
\end_layout

\begin_layout Itemize
Matrix multiplication is not commutative, in general, 
\begin_inset Formula $AB\neq BA!$
\end_inset

 Thinking of matrix multiplication as applying a linear functions, this
 makes a lot of sense: For example, suppose that our matrix 
\begin_inset Formula $A$
\end_inset

 swaps the first and second dimension of a two-dimensional vector, and that
 
\begin_inset Formula $B$
\end_inset

 doubles its first dimension.
 Clearly, it does matter whether we switch dimensions before or after doubling
 the first dimension.
 
\end_layout

\begin_layout Paragraph
Examples
\end_layout

\begin_layout Itemize
Let 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R} & = & \left(\begin{array}{cc}
0 & -1\\
1 & 0
\end{array}\right)
\end{eqnarray*}

\end_inset

as above.
 The product of 
\begin_inset Formula $\mathbf{R}$
\end_inset

 with itself is given by 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R\cdot R} & = & \left(\begin{array}{cc}
0 & -1\\
1 & 0
\end{array}\right)\left(\begin{array}{cc}
0 & -1\\
1 & 0
\end{array}\right)\\
 & = & \left(\begin{array}{cc}
\left\langle {0 \choose -1},{0 \choose 1}\right\rangle  & \left\langle {0 \choose -1},{-1 \choose 0}\right\rangle \\
\left\langle {1 \choose 0},{0 \choose 1}\right\rangle  & \left\langle {1 \choose 0},{-1 \choose 0}\right\rangle 
\end{array}\right)\\
 & = & \left(\begin{array}{cc}
1 & 0\\
0 & -1
\end{array}\right).
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
Let 
\begin_inset Formula $A=\left(\begin{array}{cc}
2 & 0\\
0 & 1
\end{array}\right),B=\left(\begin{array}{cc}
0 & 1\\
1 & 0
\end{array}\right)$
\end_inset

, then
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula 
\begin{eqnarray*}
AB & = & \left(\begin{array}{cc}
0 & 2\\
1 & 0
\end{array}\right),\\
BA & = & \left(\begin{array}{cc}
0 & 1\\
2 & 0
\end{array}\right).
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
Matrices do not have to be 'square' to be multiplied:
\begin_inset Formula 
\[
\left(\begin{array}{ccc}
1 & 0 & 1\\
3 & 2 & 1
\end{array}\right)\left(\begin{array}{cc}
1 & 0\\
1 & 1\\
1 & 2
\end{array}\right)=\left(\begin{array}{cc}
2 & 2\\
6 & 4
\end{array}\right).
\]

\end_inset


\begin_inset Formula 
\[
\]

\end_inset


\begin_inset Formula 
\[
\]

\end_inset


\end_layout

\begin_layout Itemize
Again, the identity matrix likes to be boring: Multiplying a 
\begin_inset Formula $m\times n$
\end_inset

 matrix 
\begin_inset Formula $\mathbf{A}$
\end_inset

 with the identity matrix 
\begin_inset Formula $\mathbf{I}_{m}$
\end_inset

 from the left or 
\begin_inset Formula $\mathbf{I}_{n}$
\end_inset

 from the right (
\begin_inset Formula $n$
\end_inset

 and 
\begin_inset Formula $m$
\end_inset

 denote the dimension of the identity matrix) leaves the matrix 
\begin_inset Formula $\mathbf{A}$
\end_inset

 unchanged, i.e.
 
\begin_inset Formula $\mathbf{AI}_{n}=\mathbf{I}_{m}\mathbf{A}=\mathbf{A}$
\end_inset

.
 
\end_layout

\begin_layout Itemize
We can derived the addition theorems for sine and cosine from the rule of
 matrix multiplication: Clearly, rotating a vector first by an angle of
 
\begin_inset Formula $\alpha$
\end_inset

, and then by 
\begin_inset Formula $\beta$
\end_inset

, should yield exactly the same result as rotating it by 
\begin_inset Formula $\alpha+\beta$
\end_inset

 in one go.
 If we denote the matrix which rotates by 
\begin_inset Formula $\alpha$
\end_inset

 by 
\begin_inset Formula $R(\alpha)$
\end_inset

, we get
\begin_inset Formula 
\begin{eqnarray*}
R(\alpha+\beta) & = & R(\alpha)R(\beta)\\
\left(\begin{array}{cc}
\cos(\alpha+\beta) & -\sin(\alpha+\beta)\\
\sin(\alpha+\beta) & \cos(\alpha+\beta)
\end{array}\right) & = & \left(\begin{array}{cc}
\cos(\alpha) & -\sin(\alpha)\\
\sin(\alpha) & \cos(\alpha)
\end{array}\right)\left(\begin{array}{cc}
\cos(\beta) & -\sin(\beta)\\
\sin(\beta) & \cos(\beta)
\end{array}\right)\\
 & = & \left(\begin{array}{cc}
\cos(\alpha)\cos(\beta)-\sin(\alpha)\sin(\beta) & -\cos(\alpha)\sin(\beta)-\cos(\beta)\sin(\alpha)\\
\cos(\alpha)\sin(\beta)+\cos(\beta)\sin(\alpha) & \cos(\alpha)\cos(\beta)-\sin(\alpha)\sin(\beta)
\end{array}\right).
\end{eqnarray*}

\end_inset

Equation coefficients, we recover the addition theorems 
\begin_inset Formula 
\begin{eqnarray*}
\cos(\alpha+\beta) & = & \cos(\alpha)\cos(\beta)-\sin(\alpha)\sin(\beta)\\
\sin(\alpha+\beta) & = & \sin(\alpha)\cos(\beta)+\cos(\alpha)\sin(\beta).
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
Assume that we are searching for a matrix that projects a vector 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{3}$
\end_inset

 onto the 
\begin_inset Formula $x_{1}x_{2}$
\end_inset

-plane and rotates the result by 
\begin_inset Formula $30^{\circ}$
\end_inset

around the origin.
 We can get this matrix 
\begin_inset Formula $\mathbf{C}$
\end_inset

 by multiplying the rotation matrix 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R} & = & \left(\begin{array}{cc}
\cos(30^{\circ}) & -\sin(30^{\circ})\\
\sin(30^{\circ}) & \cos(30^{\circ})
\end{array}\right)
\end{eqnarray*}

\end_inset

 with the projection matrix 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{P} & = & \left(\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0
\end{array}\right).
\end{eqnarray*}

\end_inset

The result is given by 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{R}\cdot\mathbf{P} & = & \left(\begin{array}{ccc}
\cos(30^{\circ}) & -\sin(30^{\circ}) & 0\\
\sin(30^{\circ}) & \cos(30^{\circ}) & 0
\end{array}\right).
\end{eqnarray*}

\end_inset

Note that the order in which we multiply the matrices is the reverse order
 in which we apply the transformations, i.e.
 projection and rotation.
 The reason is simply that a vector 
\begin_inset Formula $\mathbf{x}$
\end_inset

 is multiplied with 
\begin_inset Formula $\mathbf{R}\cdot\mathbf{P}$
\end_inset

 from the right, which means that it is multiplied with 
\begin_inset Formula $\mathbf{P}$
\end_inset

 first and with 
\begin_inset Formula $\mathbf{R}$
\end_inset

 afterwards.
 This is exactly the order in which we wanted to apply the transformations.
\end_layout

\begin_layout Standard
\align right
\begin_inset Formula $\lhd$
\end_inset


\end_layout

\begin_layout Standard
With the rule for matrix-matrix multiplication we can also multiply a vector
 from the left to a matrix.
 However, since the number of columns of the first matrix must match the
 number of row of the second matrix in a product, we cannot use column vectors,
 but only row vectors.
 This is one example, where it makes a difference if we have a row or a
 column vector.
 Since a row vector 
\begin_inset Formula $\mathbf{x}=(x_{1},...,x_{m})$
\end_inset

 can be treated as a 
\begin_inset Formula $1\times m$
\end_inset

-matrix, we can apply the rule for matrix-matrix multiplication and obtain
 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{x}\mathbf{A} & = & (x_{1},...,x_{n})\cdot\mathbf{A}\\
 & = & (\langle\mathbf{x},\mathbf{a}_{1}\rangle,...,\langle\mathbf{x},\mathbf{a}_{k}\rangle),
\end{eqnarray*}

\end_inset

if 
\begin_inset Formula $\mathbf{a}_{i}$
\end_inset

 denotes the 
\begin_inset Formula $i$
\end_inset

th column of 
\begin_inset Formula $\mathbf{A}$
\end_inset

 as before.
\end_layout

\begin_layout Subsubsection
Matrix Transposition
\end_layout

\begin_layout Standard
It is often convenient (or necessary) to 'flip' a matrix or a vector by
 exchanging its rows and columns.
 For example, we might want to write a column vector 
\begin_inset Formula $n\times1$
\end_inset

 as a row vector of size 
\begin_inset Formula $1\times n$
\end_inset

.
 Formally, this operation is called 'taking the transpose':
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\]

\end_inset


\end_layout

\begin_layout Paragraph
Definition (Matrix Transpose)
\end_layout

\begin_layout Standard
The 
\emph on

\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
transpose
\end_layout

\end_inset

transpose
\emph default
 of a matrix 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{A} & = & \left(\begin{array}{cccc}
\mathbf{A}_{11} & \mathbf{A}_{12} &  & \mathbf{A}_{1n}\\
\mathbf{A}_{21}\\
\vdots &  &  & \mathbf{A}_{(m-1)n}\\
\mathbf{A}_{m1} &  & \mathbf{A}_{m(n-1)} & \mathbf{A}_{mn}
\end{array}\right)
\end{eqnarray*}

\end_inset

is given by 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{A}^{\top} & = & \left(\begin{array}{cccc}
\mathbf{A}_{11} & \mathbf{A}_{21} &  & \mathbf{A}_{m1}\\
\mathbf{A}_{12}\\
\vdots &  &  & \mathbf{A}_{m(n-1)}\\
\mathbf{A}_{1n} &  & \mathbf{A}_{(m-1)n} & \mathbf{A}_{mn}
\end{array}\right).
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
If 
\begin_inset Formula $A$
\end_inset

 is of size 
\begin_inset Formula $m\times n,$
\end_inset

 
\begin_inset Formula $A^{\top}$
\end_inset

is of size 
\begin_inset Formula $n\times m.$
\end_inset


\end_layout

\begin_layout Subsubsection*
Note
\end_layout

\begin_layout Itemize
The usual dot-product between two vectors can be written as 
\begin_inset Formula $\langle v,w\rangle=v^{\top}w$
\end_inset

.
\end_layout

\begin_layout Itemize
If we take the transpose of a product, we have to reverse the order: 
\begin_inset Formula $(ABC)^{\top}=C^{\top}B^{\top}A^{\top}.$
\end_inset


\end_layout

\begin_layout Standard
\align right
\begin_inset Formula $\Diamond$
\end_inset


\end_layout

\begin_layout Subsubsection
Symmetric Matrices, Covariance Matrix and Outer Product of Vectors and Matrices
\end_layout

\begin_layout Standard
In this section we look at a special way of using the matrix notation that
 might not be immediately obvious when looking at the calculation rules
 for the first time.
 This way of using the matrix notation is especially useful for computing
 covariance matrices.
 Therefore, will develop the idea of the 
\emph on
outer product
\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
outer product
\end_layout

\end_inset


\emph default
 with the example of computing a covariance matrix in matrix notation.
 Let us start with the definition of a covariance matrix.
\end_layout

\begin_layout Paragraph
Definition (Covariance Matrix)
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $\mathsf{\bm{X}}=(\mathsf{X}_{1},...,\mathsf{X}_{n})^{\top}$
\end_inset

 be an 
\begin_inset Formula $n$
\end_inset

-dimensional random variable.
 The covariance of dimension 
\begin_inset Formula $i$
\end_inset

 with dimension 
\begin_inset Formula $j$
\end_inset

 is given by 
\begin_inset Formula 
\begin{eqnarray*}
Cov(\mathsf{X}_{i},\mathsf{X}_{j}) & = & E\left((\mathsf{X}_{i}-E(\mathsf{X}_{i}))\cdot(\mathsf{X}_{j}-E(\mathsf{X}_{j}))\right)\\
 & = & E(\mathsf{X}_{i}\cdot\mathsf{X}_{j})-E(\mathsf{X}_{i})\cdot E(\mathsf{X}_{j}).
\end{eqnarray*}

\end_inset

The covariance tells us how 
\begin_inset Formula $\mathsf{X}_{i}$
\end_inset

 behaves if we change 
\begin_inset Formula $\mathsf{X}_{j}$
\end_inset

 and vice versa.
 The single covariances can be put together in the 
\emph on

\begin_inset Formula $n\times n$
\end_inset

 
\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
covariance matrix
\end_layout

\end_inset

covariance matrix
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{C} & = & \left(\begin{array}{ccc}
Cov(\mathsf{X}_{1},\mathsf{X}_{1}) & \dots & Cov(\mathsf{X}_{1},\mathsf{X}_{n})\\
\vdots & \ddots & \vdots\\
Cov(\mathsf{X}_{n},\mathsf{X}_{1}) & \ldots & Cov(\mathsf{X}_{n},\mathsf{X}_{n})
\end{array}\right)\\
 & = & \left(\begin{array}{ccc}
Var(\mathsf{X}_{1}) & \dots & Cov(\mathsf{X}_{1},\mathsf{X}_{n})\\
\vdots & \ddots & \vdots\\
Cov(\mathsf{X}_{n},\mathsf{X}_{1}) & \ldots & Var(\mathsf{X}_{n})
\end{array}\right).
\end{eqnarray*}

\end_inset


\emph default
Empirically, i.e.
 given 
\begin_inset Formula $N$
\end_inset

 sample vectors 
\begin_inset Formula $\mathbf{x}_{1},...,\mathbf{x}_{n}$
\end_inset

, the single covariances can be computed via 
\begin_inset Formula 
\begin{eqnarray*}
\hat{Cov}(\mathsf{X}_{i},\mathsf{X}_{j}) & = & \frac{1}{N}\sum_{\ell=1}^{N}(x_{\ell i}-\mu_{i})(x_{\ell j}-\mu_{j})\\
 & = & \hat{\mathbf{C}}_{ij}.
\end{eqnarray*}

\end_inset

 
\end_layout

\begin_layout Standard
\align right
\begin_inset Formula $\Diamond$
\end_inset


\end_layout

\begin_layout Standard
For simplicity, let us assume that our sample has mean zero, i.e.
 
\begin_inset Formula $\bm{\mu}=0$
\end_inset

.
 This is no restriction since we can always subtract 
\begin_inset Formula $\bm{\mu}$
\end_inset

 from each 
\begin_inset Formula $\mathbf{x}_{i}$
\end_inset

 in order to center them around zero.
 For 
\begin_inset Formula $\bm{\mu}=0$
\end_inset

, the above equation for the empirical mean becomes
\begin_inset Formula 
\begin{eqnarray*}
\hat{Cov}(\mathsf{X}_{i},\mathsf{X}_{j}) & = & \frac{1}{N}\sum_{\ell=1}^{N}x_{\ell i}x_{\ell j}\\
 & = & \hat{\mathbf{C}}_{ij}.
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
Here, we use the hat on a variable to indicate that it has been estimated
 from empirical data.
 Covariance matrices have a certain property: They are 
\emph on
symmetric
\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
symmetric matrix
\end_layout

\end_inset


\emph default
, i.e.
 the original matrix equals its transpose 
\begin_inset Formula $\mathbf{C}=\mathbf{C}^{\top}$
\end_inset

.
 Symmetric matrices have certain nice properties that we will encounter
 later in the section about eigenvalues and eigenvectors.
\end_layout

\begin_layout Standard
Now let us return to the question of how to express the computation of the
 empirical covariance matrix with a single matrix multiplication.
 We do that in two steps: first we see how to generate the inner term 
\begin_inset Formula $x_{\ell i}x_{\ell j}$
\end_inset

 of the sum 
\begin_inset Formula $\frac{1}{N}\sum_{\ell=1}^{N}x_{\ell i}x_{\ell j}$
\end_inset

 and then expand this idea in order to get the full empirical covariance
 matrix.
 To answer the first question, we must find an operation of a vector 
\begin_inset Formula $\mathbf{x}_{\ell}$
\end_inset

 with itself such that the result is a matrix 
\begin_inset Formula $\tilde{\mathbf{C}}^{(\ell)}$
\end_inset

 with the entries 
\begin_inset Formula $\tilde{\mathbf{C}}_{ij}^{(\ell)}=x_{\ell i}x_{\ell j}$
\end_inset

.
 The crucial observation for that is that we can interpret a single entry
 
\begin_inset Formula $x_{\ell i}$
\end_inset

 as a 
\begin_inset Formula $1\times1$
\end_inset

 vector.
 With this in mind, we can apply the matrix product rule to the term 
\begin_inset Formula $\mathbf{x}_{\ell}\mathbf{x}_{\ell}^{\top}$
\end_inset

.
 The dot product between the row and the column vector simply becomes a
 multiplication of two scalars 
\begin_inset Formula $x_{\ell i}x_{\ell j}$
\end_inset

.
 Note, that the vectors have the reverse order than in the dot product,
 i.e.
 the column vector is the first factor and the row vector is the second
 factor.
 The result of this 
\emph on

\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
outer product
\end_layout

\end_inset

outer product
\emph default
 is the desired matrix: 
\begin_inset Formula 
\begin{eqnarray*}
\tilde{\mathbf{C}}^{(\ell)} & = & \mathbf{x}_{\ell}\mathbf{x}_{\ell}^{\top}\\
 & = & \left(\begin{array}{ccc}
x_{\ell1}x_{\ell1} & \dots & x_{\ell1}x_{\ell n}\\
\vdots & \ddots & \vdots\\
x_{\ell n}x_{\ell1} & \ldots & x_{\ell n}x_{\ell n}
\end{array}\right).
\end{eqnarray*}

\end_inset

Looking at the term for the empirical covariance matrix, we see that it
 can now be computed via
\begin_inset Formula 
\begin{eqnarray*}
\hat{\mathbf{C}} & =\frac{1}{N} & \sum_{\ell=1}^{N}\tilde{\mathbf{C}}^{(\ell)}.
\end{eqnarray*}

\end_inset

In order to be able to express this sum as multiplication of two matrices,
 we must arrange our data in an matrix such that the sum of the matrix multiplic
ation equals the above sum.
 Placing all our measurements 
\begin_inset Formula $\mathbf{x}_{1},...,\mathbf{x}_{N}$
\end_inset

 as rows in a 
\begin_inset Formula $N\times n$
\end_inset

 matrix 
\begin_inset Formula $\mathbf{X}=(\mathbf{x}_{1},...,\mathbf{x}_{N})^{\top}$
\end_inset

, we can see that 
\begin_inset Formula 
\begin{eqnarray*}
\mathbf{X}^{\top}\mathbf{X} & = & \sum_{\ell=1}^{N}\tilde{\mathbf{C}}^{(\ell)}.
\end{eqnarray*}

\end_inset

In order to see this, we must realize that an entry 
\begin_inset Formula $(\mathbf{X}^{\top}\mathbf{X})_{ij}$
\end_inset

 is given by the dot product between an 
\begin_inset Formula $N$
\end_inset

-dimensional vector that contains the 
\begin_inset Formula $i$
\end_inset

th entry of all our measurements and a vector of the same size that contains
 the 
\begin_inset Formula $j$
\end_inset

th entry of all our measurements, i.e.
 
\begin_inset Formula 
\begin{eqnarray*}
(\mathbf{X}^{\top}\mathbf{X})_{ij} & = & (x_{1i},x_{2i},...,x_{Ni})\cdot(x_{1j},x_{2j},...,x_{Nj})=\sum_{\ell=1}^{N}x_{\ell i}x_{\ell j}.
\end{eqnarray*}

\end_inset

This is exactly what we intended.
 Therefore, computing the covariance matrix from 
\begin_inset Formula $N$
\end_inset

 measurements from an 
\begin_inset Formula $n$
\end_inset

-dimensional random variable by a single matrix multiplication can be done
 via 
\begin_inset Formula 
\begin{eqnarray*}
\hat{\mathbf{C}} & = & \frac{1}{N}\mathbf{X}^{\top}\mathbf{X}.
\end{eqnarray*}

\end_inset


\end_layout

\end_body
\end_document