\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, October 06, 2019 02:48:12}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\allowdisplaybreaks
\ihead{Math 201-003 Fall 2019 (Darij Grinberg): homework set 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 201-003 Fall 2019 (Darij Grinberg): homework set 1 with
solutions}
\end{center}

\begin{exercise}
\label{exe.augmat.examps4}\textbf{(a)} Write down the augmented matrix
corresponding to the following system of linear equations:%
\[%
\begin{cases}
3x-6y+z=5\\
y-2z=8\\
y-3z=1\\
2z=5
\end{cases}
.
\]


\textbf{(b)} Write down the system of linear equations that corresponds to the
following augmented matrix:%
\[
\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & \mathbf{1}\\
2 & 3 & 4 & \mathbf{2}\\
3 & 4 & 5 & \mathbf{3}%
\end{array}
\right)  .
\]
(Here, as in class, we are putting the entries of the last column in boldface
instead of drawing a vertical bar to the left of them.)

\textbf{(c)} Find the RREF of the matrix in part \textbf{(a)}.

\textbf{(d)} Solve the system of linear equations in part \textbf{(a)}.

\textbf{(e)} Find the RREF of the matrix in part \textbf{(b)}.

\textbf{(f)} Solve the system of linear equations in part \textbf{(b)}.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.augmat.examps4}.]\textbf{(a)} The augmented
matrix is $\left(
\begin{array}
[c]{cccc}%
3 & -6 & 1 & \mathbf{5}\\
0 & 1 & -2 & \mathbf{8}\\
0 & 1 & -3 & \mathbf{1}\\
0 & 0 & 2 & \mathbf{5}%
\end{array}
\right)  $.

\textbf{(b)} The system is $\left\{
\begin{array}
[c]{c}%
x+2y+3z=1\\
2x+3y+4z=2\\
3x+4y+5z=3
\end{array}
\right.  $.

\textbf{(c)} We shall mark the pivot entries by putting them in boxes. Note
that the following is only one way of performing the row-reduction algorithm
(\cite[Method 6.3]{Strickland}); there are others (since you have freedom in
pivoting).%
\begin{align*}
&  \left(
\begin{array}
[c]{cccc}%
\fbox{$3$} & -6 & 1 & 5\\
0 & 1 & -2 & 8\\
0 & 1 & -3 & 1\\
0 & 0 & 2 & 5
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }1/3}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & -3 & 1/3 & 5/3\\
0 & 1 & -2 & 8\\
0 & 1 & -3 & 1\\
0 & 0 & 2 & 5
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & 1 & -2 & 8 & \\
0 & 1 & -3 & 1 & \\
0 & 0 & 2 & 5 &
\end{array}
\right) \\
&  \underset{\text{(remember that frozen rows don't count!)}%
}{\overset{\text{add }-1\text{ times row }1\text{ to row }2}{\longrightarrow}%
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \\
0 & 0 & -1 & -7 & \\
0 & 0 & 2 & 5 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \leftarrow\text{frozen}\\
0 & 0 & -1 & -7 & \\
0 & 0 & 2 & 5 &
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }-1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 7 & \\
0 & 0 & 2 & 5 &
\end{array}
\right) \\
&  \overset{\text{add }-2\text{ times row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 7 & \\
0 & 0 & 0 & -9 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 7 & \leftarrow\text{frozen}\\
0 & 0 & 0 & -9 &
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }-1/9}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 7 & \leftarrow\text{frozen}\\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 7 & \\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{before this step, we should have frozen row }1\text{ and}\\
\text{then unfrozen it again, but this changes nothing}%
\end{array}
\right) \\
&  \overset{\text{add }-7\text{ times row }2\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \leftarrow\text{frozen}\\
0 & 0 & \fbox{$1$} & 0 & \\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & -2 & 8 & \\
0 & 0 & \fbox{$1$} & 0 & \\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right) \\
&  \overset{\text{add }2\text{ times row }2\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 8 & \\
0 & 0 & \fbox{$1$} & 0 & \\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right) \\
&  \overset{\text{add }-8\text{ times row }3\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & -3 & 1/3 & 5/3 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 0 & 0 & \\
0 & 0 & \fbox{$1$} & 0 & \\
0 & 0 & 0 & \fbox{$1$} &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & -3 & 1/3 & 5/3\\
0 & \fbox{$1$} & 0 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & \fbox{$1$}%
\end{array}
\right) \\
&  \overset{\text{add }3\text{ times row }2\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 1/3 & 5/3\\
0 & \fbox{$1$} & 0 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & \fbox{$1$}%
\end{array}
\right) \\
&  \overset{\text{add }-1/3\text{ times row }3\text{ to row }%
1}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 5/3\\
0 & \fbox{$1$} & 0 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & \fbox{$1$}%
\end{array}
\right) \\
&  \overset{\text{add }-5/3\text{ times row }4\text{ to row }%
1}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 0\\
0 & \fbox{$1$} & 0 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & \fbox{$1$}%
\end{array}
\right)  .
\end{align*}
This is a matrix in RREF.

\textbf{(d)} The RREF we have just obtained has a pivot in its last column.
Thus, the system of linear equations contains an equation saying $0=1$, and
therefore has no solutions. (See \cite[Method 5.4 (b)]{Strickland} for the
logic we are using here.)

\textbf{(e)} We shall mark the pivot entries by putting them in boxes. Note
that the following is only one way of performing the row-reduction algorithm
(\cite[Method 6.3]{Strickland}); there are others (since you have freedom in
pivoting).%
\begin{align*}
&  \left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 2 & 3 & 1\\
2 & 3 & 4 & 2\\
3 & 4 & 5 & 3
\end{array}
\right) \\
&  \overset{\text{add }-2\text{ times row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 2 & 3 & 1\\
0 & -1 & -2 & 0\\
3 & 4 & 5 & 3
\end{array}
\right) \\
&  \overset{\text{add }-3\text{ times row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 2 & 3 & 1\\
0 & -1 & -2 & 0\\
0 & -2 & -4 & 0
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 3 & 1 & \leftarrow\text{frozen}\\
0 & -1 & -2 & 0 & \\
0 & -2 & -4 & 0 &
\end{array}
\right) \\
&  \overset{\text{scale row }1\text{ by }-1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 3 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 0 & \\
0 & -2 & -4 & 0 &
\end{array}
\right) \\
&  \overset{\text{add }2\text{ times row }1\text{ to row }2}{\longrightarrow
}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 3 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 0 & \\
0 & 0 & 0 & 0 &
\end{array}
\right) \\
&  \overset{\text{freeze row }1}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 3 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 0 & \leftarrow\text{frozen}\\
0 & 0 & 0 & 0 &
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{ccccc}%
\fbox{$1$} & 2 & 3 & 1 & \leftarrow\text{frozen}\\
0 & \fbox{$1$} & 2 & 0 & \\
0 & 0 & 0 & 0 &
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{we are starting to unfreeze, since we have}\\
\text{obtained a matrix with no nonzero entries}%
\end{array}
\right) \\
&  \overset{\text{unfreeze last frozen row}}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 2 & 3 & 1\\
0 & \fbox{$1$} & 2 & 0\\
0 & 0 & 0 & 0
\end{array}
\right) \\
&  \overset{\text{add }-2\text{ times row }2\text{ to row }1}{\longrightarrow
}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & -1 & 1\\
0 & \fbox{$1$} & 2 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  .
\end{align*}
This is a matrix in RREF.

\textbf{(f)} We have just row-reduced the matrix that corresponds to the
system, and obtained $\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & -1 & 1\\
0 & \fbox{$1$} & 2 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  $. Hence, the system is equivalent to the system%
\[
\left\{
\begin{array}
[c]{c}%
x-z=1\\
y+2z=0\\
0=0
\end{array}
\right.
\]
(where we are labeling the variables by $x,y,z$). This system has one free
variable, namely $z$ (because the third column of the above matrix contains no
pivot); the two other variables (that is, $x$ and $y$) are dependent variables
(because the first two columns of the above matrix contain pivots). Thus, its
solution is given by%
\[
x=1+z\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ y=-2z,
\]
with $z$ an arbitrary number. (See \cite[Method 5.4 (d)]{Strickland} for the
logic we have used here.)
\end{proof}

\begin{exercise}
\label{exe.matrix.CD-Cv}Consider the two matrices
\[
C=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ D=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
-1 & 1 & 0 & 0\\
0 & -1 & 1 & 0\\
0 & 0 & -1 & 1
\end{array}
\right)  .
\]


Let $v=\left(
\begin{array}
[c]{c}%
a\\
b\\
c\\
d
\end{array}
\right)  $ be any column vector of size $4$.

\textbf{(a)} Compute $Cv$.

\textbf{(b)} Compute $Dv$.

\textbf{(c)} Compute $CD$.

\textbf{(d)} Compute $DC$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.matrix.CD-Cv}.]\textbf{(a)} From $C=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1
\end{array}
\right)  $ and $v=\left(
\begin{array}
[c]{c}%
a\\
b\\
c\\
d
\end{array}
\right)  $, we obtain%
\[
Cv=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
a\\
b\\
c\\
d
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
1a+0b+0c+0d\\
1a+1b+0c+0d\\
1a+1b+1c+0d\\
1a+1b+1c+1d
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
a\\
a+b\\
a+b+c\\
a+b+c+d
\end{array}
\right)  .
\]


\textbf{(b)} From $D=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
-1 & 1 & 0 & 0\\
0 & -1 & 1 & 0\\
0 & 0 & -1 & 1
\end{array}
\right)  $ and $v=\left(
\begin{array}
[c]{c}%
a\\
b\\
c\\
d
\end{array}
\right)  $, we obtain%
\[
Dv=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
-1 & 1 & 0 & 0\\
0 & -1 & 1 & 0\\
0 & 0 & -1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
a\\
b\\
c\\
d
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
1a+0b+0c+0d\\
\left(  -1\right)  a+1b+0c+0d\\
0a+\left(  -1\right)  b+1c+0d\\
0a+0b+\left(  -1\right)  c+1d
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
a\\
b-a\\
c-b\\
d-c
\end{array}
\right)  .
\]


\textbf{(c)} From $C=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1
\end{array}
\right)  $ and $D=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
-1 & 1 & 0 & 0\\
0 & -1 & 1 & 0\\
0 & 0 & -1 & 1
\end{array}
\right)  $, we obtain%
\begin{align*}
CD  &  =\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
-1 & 1 & 0 & 0\\
0 & -1 & 1 & 0\\
0 & 0 & -1 & 1
\end{array}
\right)  =\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by directly applying the definition of the}\\
\text{product of two matrices, and simplifying}%
\end{array}
\right) \\
&  =I_{4}.
\end{align*}


\textbf{(d)} Similarly, a computation shows that $DC=I_{4}$.

[\textit{Remark:} The answers to parts \textbf{(a)} and \textbf{(b)} can be
restated as follows:

\begin{itemize}
\item The vector $Cv$ is obtained from $v$ by \textbf{cumulating} the entries
of $v$ from top to bottom.

\item The vector $Dv$ is obtained from $v$ by taking \textbf{differences}
between consecutive entries of $v$.
\end{itemize}

\noindent This is why we called the matrices $C$ and $D$. More usefully, this
gives an alternative explanation for why $CD=I_{4}$ and $DC=I_{4}$, without
having to actually multiply out the matrices. Indeed, any matrix $A$ is
uniquely determined by its products with all column vectors; in other words,
if $A_{1}$ and $A_{2}$ are two $n\times m$-matrices such that%
\begin{equation}
A_{1}v=A_{2}v\ \ \ \ \ \ \ \ \ \ \text{for all }v\in\mathbb{R}^{m},
\label{sol.matrix.CD-Cv.A1v=A2v}%
\end{equation}
then $A_{1}=A_{2}$.\ \ \ \ \footnote{This is not hard to prove (we will do
this in class). Just fix any $j\in\left\{  1,2,\ldots,m\right\}  $, and apply
the assumption (\ref{sol.matrix.CD-Cv.A1v=A2v}) to $v=\left(  0,0,\ldots
,0,1,0,0,\ldots,0\right)  ^{T}$ (where the $1$ is in the $j$-th position of
the vector); the result will say that the $j$-th column of $A_{1}$ equals the
$j$-th column of $A_{2}$. Since this holds for all $j\in\left\{
1,2,\ldots,m\right\}  $, we can thus conclude that $A_{1}=A_{2}$.} Thus, in
order to prove that $CD=I_{4}$, it suffices to show that $CDv=I_{4}v$ for all
$v\in\mathbb{R}^{4}$. But this is easy: Due to what we have just said about
$C$ and $D$, we see that

\begin{itemize}
\item the vector $Dv$ is obtained from $v$ by taking differences between
consecutive entries of $v$, and

\item the vector $CDv$ is obtained from $Dv$ by cumulating the entries of $v$
from top to bottom.
\end{itemize}

\noindent But this procedure (in which we first take differences between
consecutive entries, and then cumulate these differences) just returns our
original vector $v$, which of course is the same as $I_{4}v$. Thus,
$CDv=I_{4}v$. Since this holds for all $v\in\mathbb{R}^{4}$, we thus conclude
that $CD=I_{4}$. Likewise, $DC=I_{4}$, because cumulating and then taking
consecutive difference is another way to get the original vector back.]
\end{proof}

\begin{definition}
Let $A$ be any square matrix. Then, the \textit{trace} of $A$ is defined to be
the sum of all diagonal entries of $A$. In other words, it is defined to be
$A_{1,1}+A_{2,2}+\cdots+A_{n,n}$, where $n\in\mathbb{N}$ is such that $A$ is
an $n\times n$-matrix.

The trace of $A$ is denoted by $\operatorname*{Tr}A$.
\end{definition}

For example, here is what the traces of $2\times2$-matrices and $3\times
3$-matrices are:%
\[
\operatorname*{Tr}\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  =a+b^{\prime};\ \ \ \ \ \ \ \ \ \ \operatorname*{Tr}\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  =a+b^{\prime}+c^{\prime\prime}.
\]


\begin{exercise}
\label{exe.TrAB.23}\textbf{(a)} Prove that $\operatorname*{Tr}\left(
AB\right)  =\operatorname*{Tr}\left(  BA\right)  $ for any two $2\times
2$-matrices $A$ and $B$.

\textbf{(b)} Prove that $\operatorname*{Tr}\left(  AB\right)
=\operatorname*{Tr}\left(  BA\right)  $ for any two $3\times3$-matrices $A$
and $B$.

[\textbf{Hint:} In part \textbf{(a)}, you can set $A=\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  $ and compute both $\operatorname*{Tr}\left(  AB\right)  $ and
$\operatorname*{Tr}\left(  BA\right)  $ and check their equality. Likewise for
part \textbf{(b)}. Alternatively, you can show that $\operatorname*{Tr}\left(
AB\right)  =\operatorname*{Tr}\left(  BA\right)  $ for any $n\times
n$-matrices $A$ and $B$ of any size $n$. In the latter case, you will want to
be familiar with the basics of summation signs \cite[\S 2.9]{lina}.)
\end{exercise}

\begin{proof}
[First solution to Exercise \ref{exe.TrAB.23}.]\textbf{(a)} Let $A$ and $B$ be
two $2\times2$-matrices. Write $A$ and $B$ as $A=\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  $. Thus,%
\[
AB=\left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
ax+bx^{\prime} & ay+by^{\prime}\\
a^{\prime}x+b^{\prime}x^{\prime} & a^{\prime}y+b^{\prime}y^{\prime}%
\end{array}
\right)  ,
\]
so that the definition of a trace yields
\begin{equation}
\operatorname*{Tr}\left(  AB\right)  =\left(  ax+bx^{\prime}\right)  +\left(
a^{\prime}y+b^{\prime}y^{\prime}\right)  . \label{sol.TrAB.23.AB}%
\end{equation}
Also,
\[
BA=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
a & b\\
a^{\prime} & b^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
xa+ya^{\prime} & xb+yb^{\prime}\\
x^{\prime}a+y^{\prime}a^{\prime} & x^{\prime}b+y^{\prime}b^{\prime}%
\end{array}
\right)  ,
\]
so that the definition of a trace yields
\begin{equation}
\operatorname*{Tr}\left(  BA\right)  =\left(  xa+ya^{\prime}\right)  +\left(
x^{\prime}b+y^{\prime}b^{\prime}\right)  . \label{sol.TrAB.23.BA}%
\end{equation}


We need to prove that $\operatorname*{Tr}\left(  AB\right)
=\operatorname*{Tr}\left(  BA\right)  $. In view of the equalities
(\ref{sol.TrAB.23.AB}) and (\ref{sol.TrAB.23.BA}), this rewrites as
\[
\left(  ax+bx^{\prime}\right)  +\left(  a^{\prime}y+b^{\prime}y^{\prime
}\right)  =\left(  xa+ya^{\prime}\right)  +\left(  x^{\prime}b+y^{\prime
}b^{\prime}\right)  .
\]
But verifying this is a matter of straightforward computation:%
\begin{align*}
\left(  ax+bx^{\prime}\right)  +\left(  a^{\prime}y+b^{\prime}y^{\prime
}\right)   &  =\underbrace{ax}_{=xa}+\underbrace{bx^{\prime}}_{=x^{\prime}%
b}+\underbrace{a^{\prime}y}_{=ya^{\prime}}+\underbrace{b^{\prime}y^{\prime}%
}_{=y^{\prime}b^{\prime}}\\
&  =xa+x^{\prime}b+ya^{\prime}+y^{\prime}b^{\prime}=\left(  xa+ya^{\prime
}\right)  +\left(  x^{\prime}b+y^{\prime}b^{\prime}\right)  .
\end{align*}
Thus, $\operatorname*{Tr}\left(  AB\right)  =\operatorname*{Tr}\left(
BA\right)  $ is proven. This solves Exercise \ref{exe.TrAB.23} \textbf{(a)}.

Before we solve part \textbf{(b)}, let us make a simple but useful
observation: We did not need to compute the two off-diagonal entries of $AB$
and $BA$, since the trace of a matrix only depends on its diagonal entries.
This will save us some work in our solution to part \textbf{(b)}:

\textbf{(b)} Let $A$ and $B$ be two $3\times3$-matrices. Write $A$ and $B$ as
$A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{ccc}%
x & y & z\\
x^{\prime} & y^{\prime} & z^{\prime}\\
x^{\prime\prime} & y^{\prime\prime} & z^{\prime\prime}%
\end{array}
\right)  $. Thus,%
\begin{align*}
AB  &  =\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{ccc}%
x & y & z\\
x^{\prime} & y^{\prime} & z^{\prime}\\
x^{\prime\prime} & y^{\prime\prime} & z^{\prime\prime}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{ccc}%
ax+bx^{\prime}+cx^{\prime\prime} & \ast & \ast\\
\ast & a^{\prime}y+b^{\prime}y^{\prime}+c^{\prime}y^{\prime\prime} & \ast\\
\ast & \ast & a^{\prime\prime}z+b^{\prime\prime}z^{\prime}+c^{\prime\prime
}z^{\prime\prime}%
\end{array}
\right)  ,
\end{align*}
where the \textquotedblleft$\ast$\textquotedblright\ symbols stand for entries
that we don't want to compute. Thus, the definition of a trace yields
\begin{equation}
\operatorname*{Tr}\left(  AB\right)  =\left(  ax+bx^{\prime}+cx^{\prime\prime
}\right)  +\left(  a^{\prime}y+b^{\prime}y^{\prime}+c^{\prime}y^{\prime\prime
}\right)  +\left(  a^{\prime\prime}z+b^{\prime\prime}z^{\prime}+c^{\prime
\prime}z^{\prime\prime}\right)
.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \label{sol.TrAB.23.AB3}%
\end{equation}
A similar computation of $BA$ shows that%
\begin{equation}
\operatorname*{Tr}\left(  BA\right)  =\left(  xa+ya^{\prime}+za^{\prime\prime
}\right)  +\left(  x^{\prime}b+y^{\prime}b^{\prime}+z^{\prime}b^{\prime\prime
}\right)  +\left(  x^{\prime\prime}c+y^{\prime\prime}c^{\prime}+z^{\prime
\prime}c^{\prime\prime}\right)
.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \label{sol.TrAB.23.BA3}%
\end{equation}


We need to prove that $\operatorname*{Tr}\left(  AB\right)
=\operatorname*{Tr}\left(  BA\right)  $. In view of the equalities
(\ref{sol.TrAB.23.AB3}) and (\ref{sol.TrAB.23.BA3}), this rewrites as
\begin{align*}
&  \left(  ax+bx^{\prime}+cx^{\prime\prime}\right)  +\left(  a^{\prime
}y+b^{\prime}y^{\prime}+c^{\prime}y^{\prime\prime}\right)  +\left(
a^{\prime\prime}z+b^{\prime\prime}z^{\prime}+c^{\prime\prime}z^{\prime\prime
}\right) \\
&  =\left(  xa+ya^{\prime}+za^{\prime\prime}\right)  +\left(  x^{\prime
}b+y^{\prime}b^{\prime}+z^{\prime}b^{\prime\prime}\right)  +\left(
x^{\prime\prime}c+y^{\prime\prime}c^{\prime}+z^{\prime\prime}c^{\prime\prime
}\right)  .
\end{align*}
But verifying this is a matter of straightforward computation:%
\begin{align*}
&  \left(  ax+bx^{\prime}+cx^{\prime\prime}\right)  +\left(  a^{\prime
}y+b^{\prime}y^{\prime}+c^{\prime}y^{\prime\prime}\right)  +\left(
a^{\prime\prime}z+b^{\prime\prime}z^{\prime}+c^{\prime\prime}z^{\prime\prime
}\right) \\
&  =\underbrace{ax}_{=xa}+\underbrace{bx^{\prime}}_{=x^{\prime}b}%
+\underbrace{cx^{\prime\prime}}_{=x^{\prime\prime}c}+\underbrace{a^{\prime}%
y}_{=ya^{\prime}}+\underbrace{b^{\prime}y^{\prime}}_{=y^{\prime}b^{\prime}%
}+\underbrace{c^{\prime}y^{\prime\prime}}_{=y^{\prime\prime}c^{\prime}%
}+\underbrace{a^{\prime\prime}z}_{=za^{\prime\prime}}+\underbrace{b^{\prime
\prime}z^{\prime}}_{=z^{\prime}b^{\prime\prime}}+\underbrace{c^{\prime\prime
}z^{\prime\prime}}_{=z^{\prime\prime}c^{\prime\prime}}\\
&  =xa+x^{\prime}b+x^{\prime\prime}c+ya^{\prime}+y^{\prime}b^{\prime
}+y^{\prime\prime}c^{\prime}+za^{\prime\prime}+z^{\prime}b^{\prime\prime
}+z^{\prime\prime}c^{\prime\prime}\\
&  =\left(  xa+ya^{\prime}+za^{\prime\prime}\right)  +\left(  x^{\prime
}b+y^{\prime}b^{\prime}+z^{\prime}b^{\prime\prime}\right)  +\left(
x^{\prime\prime}c+y^{\prime\prime}c^{\prime}+z^{\prime\prime}c^{\prime\prime
}\right)  .
\end{align*}
Thus, $\operatorname*{Tr}\left(  AB\right)  =\operatorname*{Tr}\left(
BA\right)  $ is proven. This solves Exercise \ref{exe.TrAB.23} \textbf{(b)}.
\end{proof}

\begin{proof}
[Second solution to Exercise \ref{exe.TrAB.23}.]As the Hint suggests, we can
kill two birds with one stone by proving that $\operatorname*{Tr}\left(
AB\right)  =\operatorname*{Tr}\left(  BA\right)  $ holds for any two $n\times
n$-matrices $A$ and $B$ for any $n\in\mathbb{N}$. This requires some
familiarity with summation signs; see \cite[\S 2.9]{lina} for an introduction.

Let us show this proof. Let $n\in\mathbb{N}$. Let $A$ and $B$ be two $n\times
n$-matrices. We must show that $\operatorname*{Tr}\left(  AB\right)
=\operatorname*{Tr}\left(  BA\right)  $. Recall that we are using the notation
$C_{i,j}$ for the $\left(  i,j\right)  $-th entry\footnote{that is, the entry
in row $i$ and column $j$} of a matrix $C$. Now, \cite[Proposition 2.28]{lina}
(applied to $m=n$ and $p=n$) yields%
\begin{equation}
\left(  AB\right)  _{i,j}=\sum_{k=1}^{n}A_{i,k}B_{k,j}
\label{sol.TrAB.23.gen.ABij=}%
\end{equation}
for all $i\in\left\{  1,2,\ldots,n\right\}  $ and $j\in\left\{  1,2,\ldots
,n\right\}  $. But the definition of a trace shows that%
\begin{align}
\operatorname*{Tr}\left(  AB\right)   &  =\left(  AB\right)  _{1,1}+\left(
AB\right)  _{2,2}+\cdots+\left(  AB\right)  _{n,n}=\sum_{\ell=1}%
^{n}\underbrace{\left(  AB\right)  _{\ell,\ell}}_{\substack{=\sum_{k=1}%
^{n}A_{\ell,k}B_{k,\ell}\\\text{(by (\ref{sol.TrAB.23.gen.ABij=}), applied to
}i=\ell\text{ and }j=\ell\text{)}}}\nonumber\\
&  =\sum_{\ell=1}^{n}\sum_{k=1}^{n}A_{\ell,k}B_{k,\ell}.
\label{sol.TrAB.23.gen.TrAB=}%
\end{align}
The same argument (but with the roles of $A$ and $B$ interchanged) shows that%
\begin{equation}
\operatorname*{Tr}\left(  BA\right)  =\sum_{\ell=1}^{n}\sum_{k=1}^{n}%
B_{\ell,k}A_{k,\ell}. \label{sol.TrAB.23.gen.TrBA=}%
\end{equation}


We want to prove that $\operatorname*{Tr}\left(  AB\right)
=\operatorname*{Tr}\left(  BA\right)  $. In view of
(\ref{sol.TrAB.23.gen.TrAB=}) and (\ref{sol.TrAB.23.gen.TrBA=}), this rewrites
as%
\[
\sum_{\ell=1}^{n}\sum_{k=1}^{n}A_{\ell,k}B_{k,\ell}=\sum_{\ell=1}^{n}%
\sum_{k=1}^{n}B_{\ell,k}A_{k,\ell}.
\]
Now, to prove this equality, we need to perform several manipulations of sums.
First of all, we rename the two summation indexes $\ell$ and $k$ in the sum
$\sum_{\ell=1}^{n}\sum_{k=1}^{n}A_{\ell,k}B_{k,\ell}$ as $k$ and $\ell$,
respectively. We thus obtain%
\[
\sum_{\ell=1}^{n}\sum_{k=1}^{n}A_{\ell,k}B_{k,\ell}=\sum_{k=1}^{n}\sum
_{\ell=1}^{n}\underbrace{A_{k,\ell}B_{\ell,k}}_{\substack{=B_{\ell,k}%
A_{k,\ell}\\\text{(since multiplication of}\\\text{numbers is commutative)}%
}}=\sum_{k=1}^{n}\sum_{\ell=1}^{n}B_{\ell,k}A_{k,\ell}.
\]
Next, we interchange the two summation signs; to be more precise, we apply
\cite[Proposition 2.31]{lina} to $m=n$, $p=n$ and $a_{k,\ell}=B_{\ell
,k}A_{k,\ell}$. Thus, we obtain%
\[
\sum_{k=1}^{n}\sum_{\ell=1}^{n}B_{\ell,k}A_{k,\ell}=\sum_{\ell=1}^{n}%
\sum_{k=1}^{n}B_{\ell,k}A_{k,\ell}.
\]
Combining what we have proven, we obtain
\[
\sum_{\ell=1}^{n}\sum_{k=1}^{n}A_{\ell,k}B_{k,\ell}=\sum_{k=1}^{n}\sum
_{\ell=1}^{n}B_{\ell,k}A_{k,\ell}=\sum_{\ell=1}^{n}\sum_{k=1}^{n}B_{\ell
,k}A_{k,\ell}.
\]
In view of (\ref{sol.TrAB.23.gen.TrAB=}) and (\ref{sol.TrAB.23.gen.TrBA=}),
this rewrites as $\operatorname*{Tr}\left(  AB\right)  =\operatorname*{Tr}%
\left(  BA\right)  $. This is what we wanted to show. Thus, Exercise
\ref{exe.TrAB.23} is solved again.
\end{proof}

\begin{exercise}
\label{exe.Aek}Let $n\in\mathbb{N}$. For each $k\in\left\{  1,2,\ldots
,n\right\}  $, we let $e_{k}$ denote the $n\times1$-matrix (i.e., the column
vector of size $n$) whose $k$-th entry is $1$ and whose all other entries are
$0$.

(For example: If $n=3$, then $e_{1}=\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  $ and $e_{2}=\left(
\begin{array}
[c]{c}%
0\\
1\\
0
\end{array}
\right)  $ and $e_{3}=\left(
\begin{array}
[c]{c}%
0\\
0\\
1
\end{array}
\right)  $.)

\textbf{(a)} If $n=3$ and if $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  $ is any $2\times3$-matrix, then compute $Ae_{1}$, $Ae_{2}$ and
$Ae_{3}$.

\textbf{(b)} Express $Ae_{k}$ in very simple terms (no matrix multiplication
involved!) for every $m\times n$-matrix $A$ (of arbitrary dimensions $m$ and
$n$).

\textbf{(c)} If $n=2$ and if $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  $ is any $2\times3$-matrix, then compute $e_{1}^{T}A$ and $e_{2}%
^{T}A$. (Note: $e_{k}^{T}$ means $\left(  e_{k}\right)  ^{T}$, that is, the
transpose of $e_{k}$. This is a row vector.)

\textbf{(d)} Express $e_{k}^{T}A$ in very simple terms (no matrix
multiplication involved!) for every $n\times m$-matrix $A$ (of arbitrary
dimensions $n$ and $m$).

[In parts \textbf{(b)} and \textbf{(d)}, you don't need to prove your answer.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.Aek}.] \textbf{(a)} If $n=3$ and $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  $, then%
\[
Ae_{1}=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
a\cdot1+b\cdot0+c\cdot0\\
a^{\prime}\cdot1+b^{\prime}\cdot0+c^{\prime}\cdot0
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
a\\
a^{\prime}%
\end{array}
\right)
\]
and similarly%
\[
Ae_{2}=\left(
\begin{array}
[c]{c}%
b\\
b^{\prime}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ Ae_{3}=\left(
\begin{array}
[c]{c}%
c\\
c^{\prime}%
\end{array}
\right)  .
\]


\textbf{(b)} If $A$ is any $m\times n$-matrix, and if $k\in\left\{
1,2,\ldots,n\right\}  $, then $Ae_{k}=\operatorname{col}_{k}A$. (Here, we are
using the notations of \cite[Definition 2.17 \textbf{(b)}]{lina}; thus,
$\operatorname{col}_{k}A$ denotes the $k$-th column of $A$.)

The easiest way to prove this is using \cite[Proposition 2.19]{lina}. Indeed,
let $A$ be any $m\times n$-matrix, and let $k\in\left\{  1,2,\ldots,n\right\}
$. Note that the identity matrix $I_{n}$ satisfies $\operatorname{col}%
_{k}\left(  I_{n}\right)  =e_{k}$ (since both $\operatorname{col}_{k}\left(
I_{n}\right)  $ and $e_{k}$ are column vectors of size $n$, with their $k$-th
entries equal to $1$ and all other entries equal to $0$). But
\cite[Proposition 2.19 \textbf{(d)}]{lina} (applied to $m$, $n$, $n$, $I_{n}$
and $k$ instead of $n$, $m$, $p$, $B$ and $j$) shows that $\operatorname{col}%
_{k}\left(  AI_{n}\right)  =A\cdot\operatorname{col}_{k}\left(  I_{n}\right)
$. Since $AI_{n}=A$ and $\operatorname{col}_{k}\left(  I_{n}\right)  =e_{k}$,
this rewrites as $\operatorname{col}_{k}A=A\cdot e_{k}=Ae_{k}$. In other
words, $Ae_{k}=\operatorname{col}_{k}A$, which is precisely what we wanted to prove.

\textbf{(c)} If $n=2$ and $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  $, then%
\[
e_{1}^{T}A=\left(
\begin{array}
[c]{cc}%
1 & 0
\end{array}
\right)  \left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{ccc}%
1a+0a^{\prime} & 1b+0b^{\prime} & 1c+0c^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{ccc}%
a & b & c
\end{array}
\right)
\]
and similarly%
\[
e_{2}^{T}A=\left(
\begin{array}
[c]{ccc}%
a^{\prime} & b^{\prime} & c^{\prime}%
\end{array}
\right)  .
\]


\textbf{(d)} If $A$ is any $n\times m$-matrix, and if $k\in\left\{
1,2,\ldots,n\right\}  $, then $e_{k}^{T}A=\operatorname{row}_{k}A$. (Here, we
are using the notations of \cite[Definition 2.17 \textbf{(a)}]{lina}; thus,
$\operatorname{row}_{k}A$ denotes the $k$-th row of $A$.)

The easiest way to prove this is using \cite[Proposition 2.19]{lina}. Indeed,
let $A$ be any $n\times m$-matrix, and let $k\in\left\{  1,2,\ldots,n\right\}
$. Note that the identity matrix $I_{n}$ satisfies $\operatorname*{row}{}%
_{k}\left(  I_{n}\right)  =e_{k}^{T}$ (since both $\operatorname{row}%
_{k}\left(  I_{n}\right)  $ and $e_{k}^{T}$ are row vectors of size $n$, with
their $k$-th entries equal to $1$ and all other entries equal to $0$). But
\cite[Proposition 2.19 \textbf{(c)}]{lina} (applied to $n$, $n$, $m$, $I_{n}$,
$A$ and $k$ instead of $n$, $m$, $p$, $A$, $B$ and $i$) shows that
$\operatorname{row}_{k}\left(  I_{n}A\right)  =\left(  \operatorname{row}%
_{k}\left(  I_{n}\right)  \right)  \cdot A$. Since $I_{n}A=A$ and
$\operatorname{row}_{k}\left(  I_{n}\right)  =e_{k}^{T}$, this rewrites as
$\operatorname{row}_{k}A=e_{k}^{T}\cdot A=e_{k}^{T}A$. In other words,
$e_{k}^{T}A=\operatorname{row}_{k}A$, which is precisely what we wanted to prove.
\end{proof}

\begin{exercise}
\label{exe.RREFornot}Which of the following matrices are in RREF? (See
\cite[Definition 5.1]{Strickland} for the definition of an RREF.)

\vspace{0.809pc}\textbf{(a)} $\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & 0 & 1\\
0 & 0 & 0
\end{array}
\right)  $.\qquad\qquad\textbf{(b)} $\left(
\begin{array}
[c]{ccc}%
1 & 2 & 0\\
0 & 0 & 1\\
0 & 0 & 0
\end{array}
\right)  $.\qquad\qquad\textbf{(c)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 3\\
0 & 0 & 1\\
0 & 0 & 0
\end{array}
\right)  $.

\vspace{0.809pc}\textbf{(d)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
0 & 2 & 0\\
0 & 0 & 3
\end{array}
\right)  $.\qquad\qquad\textbf{(e)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
1 & 2 & 0\\
0 & 0 & 3
\end{array}
\right)  $.\qquad\qquad\textbf{(f)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 0
\end{array}
\right)  $.

\vspace{0.809pc}\textbf{(g)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 1
\end{array}
\right)  $.\qquad\qquad\textbf{(h)} $\left(
\begin{array}
[c]{ccc}%
1 & 0 & 3\\
0 & 0 & 2\\
0 & 1 & 1
\end{array}
\right)  $\qquad\qquad\textbf{(i)} $\left(
\begin{array}
[c]{ccc}%
1 & 2 & 0\\
0 & 1 & 1\\
0 & 0 & 0
\end{array}
\right)  $

\vspace{0.806pc}\textbf{(j)} $\left(
\begin{array}
[c]{ccc}%
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0
\end{array}
\right)  $.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.RREFornot}.] See \cite[Definition
5.1]{Strickland} for the properties RREF0, RREF1, RREF2 and RREF3 that we will
refer to in the following.

\textbf{(a)} This matrix is not in RREF, since it violates property RREF3.
(Namely, the pivot in the second row has a nonzero entry in its column.)

\textbf{(b)} This matrix is in RREF.

\textbf{(c)} This matrix is not in RREF, since it violates property RREF3.
(Namely, the pivot in the second row has a nonzero entry in its column.)

\textbf{(d)} This matrix is not in RREF, since it violates property RREF1
(because two of its pivots are not equal to $1$).

\textbf{(e)} This matrix is not in RREF, since it violates property RREF3.
(Namely, the pivot in the first row has a nonzero entry in its column.) It
also violates property RREF2 (since the pivot in the second row is not further
right than the pivot in the first row).

\textbf{(f)} This matrix is in RREF.

\textbf{(g)} This matrix is not in RREF, since it violates property RREF0.
(Indeed, its second row is zero, but its third row is nonzero, so it has a
zero row that does not come after all the nonzero rows.)

\textbf{(h)} This matrix is not in RREF, since it violates property RREF1. (It
also violates RREF2 and RREF3.)

\textbf{(i)} This matrix is not in RREF, since it violates property RREF3.
(Namely, the pivot in the second row has a nonzero entry in its column.)

\textbf{(j)} This matrix is in RREF. (It is a zero matrix, and any zero matrix
is in RREF.)
\end{proof}

\begin{exercise}
\label{exe.commutant.1111}\textbf{(a)} Let $A=\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  $. Show that the matrices $2\times2$-matrices $B$ that satisfy
$AB=BA$ are precisely the matrices of the form $\left(
\begin{array}
[c]{cc}%
a & b\\
0 & a
\end{array}
\right)  $ for $a,b\in\mathbb{R}$.

[\textbf{Hint:} Let $B=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  $ be any $2\times2$-matrix. Your goal is to prove that $AB=BA$ holds
if and only if $x=y^{\prime}$ and $x^{\prime}=0$.]

\textbf{(b)} Let $A^{\prime}=\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 1
\end{array}
\right)  $. Characterize the $2\times2$-matrices $B$ that satisfy $A^{\prime
}B=BA^{\prime}$.

[That is, find a similar characterization to the one given in part
\textbf{(a)}. Show your reasoning!]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.commutant.1111}.] \textbf{(a)} Let $B=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  $ be any $2\times2$-matrix.

Multiplying the equalities $A=\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  $, we obtain%
\[
AB=\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
1x+1x^{\prime} & 1y+1y^{\prime}\\
0x+1x^{\prime} & 0y+1y^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
x+x^{\prime} & y+y^{\prime}\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  .
\]
Similarly,%
\[
BA=\left(
\begin{array}
[c]{cc}%
x & x+y\\
x^{\prime} & x^{\prime}+y^{\prime}%
\end{array}
\right)  .
\]


Now, we have the following chain of logical equivalences:%
\begin{align*}
& \ \left(  AB=BA\right)  \\
& \Longleftrightarrow\ \left(  \left(
\begin{array}
[c]{cc}%
x+x^{\prime} & y+y^{\prime}\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
x & x+y\\
x^{\prime} & x^{\prime}+y^{\prime}%
\end{array}
\right)  \right)  \\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{since }AB=\left(
\begin{array}
[c]{cc}%
x+x^{\prime} & y+y^{\prime}\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  \text{ and }BA=\left(
\begin{array}
[c]{cc}%
x & x+y\\
x^{\prime} & x^{\prime}+y^{\prime}%
\end{array}
\right)  \right)  \\
& \Longleftrightarrow\ \left(  x+x^{\prime}=x\text{ and }y+y^{\prime
}=x+y\text{ and }x^{\prime}=x^{\prime}\text{ and }y^{\prime}=x^{\prime
}+y^{\prime}\right)  \\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because two matrices are equal if and only if}\\
\text{each entry of the former equals the}\\
\text{respective entry of the latter}%
\end{array}
\right)  \\
& \Longleftrightarrow\ \left(  x^{\prime}=0\text{ and }x=y^{\prime}\right)
\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because both equations }x+x^{\prime}=x\text{ and }y^{\prime}=x^{\prime
}+y^{\prime}\\
\text{are equivalent to }x^{\prime}=0\text{,}\\
\text{whereas the equation }x^{\prime}=x^{\prime}\text{ is a tautology (i.e.,
always true),}\\
\text{while the equation }y+y^{\prime}=x+y\text{ is equivalent to }y^{\prime
}=x
\end{array}
\right)  \\
& \Longleftrightarrow\ \left(  x=y^{\prime}\text{ and }x^{\prime}=0\right)
\\
& \Longleftrightarrow\ \left(  \text{the diagonal entries of }B\text{ are
equal, whereas the }\left(  2,1\right)  \text{-th entry of }B\text{ equals
}0\right)  \\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since }x\text{ and }y^{\prime}\text{ are the diagonal entries of
}B\text{,}\\
\text{whereas }x^{\prime}\text{ is the }\left(  2,1\right)  \text{-th entry of
}B
\end{array}
\right)  \\
& \Longleftrightarrow\ \left(  B=\left(
\begin{array}
[c]{cc}%
a & b\\
0 & a
\end{array}
\right)  \text{ for some }a,b\in\mathbb{R}\right)  .
\end{align*}
This solves part \textbf{(a)} of the exercise.

\textbf{(b)}  Let $B=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  $ be any $2\times2$-matrix.

Multiplying the equalities $A=\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 1
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  $, we obtain%
\[
AB=\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
x & y\\
x^{\prime} & y^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
1x+1x^{\prime} & 1y+1y^{\prime}\\
1x+1x^{\prime} & 1y+1y^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
x+x^{\prime} & y+y^{\prime}\\
x+x^{\prime} & y+y^{\prime}%
\end{array}
\right)  .
\]
Similarly,%
\[
BA=\left(
\begin{array}
[c]{cc}%
x+y & x+y\\
x^{\prime}+y^{\prime} & x^{\prime}+y^{\prime}%
\end{array}
\right)  .
\]


Now, we have the following chain of logical equivalences:%
\begin{align*}
& \ \left(  AB=BA\right)  \\
& \Longleftrightarrow\ \left(  \left(
\begin{array}
[c]{cc}%
x+x^{\prime} & y+y^{\prime}\\
x+x^{\prime} & y+y^{\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
x+y & x+y\\
x^{\prime}+y^{\prime} & x^{\prime}+y^{\prime}%
\end{array}
\right)  \right)  \\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{since }AB=\left(
\begin{array}
[c]{cc}%
x+x^{\prime} & y+y^{\prime}\\
x+x^{\prime} & y+y^{\prime}%
\end{array}
\right)  \text{ and }BA=\left(
\begin{array}
[c]{cc}%
x+y & x+y\\
x^{\prime}+y^{\prime} & x^{\prime}+y^{\prime}%
\end{array}
\right)  \right)  \\
& \Longleftrightarrow\ \left(  x+x^{\prime}=x+y\text{ and }y+y^{\prime
}=x+y\text{ and }x+x^{\prime}=x^{\prime}+y^{\prime}\text{ and }y+y^{\prime
}=x^{\prime}+y^{\prime}\right)  \\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because two matrices are equal if and only if}\\
\text{each entry of the former equals the}\\
\text{respective entry of the latter}%
\end{array}
\right)  \\
& \Longleftrightarrow\ \left(  x^{\prime}=y\text{ and }y^{\prime}=x\right)
\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because both equations }x+x^{\prime}=x+y\text{ and }y+y^{\prime
}=x^{\prime}+y^{\prime}\\
\text{are equivalent to }x^{\prime}=y\text{,}\\
\text{whereas both equations }y+y^{\prime}=x+y\text{ and }x+x^{\prime
}=x^{\prime}+y^{\prime}\\
\text{are equivalent to }y^{\prime}=x
\end{array}
\right)  \\
& \Longleftrightarrow\ \left(  \text{the off-diagonal entries of }B\text{ are
equal, and the diagonal entries of }B\text{ are equal}\right)  \\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since }x^{\prime}\text{ and }y\text{ are the off-diagonal entries of
}B\text{,}\\
\text{whereas }x\text{ and }y^{\prime}\text{ are the diagonal entries of }B
\end{array}
\right)  \\
& \Longleftrightarrow\ \left(  B=\left(
\begin{array}
[c]{cc}%
a & b\\
b & a
\end{array}
\right)  \text{ for some }a,b\in\mathbb{R}\right)  .
\end{align*}


[\textit{Remark:} We could have approached both parts \textbf{(a)} and
\textbf{(b)} more systematically: For example, in part \textbf{(a)}, instead
of manually transforming the equations%
\[
x+x^{\prime}=x\text{ and }y+y^{\prime}=x+y\text{ and }x^{\prime}=x^{\prime
}\text{ and }y^{\prime}=x^{\prime}+y^{\prime}%
\]
into simpler forms, we could have treated them as a system of linear equations%
\[
\left\{
\begin{array}
[c]{c}%
x+x^{\prime}=x\\
y+y^{\prime}=x+y\\
x^{\prime}=x^{\prime}\\
y^{\prime}=x^{\prime}+y^{\prime}%
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \text{in four unknowns }x,y,x^{\prime},y^{\prime
},
\]
and solved this system using Gaussian elimination.]
\end{proof}

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[lina]{lina}Darij Grinberg, \textit{Notes on linear algebra}, version
of 13 December 2016.\newline\url{https://github.com/darijgr/lina}

\bibitem[Strickland]{Strickland}Neil Strickland, \textit{MAS201 Linear
Mathematics for Applications}, lecture notes, 28 September 2013.\newline\url{http://neil-strickland.staff.shef.ac.uk/courses/MAS201/}
\end{thebibliography}


\end{document}