Linear Algebra and Optimization

Chapter One

Problem 2.1.

(1) To prove that $({\cal H},\cdot)$ is a group we must show that the following properties hold:

1. Closure: if $A,B \in {\cal H}$ then $A \cdot B \in {\cal H}$. To show this note that any upper triangular matrix $A$ has the property
   $$\begin{bmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & a & b \\ d & 1 & c \\ e & f & 1 \end{bmatrix} \odot \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$$
   where $\odot$ denotes the Hadamard product of two matrices and the first matrix is non-singular. In index notation we write this as
   $$A_{ij} = a_{ij} \mathbb{1}_{j \geq i}$$
   where $\mathbb{1}_{\text{statement}}=1$ if the statement is true and zero otherwise. Then
   $$\begin{align*} (A \cdot B)_{ij}&=\sum_{k=1}^n A_{ik}B_{kj}=\sum_{k=1}^n a_{ik}b_{kj} \mathbb{1}_{k \geq i}\mathbb{1}_{j \geq k} \\ & =\sum_{k=1}^n a_{ik}b_{kj}\mathbb{1}_{j \geq i} =(a \cdot b)_{ij}\mathbb{1}_{j \geq i} \end{align*}$$
   and so, $A \cdot B \in {\cal H}$.
2. Since $\cal H$ is a subspace of the vector space of $3 \times 3$ matrices it inherits associativity and the identity element.
3. The inverse $A^{-1}$ of $A \in \cal H$ must have the property
   $$A \cdot A^{-1} = A^{-1} \cdot A = I, \quad A^{-1} \in \cal H.$$
   We note that
   $$(A \cdot A^{-1})_{ij}=\sum_{k=1}^n a_{ik}a^{-1}_{kj} \mathbb{1}_{k \geq i} \mathbb{1}_{j \geq k} = \sum_{k=1}^n \delta_{ij}\mathbb{1}_{k \geq i} \mathbb{1}_{j \geq k} =\delta_{ij}$$
   where $\delta_{ij}=1$ if $i=j$ and zero otherwise. Therefore the inverse exists and is an element of $\cal H$. The following explicit form of the inverse
   $$\begin{bmatrix} 1 & a' & b' \\ 0 & 1 & c' \\ 0 & 0 & 1 \end{bmatrix}$$
   satisfies the diagonal and lower triangular conditions. For the upper triangular elements we must have
   $$\begin{align*} a'+a & = 0 \\ b'+ac'+b & = 0 \\ c'+c & = 0 \end{align*}$$
   and so
   $$A^{-1}=\left[\begin{matrix}1 & - a & a c - b\\0 & 1 & - c\\0 & 0 & 1\end{matrix}\right].$$
   If $({\cal H},\cdot)$ is abelian then $A \cdot B = B \cdot A$ or
   $$\begin{align*} (A\cdot B)_{ij} & = \sum_{k=1}^n a_{ik} b_{kj} \mathbb{1}_{k \geq i} \mathbb{1}_{j \geq k} = \mathbb{1}_{j \geq i}\sum_{k=1}^n a_{ik} b_{kj} = \mathbb{1}_{j \geq i} (a \cdot b)_{ij},\\ (B \cdot A)_{ij} & = \sum_{k=1}^n b_{ik} a_{kj} \mathbb{1}_{k \geq i} \mathbb{1}_{j \geq k} = \mathbb{1}_{j \geq i}\sum_{k=1}^n b_{ik} a_{kj} =\mathbb{1}_{j \geq i} (b \cdot a). \end{align*}$$
   Since $a \cdot b \neq b \cdot a$ we conclude that $\cal H$ is not abelian.

(2) If $a \in G_1$ then from the definition of $e_1$
$$\phi(a e_1 )=\phi(a) \in G_2$$
and since $\phi$ is a homomorphism
$$\phi(a e_1)=\phi(a) \phi(e_1).$$
Hence
$$\phi(a) \phi(e_1)=\phi(a)$$
and we conclude that $\phi(e_1)=e_2$.

Since $a a^{-1} = e_1$
$$\phi(a a^{-1})=\phi(a) \phi(a^{-1})=\phi(e_1).$$
We have already shown that $\phi(e_1)=e_2$. Therefore $\phi(a^{-1})=\phi(a)^{-1}$.

(3) For any $A \in \cal H$, elements $a, b , c \in \mathbb{R}$. Since if $b \in \mathbb{R}$, $e^{ib}$ generates all elements of $S^1$ we conclude that $\phi$ is surjective.

To prove that $(G,\cdot)$ first note that closure is a consequence of the closure of $\mathbb{R}$ w.r.t. addition and multiplication and the fact that if $u_1,u_2 \in S^1$ then, since $e^{ix_1y_2} \in S_1$, $e^{ix_1y_2}u_1 u_2 \in S_1$ (closure of $S^1$ under multiplication). To prove associativity write
$$\begin{align*} & ((x_1,y_1,u_1)\cdot(x_2,y_2,u_2))\cdot(x_3,y_3,u_3)=\\ & \kern3ex= (x_1+x_2,y_1+y_2,e^{ix_1y_2}u_1u_2)\cdot(x_3,y_3,u_3)=\\ & \kern3ex= (x_1+x_2+x_3,y_1+y_2+y_3,e^{i(x_1+x_2)y_3}e^{ix_1y_2}u_1u_2u_3)=\\ & \kern3ex= (x_1+(x_2+x_3),y_1+(y_2+y_3),e^{ix_1(y_2+y_3)}u_1(e^{ix_2y_3}u_2u_3))=\\ & \kern3ex= (x_1,y_1,u_1)\cdot(x_2+x_3,y_2+y_3,e^{ix_2y_3}u_2u_3)=\\ & \kern3ex= (x_1,y_1,u_1)\cdot((x_2,y_2,u_2)\cdot(x_3,y_3,u_3)). \end{align*}$$
The identity element of $G$, $(0,0,1)$ borrows the identity elements of$(\mathbb{R},+)$ and $(S^1,\cdot)$. The inverse of $(x,y,u)$ must have the property
$$(x,y,u)\cdot(x',y',u')=(x+x',y+y',e^{ixy'}uu')=(0,0,1)$$
and so $x'=-x,\ y'=-y, \ u'=e^{ixy}u^{-1}$. $\phi$ is a homomorphism if for $A,B \in \cal H$
$$\phi(A \cdot B) = \phi(A) \cdot \phi(B).$$
Since
$$\begin{bmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & d & e \\ 0 & 1 & f \\ 0 & 0 & 1 \end{bmatrix}= \begin{bmatrix} 1& a+ d & af +b + e \\ 0 & 1 & c+ f \\ 0 & 0 & 1 \end{bmatrix},$$
we have
$$\begin{align*} \phi(A \cdot B) & =(a+d, c+f,e^{i(af+b+e)}) \\ & =(a,c,e^{ib}) \cdot (d,f,e^{ie}) \\ & = \phi(A) \cdot \phi(B). \end{align*}$$
(4) We are looking for a set of matrices $A \in \cal H$ such that
$$\phi(A)=(0,0,1)$$
the identity element in $G$. From the definition of $\phi$ we must have
$$a=0, c=0, b =2\pi n$$
where $n \in \mathbb{Z}$. For any $A \in \ker\phi$ we can write $A=I + 2\pi n e_1 e_3^{\sf T}$ where $e_1^{\sf T}=(1,0,0)$ and $e_3^{\sf T}=(0,0,1)$. Closure follows since if $A,B\in\ker\phi$
$$\begin{align*} A \cdot B & = (I + 2 \pi n e_1 e_3^{\sf T})\cdot(I + 2\pi m e_1 e_3^{\sf T})\\ & = I +2 \pi (n+m) e_1 e_3^{\sf T} + (2\pi)^2nm e_1 e_3^{\sf T} e_1 e_3^{\sf T} , \quad e_3^{\sf T} e_1 =0\\ & =I +2 \pi (n+m) e_1 e_3^{\sf T} \in \ker\phi. \end{align*}$$
Associativity is inherited; the identity element is $I$ ($n=0$) while the inverse of $A=I + 2\pi n e_1 e_3^{\sf T}$ is $A^{-1}=I - 2\pi n e_1 e_3^{\sf T}$. Hence $\ker\phi$ is a subgroup of $\cal H$.

Problem 2.2.

To check that $m\mathbb{Z}=\{mk \vert k\in \mathbb{Z}\}$ is an abelian subgroup of $\mathbb{Z}$ first note that $mk_1+mk_2=m(k_1+k_2)$ (closure). Addition is commutative/associative in $\mathbb{Z}$ and $m\mathbb{Z}$ inherits these properties. It also inherits the identity element ($k=0$) and the inverse ($k^{-1}=-k$).

(1) $\phi(mk):=k$; this is an homomorphism since
$$\phi(mk_1+mk_2)=\phi(m(k_1+k_2))=k_1+k_2=\phi(mk_1)+\phi(mk_2).$$
Since $\ker\phi=\{0\}$ it is also an isomorphism.
(2) If $i(mk):=mk$ then
$$i(mk_1+mk_2)=i(m(k_1+k_2))=m(k_1+k_2)=\\mk_1+mk_2= i(mk_1)+i(mk_2)$$
hence the inclusion map is a group homomorphism. If $p:\mathbb{Z} \to m\mathbb{Z}$ is a homomorphism then
$$p (l_1+l_2)=p(l_1)+p(l_2)=mk_1+m k_2$$
where $l_1,l_2,k_1,k_2 \in \mathbb{Z}$ (for example $k=\lfloor l/m \rfloor$). If $p \circ i={\rm id}$ then $p$ is the left inverse of $i$. By Proposition 2.16 $i$ must be an isomorphism. However, unless $m=1$, $i$ is not an isomorphism since it is not surjective.

Problem 2.3.

As defined $E$ is an abelian group w.r.t. $+$.
From the definition of $\cdot$ we have
$$\lambda\cdot((x_1,y_1)+(x_2,y_2))=\lambda\cdot(x_1+x_2,y_1+y_2) \\ =(\lambda(x_1+x_2),y_1+y_2)=(\lambda x_1+\lambda x_2,y_1+y_2)\\ =(\lambda x_1,y_1)+(\lambda x_2,y_2)=\lambda\cdot(x_1,y_1)+\lambda\cdot(x_2,y_2)$$
so axiom $\text{(V1)}$ holds.
$$(\lambda + \mu) \cdot (x,y)=((\lambda+\mu)x,y)=(\lambda x + \mu x,y) \\=(\lambda x,y)+(\mu x,0)=\lambda\cdot(x,y)+\mu\cdot(x,0)\neq\lambda\cdot(x,y)+\mu\cdot(x,y)$$
so axiom $\text{(V2)}$ fails.
$$(\lambda \mu)\cdot(x,y)=((\lambda\mu)x,y)=(\lambda(\mu x),y)\\=\lambda\cdot(\mu x,y)=\lambda\cdot(\mu\cdot(x,y))$$
so axiom $\text{(V3)}$ holds.
$$1\cdot(x,y)=(1*x,y)=(x,y)$$
so axiom $\text{(V4)}$ holds.

Problem 2.4.

(1) Below we (mostly) omit steps that use the properties of a field.
$$\begin{align*} \alpha\cdot 0&=\alpha\cdot(u-u), \quad \text{\footnotesize any vector $u$ has an additive inverse} \\ &=\alpha \cdot u - \alpha \cdot u, \quad \text{\footnotesize (V1)} \\ & =0, \quad \text{\footnotesize the additive inverse of $\alpha \cdot u$ is $-\alpha \cdot u$} \end{align*}$$
$$\begin{align*} 0 \cdot v &= (\alpha - \alpha) \cdot v, \quad \text{\footnotesize$K$ is a field} \\ & = \alpha \cdot v - \alpha \cdot v, \quad \text{\footnotesize (V2)} \\ & =0, \quad \text{\footnotesize the additive inverse of $\alpha \cdot v$ is $-\alpha \cdot v$} \end{align*}$$
$$\begin{align*} \alpha \cdot (-v) & = \alpha \cdot (-1 \cdot v) \\ & = (\alpha * -1) \cdot v, \quad \text{\footnotesize (V3)} \\ & = - (\alpha \cdot v) \end{align*}$$
$$\begin{align*} (-\alpha) \cdot v & = (-1 *\alpha) \cdot v \\ & = -1\cdot (\alpha\cdot v), \quad \text{\footnotesize (V3)} \\ & = - (\alpha \cdot v), \quad \text{\footnotesize the additive inverse of $\alpha \cdot v$ is $-1\cdot(\alpha \cdot v)$} \end{align*}$$

(2) Axiom $\text{(V2)}$ states that
$$\alpha\cdot(u+v)=\alpha\cdot u + \alpha \cdot v$$
where $u,v$ are vectors and $\alpha$ is a scalar. Then
$$\begin{align*} \alpha \cdot x &= \alpha \cdot (x_1 e_1 + x_2 e_2 + \cdots + x_n e_n) \\ & = \alpha \cdot (x_1 e_1 + ( x_2 e_2 + \cdots + x_n e_n)) \\ & = \alpha \cdot (x_1 e_1)+ \alpha \cdot (x_2 e_2 + \cdots + x_n e_n) \\ & \kern15ex \vdots \\ & = \alpha \cdot (x_1 e_1)+\cdots + \alpha \cdot (x_{n-2} e_{n-2})+ \alpha \cdot(x_{n-1}e_{n-1}+ x_n e_n) \\ & = \alpha\cdot (x_1 e_1)+ \cdots + \alpha\cdot(x_n e_n). \end{align*}$$
Since for any $i=1,2,\ldots,n$,
$$\alpha\cdot(x_i e_i)=\alpha\cdot(x_i\cdot e_i)=(\alpha * x_i) \cdot e_i \\ =(x_i * \alpha) \cdot e_i=x_i\cdot(\alpha\cdot e_i)$$
given $\{\alpha \cdot e_i\}_{i=1}^n$ we can determine the result of scalar multiplication on any vector by its action on the basis vectors.
(3) Lets work backwards. We want to define scalar multiplication so that
$$1 \cdot u \neq u;$$
if we denote $1\cdot u=\nu(u)$ then if axiom $\text{(V3)}$ holds
$$(1*1)\cdot u=1\cdot(1 \cdot u)=1\cdot \nu(u)=\nu^2(u).$$
Since $1*1=1$ we conclude that $\nu(u)=\nu^2(u)$ and so, in this setting, scalar multiplication must be a projection. One example is
$$\alpha \cdot x=(\alpha x_1,\ldots,\alpha x_{n-1},0)$$
which for $\alpha=1$ gives the desired result. All other axioms follow; for example
$$\begin{align*} \alpha\cdot(x+y)&=(\alpha(x_1+y_1),\ldots,\alpha(x_{n-1}+y_{n-1}),0) \\ & =(\alpha x_1 ,\alpha x_{n-1},0)+(\alpha y_1,\ldots,\alpha y_{n-1},0) \\ & = \alpha \cdot x + \alpha \cdot y. \end{align*}$$
(4) If $n \in \mathbb{N}$ then according to $\text{(V2)}$
$$n\cdot u= 1 \cdot u + \ldots + 1 \cdot u = n(1 \cdot u).$$
Next use $\text{(V3)}$:
$$1\cdot u =\left( \frac{1}{n}* n\right)\cdot u=\frac{1}{n}\cdot(n \cdot u)=\frac{1}{n}\cdot (n(1 \cdot u)).$$
This is possible only if
$$\frac{1}{n}\cdot u=\frac{1}{n}(1 \cdot u).$$
A rational number $r=m/n$ where $m,n \in \mathbb{N}$; then
$$\frac{m}{n}\cdot u = \left( m * \frac{1}{n} \right) \cdot u =m \cdot \left( \frac{1}{n} \cdot u\right)=m \cdot \left(\frac{1}{n} (1\cdot u) \right) \\=\frac{1}{n}\left(m \cdot (1 \cdot u)\right)=\frac{1}{n}\left(1 \cdot (m \cdot u)\right)=\frac{1}{n}\left( 1 \cdot m (1\cdot u) \right)\\=\frac{m}{n}(1\cdot(1\cdot u))=r((1*1)\cdot u)=r(1 \cdot u).$$

Written with StackEdit.