Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
507 lines (443 sloc) 10.1 KB
\documentclass{amsbook}
\usepackage{enumitem}
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{section}{chapter}
\numberwithin{equation}{chapter}
\begin{document}
\frontmatter
\title{Minqi's Solutions to the Exercises and Problems of Michael Artin (2011), Algebra (2nd Edition)}
\author{Minqi Pan}
\date{\today}
\maketitle
\setcounter{page}{4}
\tableofcontents
\mainmatter
\chapter{Matrices}
\section{Exercise 1.1: The Row Index and the Column Index}
What are the entries $a_{21}$ and $a_{23}$ of the matrix $\begin{bmatrix}
1 & 2 & 5\\
2 & 7 & 8\\
0 & 9 & 4
\end{bmatrix}$?
\begin{proof}[Answer]
$2$ and $8$.
\end{proof}
\section{Exercise 1.2: Matrix Multiplication is not Commutative}
Determine the products $AB$ and $BA$ for the following values of $A$ and $B$:
\[ A=\begin{bmatrix}
1&2&3\\
3&3&1
\end{bmatrix}, B=\begin{bmatrix}
-8 & -4\\
9 & 5\\
-3 & -2\end{bmatrix}; A=\begin{bmatrix}
1&4\\
1&2\end{bmatrix}, B=\begin{bmatrix}
6 & -4\\
3 & 2\end{bmatrix}. \]
\begin{proof}[Answer]
For the 1st pair,
\[AB=\begin{bmatrix}
1&0\\
0&1\end{bmatrix}, BA=\begin{bmatrix}
-20 & -28 & -28\\
24 & 33 & 32\\
-9 & -12 & -11\end{bmatrix}.\]
For the 2nd pair,
\[AB=\begin{bmatrix}
18 & 4\\
12 & 0 \end{bmatrix}, BA=\begin{bmatrix}
2 & 16 \\
5 & 16 \end{bmatrix}. \]
\end{proof}
\section{Exercise 1.3: Row$\times$Column and Column$\times$Row}
Let $A=\begin{bmatrix}
a_1 & \dots & a_n
\end{bmatrix}$ be a row vector, and let $B=\begin{bmatrix}
b_1\\
\vdots\\
b_n
\end{bmatrix}$ be a column vector. Compute the products $AB$ and $BA$.
\begin{proof}[Answer]
\[AB=a_1b_1+a_2b_2+\dots+a_nb_n.\]
\[BA=\begin{bmatrix}
b_1a_1 & b_1a_2 & \dots & b_1a_n \\
b_2a_1 & b_2a_2 & \dots & b_2a_n \\
\vdots \\
b_na_1 & b_na_2 & \dots & b_na_n
\end{bmatrix}. \]
\end{proof}
\section{Exercise 1.4: Matrix Multiplication is Associative}
Verify the associative law for the matrix product $\begin{bmatrix}
1 & 2\\
0 & 1\end{bmatrix}, \begin{bmatrix}
0 & 1 & 2\\
1 & 1 & 3 \end{bmatrix}, \begin{bmatrix}
1\\
4\\
3\end{bmatrix}$.
\begin{proof}[Answer]
\[
\left(
\begin{bmatrix}
1 & 2\\
0 & 1\end{bmatrix} \begin{bmatrix}
0 & 1 & 2\\
1 & 1 & 3 \end{bmatrix}
\right)
\begin{bmatrix}
1\\
4\\
3\end{bmatrix}
=\begin{bmatrix}
2 &3 &8\\
1 &1 &3
\end{bmatrix}\begin{bmatrix}
1\\
4\\
3\end{bmatrix}=\begin{bmatrix}
38\\
14\end{bmatrix}.
\]
\[
\begin{bmatrix}
1 & 2\\
0 & 1\end{bmatrix}
\left(\begin{bmatrix}
0 & 1 & 2\\
1 & 1 & 3 \end{bmatrix}
\begin{bmatrix}
1\\
4\\
3\end{bmatrix}
\right)
=\begin{bmatrix}
1 &2\\
0 &1\end{bmatrix}\begin{bmatrix}
10\\
14\end{bmatrix}=\begin{bmatrix}
38\\
14\end{bmatrix}
\]
\end{proof}
\section{Exercise 1.5: The Number of Multiplications Required to Multiply 3 Matrices}
Let $A$, $B$ and $C$ be matrices of size $l\times m$, $m\times n$ and $n\times p$. How many multiplications are required to compute the product $AB$? In which order should the triple product $ABC$ be computed, so as to minimize the number of multiplications required?
\begin{proof}[Answer]
$AB$ has $l\times n$ entries, each in need of $m$ multiplications. Therefore $l\times m\times n$ multiplications are required to compute the product $AB$.
There are $2$ ways to compute $ABC$:
\begin{enumerate}
\item Compute $(AB)C$ with $l\times m\times n + l\times n\times p$ multiplications;
\item Compute $A(BC)$ with $m\times n\times p + l\times m\times p$ multiplications.
\end{enumerate}
Therefore,
\begin{enumerate}
\item If $lmn+lnp>mnp+lmp$, the product $ABC$ should be computed in the order of $A(BC)$.
\item If $lmn+lnp<mnp+lmp$, the product $ABC$ should be computed in the order of $(AB)C$.
\item Otherwise, both orders are equally good.
\end{enumerate}
\end{proof}
\section{Exercise 1.6: $2\times2$ Upper Triangular Matrices}
Compute $\begin{bmatrix}
1 &a\\
&1\end{bmatrix}\begin{bmatrix}
1 &b\\
&1\end{bmatrix}$ and $\begin{bmatrix}
1 &a\\
&1\end{bmatrix}^n$.
\begin{proof}[Answer]
\[
\begin{bmatrix}
1 &a\\
&1\end{bmatrix}\begin{bmatrix}
1 &b\\
&1\end{bmatrix}=\begin{bmatrix}
1 &a+b\\
&1\end{bmatrix}.
\]
\[
\begin{bmatrix}
1 &a\\
&1\end{bmatrix}^n=\begin{bmatrix}
1 &na\\
&1\end{bmatrix}.
\]
\end{proof}
\section{Exercise 1.7: $3\times3$ Upper Triangular Matrices}
Find a formula for $\begin{bmatrix}
1&1&1\\
&1&1\\
& &1\end{bmatrix}^n$, and prove it by induction.
\begin{proof}
We claim that,
\[
\begin{bmatrix}
1&1&1\\
&1&1\\
& &1\end{bmatrix}^n=\begin{bmatrix}
1& n& \frac{n(n + 1)}{2}\\
& 1& n\\
& & 1\end{bmatrix}.
\]
Set $n=2$ and we can verify it by showing that,
\[
\begin{bmatrix}
1&1&1\\
&1&1\\
& &1\end{bmatrix}^2=\begin{bmatrix}
1 &2 &3\\
&1 &2\\
& &1\end{bmatrix}=\begin{bmatrix}
1& 2& \frac{2*(2 + 1)}{2}\\
& 1& 2\\
& & 1\end{bmatrix}.
\]
Now suppose that there exists some $n_0\in\mathbb{N}, n_0\geq 2$ such that,
\[
\begin{bmatrix}
1&1&1\\
&1&1\\
& &1\end{bmatrix}^{n_0}=\begin{bmatrix}
1& n_0& \frac{n_0(n_0 + 1)}{2}\\
& 1& n_0\\
& & 1\end{bmatrix}.
\]
It follows that,
\begin{equation*}
\begin{split}
\begin{bmatrix}
1&1&1\\
&1&1\\
& &1\end{bmatrix}^{n_0+1}&=\begin{bmatrix}
1& n_0& \frac{n_0(n_0 + 1)}{2}\\
& 1& n_0\\
& & 1\end{bmatrix}
\begin{bmatrix}
1&1&1\\
&1&1\\
& &1\end{bmatrix}\\
&=\begin{bmatrix}
1&n_0+1&\frac{n_0(n_0 + 1)}{2}+n_0+1\\
&1&n_0+1\\
&&1\end{bmatrix}.
\end{split}
\end{equation*}
Note that,
\begin{equation*}
\begin{split}
\frac{n_0(n_0 + 1)}{2}+n_0+1&=\frac{n_0(n_0 + 1)}{2}+\frac{2n_0}{2}+\frac{2}{2}\\
&=\frac{n_0(n_0 + 1)+2n_0+2}{2}\\
&=\frac{n_0(n_0 + 1)+2(n_0+1)}{2}\\
&=\frac{(n_0+2)(n_0 + 1)}{2}\\
&=\frac{(n_0+1)((n_0 + 1) + 1)}{2}.
\end{split}
\end{equation*}
Therefore the equation holds for all $n\in\mathbb{N}, n\geq 2$.
\end{proof}
\section{Exercise 1.8: Block Multiplications}
Compute the following products by block multiplications:
\[
\left[
\begin{array}{c|c}
\begin{matrix}
1&1\\
0&1\end{matrix} & \begin{matrix}
1&5\\
0&1\end{matrix}\\\hline
\begin{matrix}
1&0\\
0&1\end{matrix}&\begin{matrix}
0&1\\
1&0\end{matrix}
\end{array}
\right]
\left[
\begin{array}{c|c}
\begin{matrix}
1&2\\
0&1\end{matrix} & \begin{matrix}
1&0\\
0&1\end{matrix}\\\hline
\begin{matrix}
1&0\\
0&1\end{matrix}&\begin{matrix}
0&1\\
1&3\end{matrix}
\end{array}
\right],
\left[
\begin{array}{c|c}
0&\begin{matrix}1&2\end{matrix}\\\hline
\begin{matrix}0\\3\end{matrix}&\begin{matrix}
1&0\\0&1\end{matrix}
\end{array}
\right]
\left[
\begin{array}{c|c}
1&\begin{matrix}2&3\end{matrix}\\\hline
\begin{matrix}4\\5\end{matrix}&\begin{matrix}
2&3\\0&4\end{matrix}
\end{array}
\right]
\]
\begin{proof}[Answer]
\[
\left[
\begin{array}{c|c}
\begin{matrix}
1&1\\
0&1\end{matrix} & \begin{matrix}
1&5\\
0&1\end{matrix}\\\hline
\begin{matrix}
1&0\\
0&1\end{matrix}&\begin{matrix}
0&1\\
1&0\end{matrix}
\end{array}
\right]
\left[
\begin{array}{c|c}
\begin{matrix}
1&2\\
0&1\end{matrix} & \begin{matrix}
1&0\\
0&1\end{matrix}\\\hline
\begin{matrix}
1&0\\
0&1\end{matrix}&\begin{matrix}
0&1\\
1&3\end{matrix}
\end{array}
\right]
\]
\[
=\left[
\begin{array}{c|c}
\begin{pmatrix}
1&1\\
0&1\end{pmatrix}\begin{pmatrix}
1&2\\
0&1\end{pmatrix}+\begin{pmatrix}
1&5\\
0&1\end{pmatrix}\begin{pmatrix}
1&0\\
0&1\end{pmatrix} & \begin{pmatrix}
1&1\\
0&1\end{pmatrix}\begin{pmatrix}
1&0\\
0&1\end{pmatrix}+\begin{pmatrix}
1&5\\
0&1\end{pmatrix}\begin{pmatrix}
0&1\\
1&3\end{pmatrix}\\\hline
\begin{pmatrix}
1&0\\
0&1\end{pmatrix}\begin{pmatrix}
1&2\\
0&1\end{pmatrix}+\begin{pmatrix}
0&1\\
1&0\end{pmatrix}\begin{pmatrix}
1&0\\
0&1\end{pmatrix}&\begin{pmatrix}
1&0\\
0&1\end{pmatrix}\begin{pmatrix}
1&0\\
0&1\end{pmatrix}+\begin{pmatrix}
0&1\\
1&0\end{pmatrix}\begin{pmatrix}
0&1\\
1&3\end{pmatrix}
\end{array}
\right]\\
\]
\[
=\left[
\begin{array}{c|c}
\begin{matrix}2&8\\0&2\end{matrix}&
\begin{matrix}6&17\\1&4\end{matrix}\\\hline
\begin{matrix}1&3\\1&1\end{matrix}&
\begin{matrix}2&3\\0&2\end{matrix}
\end{array}
\right].
\]
\[
\left[
\begin{array}{c|c}
0&\begin{matrix}1&2\end{matrix}\\\hline
\begin{matrix}0\\3\end{matrix}&\begin{matrix}
1&0\\0&1\end{matrix}
\end{array}
\right]
\left[
\begin{array}{c|c}
1&\begin{matrix}2&3\end{matrix}\\\hline
\begin{matrix}4\\5\end{matrix}&\begin{matrix}
2&3\\0&4\end{matrix}
\end{array}
\right]
\]
\[
=\left[
\begin{array}{c|c}
0*1+\begin{pmatrix}1&2\end{pmatrix}\begin{pmatrix}4\\5\end{pmatrix}&
0*\begin{pmatrix}2&3\end{pmatrix}+\begin{pmatrix}1&2\end{pmatrix}\begin{pmatrix}
2&3\\0&4\end{pmatrix}\\\hline
\begin{pmatrix}0\\3\end{pmatrix}*1+\begin{pmatrix}
1&0\\0&1\end{pmatrix}*\begin{pmatrix}4\\5\end{pmatrix}&
\begin{pmatrix}0\\3\end{pmatrix}*\begin{pmatrix}2&3\end{pmatrix}+
\begin{pmatrix}1&0\\0&1\end{pmatrix}\begin{pmatrix}
2&3\\0&4\end{pmatrix}
\end{array}
\right]
\]
\[
=\left[
\begin{array}{c|c}
14&\begin{matrix}2&11\end{matrix}\\\hline
\begin{matrix}4\\8\end{matrix}&\begin{matrix}
2&3\\6&13
\end{matrix}
\end{array}
\right].
\]
\end{proof}
\section{Exercise 1.9: Laws of Matrix Operations}
Let $A, B$ be square matrices.
\begin{enumerate}[label=(\alph*)]
\item When is $(A+B)(A-B)=A^2-B^2$?
\item Expand $(A+B)^3$.
\end{enumerate}
\begin{proof}[Answer]
\begin{enumerate}[label=(\alph*)]
\item When $BA=AB$.
\item $(A+B)^3 = A^3 + ABA + BAA + BBA + AAB + ABB + BAB + B^3$.
\end{enumerate}
\end{proof}
\section{Exercise 1.10: Multiplications with Diagonal Matrices}
Let $D$ be the diagonal matrix with diagonal entries $d_1, \dots, d_n$, and let $A=(a_{ij})$ be an arbitrary $n\times n$ matrix. Compute the products $DA$ and $AD$.
\begin{proof}[Answer]
\[
DA=\begin{bmatrix}
d_1a_{11} & d_1a_{12} & \dots & d_1a_{1n}\\
d_2a_{21} & d_2a_{22} & \dots & d_2a_{2n}\\
\dots & \dots & \dots & \dots\\
d_na_{n1} & d_na_{n2} & \dots & d_na_{nn}
\end{bmatrix},
\]
\[
AD=\begin{bmatrix}
d_1a_{11} & d_2a_{12} & \dots & d_na_{1n}\\
d_1a_{21} & d_2a_{22} & \dots & d_na_{2n}\\
\dots & \dots & \dots & \dots\\
d_1a_{n1} & d_2a_{n2} & \dots & d_na_{nn}
\end{bmatrix}.
\]
\end{proof}
\end{document}
You can’t perform that action at this time.