#math/linear-algebra **** **Problem 1:** Suppose $V$ and $W$ are finite-dimensional and $T \in \mathcal{L}(V, W)$. Show that with respect to each choice of bases of $V$ and $W$, the matrix of $T$ has at least $\dim \operatorname{range} T$ nonzero entries. Let $v_{1},\ldots,v_{n}$ be a basis for $V$ and $w_{1},\ldots w_{m}$ be a basis for $W$. Denote $r=\text{dim range }T$. $Tv_{i}=a_{1,i}w_{1}+\ldots+a_{m,i}w_{m}$ for $i=1,\ldots, n$. ATC that the matrix of $T$ has $k<r$ nonzero entries. Then at most $k$ $Tv_{i}\neq{}0$. Suppose $v\in V$, then $Tv=T(\alpha_{1} v_{1}+\ldots+\alpha _{n} v_{n})$=\beta _{1} Tu_{1}+\ldots+\beta _{k}Tu_{k}$ where $u_{1},\ldots,u_{k}$ and associated coefficients, are the $v's$ where $Tv_{i}\neq{}0$. Then $\text{dim range T}\leq{}k<r$. Thus it must be that there are at least $\text{dim range }T$ nonzero entries. You can **not** split the v's into null of T and vectors not in null T. The T doesn't care about your basis formation's way of slicing those independent vectors. **** **Problem 2:** Suppose $D \in \mathcal{L}(\mathcal{P}_3(\mathbb{R}), \mathcal{P}_2(\mathbb{R}))$ is the differentiation map defined by $Dp = p'$. Find a basis of $\mathcal{P}_3(\mathbb{R})$ and a basis of $\mathcal{P}_2(\mathbb{R})$ such that the matrix of $D$ with respect to these bases is $\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}.$ Chose $(x^{3},x^{2},x,1)$ to be a basis of $\mathcal{P}_{3}(\mathbb{R})$ and $\left( 3x^{2}, 2x,1 \right)$ be a basis of $\mathcal{P}_{2}(\mathbb{R})$. _Compare the exercise above to Example 3.34. The next exercise generalizes the exercise above._ **** **Problem 3:** Suppose $V$ and $W$ are finite-dimensional and $T \in \mathcal{L}(V, W)$. Prove that there exist a basis of $V$ and a basis of $W$ such that with respect to these bases, all entries of $\mathcal{M}(T)$ are $0$ except that the entries in row $j$, column $j$, equal $1$ for $1 \leq j \leq \dim \operatorname{range} T$. Let $u_{1},\ldots,u_{k}$ be a basis for $\text{null }T$. Extend it with $v_{1},\ldots,v_{n}$ to be a basis of $V$. Let $v\in V$. Then $Tv=T(b_{1}u_{1}+\ldots+b_{k}u_{k}+a_{1}v_{1}+\ldots+a_{n}v_{n})=a_{1}Tv_{1}+\ldots+a_{n}Tv_{n}.$ And, by [[3B3 - Fundamental Theorem of Linear Maps|the fundamental theorem of linear maps]], $Tv_{1},\ldots,Tv_{n}$ is a basis for $\text{range }T$. Let $w_{i}\in W$ be the element $Tv_{i}$ for $i=1,\ldots,n$. Extend $w_{1},\ldots,w_{n}$ with $q_{1},\ldots,q_{m}\in W$ to be a basis of $W$. Since $v_{i}\not\in \text{null }T$ then each $Tv_{i}=w_{i}\neq{}0$. By [[3C1 - Matrices|definition of matrix of linear maps]], $Tv_{i}=A_{1,i}w_{1}+\ldots+A_{n,i}w_{n}+A_{n+1,i}q_{1}+\ldots+A_{n+m,i}q_{m}=A_{i,i}w_{i}=1\cdot w_{i}$. Thus $A_{i,i}=1$ for $i=1,\ldots,n$ and $A_{j,k}=0$ for all $j\neq{}k$. **** **Problem 4:** Suppose $v_1, \ldots, v_m$ is a basis of $V$ and $W$ is finite-dimensional. Suppose $T \in \mathcal{L}(V, W)$. Prove that there exists a basis $w_1, \ldots, w_n$ of $W$ such that all the entries in the first column of $\mathcal{M}(T)$ (with respect to the bases $v_1, \ldots, v_m$ and $w_1, \ldots, w_n$) are $0$ except for possibly a $1$ in the first row, first column. Suppose $Tv_{1}=w_{1}$. **Case 1**: If $w_{1}=0$ then any basis will hold $Tv_{1}=0w_{1}+\ldots+0w_{n}$. Then the entries of the first column of $\mathcal{M}(T)$ are all 0. **Case 2**: If $w_{1}\neq{}0$. Extend $w_{1}$ to $w_{1},\ldots,w_{n}$ to be a basis of $W$. Then $Tv_{1}=1w_{1}+0w_{2}+\ldots+0w_{n}$ and the first column would be a 1 followed by 0s. $ \begin{matrix} w_{1} \\ w_{2} \\ \vdots \\ w_{n} \\ \end{matrix} \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ \end{pmatrix} $ _In this exercise, unlike Exercise 3, you are given the basis of $V$ instead of being able to choose a basis of $V$._ **** **Problem 5:** Suppose $w_1, \ldots, w_n$ is a basis of $W$ and $V$ is finite-dimensional. Suppose $T \in \mathcal{L}(V, W)$. Prove that there exists a basis $v_1, \ldots, v_m$ of $V$ such that all the entries in the first row of $\mathcal{M}(T)$ (with respect to the bases $v_1, \ldots, v_m$ and $w_1, \ldots, w_n$) are $0$ except for possibly a $1$ in the first row, first column. Let $m=\dim V$ and let $\varphi\in\mathcal{L}(V,\mathbf{F})$ assign to each $v\in V$ the coefficient of $w_1$ in $Tv$. The entries in the first row of $\mathcal{M}(T)$ are precisely $\varphi(v_1),\ldots,\varphi(v_m)$. If $\varphi=0$, any basis of $V$ works. Otherwise, choose $v_1\in V$ with $\varphi(v_1)=1$ and choose a basis $v_2,\ldots,v_m$ of $\operatorname{null}\varphi$. Because $\varphi\neq0$, rank–nullity gives $\dim\operatorname{null}\varphi=m-1$, and $v_1\notin\operatorname{null}\varphi$; hence $v_1,\ldots,v_m$ is a basis of $V$. Its corresponding first matrix row is $(1,0,\ldots,0)$. _In this exercise, unlike Exercise 3, you are given the basis of $W$ instead of being able to choose a basis of $W$._ **** **Problem 6:** Suppose $V$ and $W$ are finite-dimensional and $T \in \mathcal{L}(V, W)$. Prove that $\dim \operatorname{range} T = 1$ if and only if there exist a basis of $V$ and a basis of $W$ such that with respect to these bases, all entries of $\mathcal{M}(T)$ equal $1$. $(\Rightarrow)$ Let $n=\dim V$, $m=\dim W$, and suppose $\dim\operatorname{range}T=1$. Choose $0\neq u\in\operatorname{range}T$ and $y\in V$ with $Ty=u$. If $z_1,\ldots,z_{n-1}$ is a basis of $\operatorname{null}T$, then $y,z_1,\ldots,z_{n-1}$ is a basis of $V$ because $y\notin\operatorname{null}T$. Thus $v_1=y$ and $v_i=y+z_{i-1}$ for $2\leq i\leq n$ also form a basis, with $Tv_i=u$ for every $i$. Extend $u$ to a basis $u,x_2,\ldots,x_m$ of $W$, and set $w_1=u-x_2-\cdots-x_m$ and $w_i=x_i$ for $i\geq2$. This is again a basis, and $u=w_1+\cdots+w_m$, so every entry of $\mathcal{M}(T)$ is $1$. $(\Leftarrow)$ Conversely, suppose every entry of $\mathcal{M}(T)$ is $1$ with respect to bases $v_1,\ldots,v_n$ and $w_1,\ldots,w_m$. Setting $u=w_1+\cdots+w_m\neq0$, we have $Tv_i=u$ for every $i$. Therefore $T(\sum_i a_iv_i)=(\sum_i a_i)u$, so $\operatorname{range}T=\operatorname{span}(u)$ and $\dim\operatorname{range}T=1$. **** **Problem 7:** Verify 3.36. Suppose $S,T\in \mathcal{L}(V,W).$ Then $\mathcal{M}(S+T)=\mathcal{M}(S)+\mathcal{M}(T)$. See [[3C4 - Matrices as a Vector Space]]. **** **Problem 8:** Verify 3.38. Suppose $T\in \mathcal{L}(V,W)$ and $\lambda \in F$. Then $\mathcal{M}(\lambda T)=\lambda \mathcal{M}(T)$ See [[3C4 - Matrices as a Vector Space]]. **** **Problem 9:** Prove 3.52. Suppose $A$ is an $m\text{-by-}n$ matrix and $c=\begin{pmatrix}c_{1} \\ \vdots \\ c_{n}\end{pmatrix}$ is an $n\text{-by-}1$ matrix. Then, $ Ac=c_{1}A_{\cdot,1}+\ldots+c_{n}A_{\cdot,n} $ In other words, $Ac$ is a linear combination of the columns of $A$, with the scalars that multiply the columns coming from $c$. $ \begin{pmatrix} A_{1,1} & \cdots & A_{1,n} \\ \vdots & \ddots & \vdots \\ A_{m,1} & \cdots & A_{m,n} \end{pmatrix} \begin{pmatrix} {c_1} \\ {\vdots} \\ {c_n} \end{pmatrix} $ By definition of [[3C3 - Matrix Multiplication]], $Ac$ is defined as $ \begin{align} (Ac)_{i,j} & =\sum_{k=1}^{n}A_{i,k}\times c_{k} \\ & =A_{i,1}c_{1}+\ldots+A_{i,n}c_{n} \end{align} $ Then, $ \begin{align} Ac & =\begin{pmatrix} A_{1,1}c_{1}+\ldots+A_{1,n}c_{n} \\ \vdots{} \\ A_{m,1}c_{1}+\ldots+A_{m,n}c_{n} \\ \end{pmatrix} \\\\ & = c_{1}\begin{pmatrix} A_{1,1} \\ \vdots{} \\ A_{m,1} \end{pmatrix} + \ldots + c_{n} \begin{pmatrix} A_{n,1} \\ \vdots{} \\ A_{m,n} \end{pmatrix} \end{align} $ Which is exactly a linear combination of the columns of $A$ with their respective scalars of $c.$ **** **Problem 10:** Suppose $A$ is an $m$-by-$n$ matrix and $C$ is an $n$-by-$p$ matrix. Prove that $(AC)_{i,\cdot} = A_{i,\cdot}\, C$ for $1 \leq i \leq m$. In other words, show that row $i$ of $AC$ equals (row $i$ of $A$) times $C$. $ \begin{pmatrix} A_{1,1} & \cdots & A_{1,n} \\ \vdots & \ddots & \vdots \\ A_{m,1} & \cdots & A_{m,n} \end{pmatrix} \begin{pmatrix} C_{1,1} & \cdots & C_{1,p} \\ \vdots & \ddots & \vdots \\ C_{n,1} & \cdots & C_{n,p} \end{pmatrix} $ We want to equate $(AC)_{i,\cdot}=A_{i,\cdot}C$. By definition of [[3C3 - Matrix Multiplication]], $(AC)_{i,j}$ is defined by $ \begin{align} (AC)_{i,j} & =\sum _{k=1}^{n}A_{i,k}\times C_{k,j} \\ (AC)_{i,\cdot} & =\underbrace{(\sum _{k=1}^{n}A_{i,k}\times C_{k,1}, \ldots, \sum _{k=1}^{n}A_{i,k}\times C_{k,p})}_{1\ldots p} \end{align} $ Now considering $A_{i}C$, again by definition is equal to $ \begin{align} (A_{i,\cdot}C) & =\underbrace{\begin{pmatrix} \sum _{k=1}^{n}A_{i,k}\times C_{k,1}, & \ldots, & \sum _{k=1}^{n}A_{i,k}\times C_{k,p} \end{pmatrix}\\}_{1\ldots p} \end{align} $ Which is exactly equal to $(AC)_{i,\cdot}$. Thus $A_{i,\cdot}C=(AC)_{i,\cdot}$ **** **Problem 11:** Suppose $a = \begin{pmatrix} a_1 & \cdots & a_n \end{pmatrix}$ is a $1$-by-$n$ matrix and $C$ is an $n$-by-$p$ matrix. Prove that $aC = a_1 C_{1,\cdot} + \cdots + a_n C_{n,\cdot}$ In other words, show that $aC$ is a linear combination of the rows of $C$, with the scalars that multiply the rows coming from $a$. $ \begin{pmatrix} a_1 & \cdots & a_n \end{pmatrix} \begin{pmatrix} C_{1,1} & \cdots & C_{1,p} \\ \vdots & \ddots & \vdots \\ C_{n,1} & \cdots & C_{n,p} \end{pmatrix} $ By definition, $ (aC)_{i}= \sum _{k=1}^{n}a_{k}\times C_{k,i} $ Then, $ \begin{align} aC & = \begin{pmatrix} \sum _{k=1}^{n}a_{k}\times C_{k,1}, \ldots, \sum _{k=1}^{n}a_{k}\times C_{k,p} \end{pmatrix} \\ & =\underbrace{\begin{pmatrix} a_{1}\times C_{1,1} , \ldots, a_{1}\times C_{1,p} \end{pmatrix}}_{1\ldots p} + \ldots +\underbrace{\begin{pmatrix} a_{n}\times C_{n,1}, \ldots, a_{n}\times C_{n,p}\end{pmatrix}}_{1\ldots p} \\ & =a_{1}C_{1,\cdot}+\ldots + a_{n}C_{n,\cdot} \end{align} $ **** **Problem 12:** Give an example with $2$-by-$2$ matrices to show that matrix multiplication is not commutative. In other words, find $2$-by-$2$ matrices $A$ and $C$ such that $AC \neq CA$. Choose $ A=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \quad C=\begin{pmatrix} 2 & 3 \\ 2 & 3 \end{pmatrix} $ $ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 2 & 3 \\ 2 & 3 \end{pmatrix} = \begin{pmatrix} 2 & 3 \\ 2 & 3 \end{pmatrix} $ $ \begin{pmatrix} 2 & 3 \\ 2 & 3 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 3 & 2 \end{pmatrix} $ Left-multiplying by $A$ swaps the **rows** of $C$ (which are identical, so $AC=C$), while right-multiplying by $A$ swaps the **columns** of $C$ (which differ, so $CA\neq{}C$). Left multiplication acts on rows, right multiplication acts on columns. >[!Left Side Multiplication] > For any $A$ and $C$. **Left** ($AC$): each **row** of $AC$ is a linear combination of the **rows of** $C$, with weights taken from the corresponding row of $A$. $A_{(1\times n)} \times C_{(n \times p)}$: the $n \text{ columns of }A$ align and apply to the $n \text{ rows of }C$. $ \begin{pmatrix} a_1 & \cdots & a_n \end{pmatrix} \begin{pmatrix} C_{1,1} & \cdots & C_{1,p} \\ \vdots & \ddots & \vdots \\ C_{n,1} & \cdots & C_{n,p} \end{pmatrix} \implies \begin{pmatrix} a_{1}(C_{1,1} & \cdots & C_{1,p})_{\text{row 1 of }C} \\ + & & +\\ \vdots & & \vdots \\ + & & +\\ a_{n}(C_{n,1} & \cdots & C_{n,p})_{\text{row n of }C} \end{pmatrix}_{1\times p} $ > [!Right Side Multiplication] > **Right** (CA): each **column** of $CA$ is a linear combination of the **columns of** $C$, with weights taken from the corresponding column of $A$. Here is the exact equivalent for right-side multiplication, where a matrix $C$ is multiplied on the right by a single column vector $A$. $C_{(m\times n)} \times A_{(n \times 1)}$: the $n \text{ rows of }A$ align and apply to the $n \text{ columns of }C$. $\begin{pmatrix} C_{1,1} & \cdots & C_{1,n} \\ \vdots & \ddots & \vdots \\ C_{m,1} & \cdots & C_{m,n} \end{pmatrix} \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} \implies \begin{pmatrix} a_1 \begin{pmatrix} C_{1,1} \\ \vdots \\ C_{m,1} \end{pmatrix} + \cdots + a_n \begin{pmatrix} C_{1,n} \\ \vdots \\ C_{m,n} \end{pmatrix} \end{pmatrix}_{m \times 1}$ **** **Problem 13:** Prove that the distributive property holds for matrix addition and matrix multiplication. In other words, suppose $A$, $B$, $C$, $D$, $E$, and $F$ are matrices whose sizes are such that $A(B + C)$ and $(D + E)F$ make sense. Prove that $AB + AC$ and $DF + EF$ both make sense and that $A(B + C) = AB + AC$ and $(D + E)F = DF + EF$. Suppose $A_{n\times m},B_{m\times p},C_{m\times p}$ and $D_{n\times m},E_{n\times m},F_{m\times p}$. By definition of matrix addition $(B+C)_{i,j}=B_{i,j}+C_{i,j}$. Then, by definition of [[3C3 - Matrix Multiplication]], $ \begin{align} A(B+C)_{i,j} & =\sum _{k=1}^{m}A_{i,k}\times(B+C)_{k,j} \\ & =\sum _{k=1}^{m}A_{i,k}B_{k,j}+A_{i,k}C_{k,j} \end{align} $ And, $(AB)_{i,j}=\sum _{k=1}^{m}A_{i,k}B_{k,j}$ and $(AC)_{i,j}=\sum _{k=1}^{m}A_{i,k}C_{k,j}$. Thus $(AB)_{i,j} + AC_{i,j}$ $= \sum _{k=1}^{m}A_{i,k}B_{k,j}+A_{i,k}C_{k,j}$. So $A(B+C)=AB+AC$. Similarly, by definition of matrix addition $(D+E)_{i,j}=D_{i,j}+E_{i,j}$. Then, by definition of [[3C3 - Matrix Multiplication]], $ \begin{align} ((D+E)F)_{i,j} & =\sum _{k=1}^{m}(D+E)_{i,k}\times F_{k,j} \\ & =\sum _{k=1}^{m}D_{i,k}F_{k,j}+E_{i,k}F_{k,j} \end{align} $ And, $(DF)_{i,j}=\sum _{k=1}^{m}D_{i,k}F_{k,j}$ and $(EF)_{i,j}=\sum _{k=1}^{m}E_{i,k}F_{k,j}$. Thus $(DF)_{i,j} + EF_{i,j}$ $= \sum _{k=1}^{m}D_{i,k}F_{k,j}+E_{i,k}F_{k,j}$. So $(D+E)F=DF+EF$. **** **Problem 14:** Prove that matrix multiplication is associative. In other words, suppose $A$, $B$, and $C$ are matrices whose sizes are such that $(AB)C$ makes sense. Prove that $A(BC)$ makes sense and that $(AB)C = A(BC)$. Let $S,R,T\in \mathcal{L}(\ldots, \ldots)$ be the linear maps for matrices $A,B,C$, respectively, such that $SRT$ makes sense. Then, by [[3B3 - Fundamental Theorem of Linear Maps|algebraic properties of products of linear maps]], we know $(SR)T=S(RT)$. Then, with $\mathcal{M}(S)=A,\mathcal{M}(R)=B,\mathcal{M}(T)=C$, $\mathcal{M}(SR)=AB$ and $\mathcal{M}(RT)=BC$, we have $ \begin{align} (AB)C & =\mathcal{M}(SR)\mathcal{M}(T) & \text{product of linear maps}\\ & =\mathcal{M}((SR)T) \\ & =\mathcal{M}(S(RT)) & \text{3.9 associativity of linear maps}\\ & =\mathcal{M}(S)\mathcal{M}(RT) \\ & =A(BC) \end{align} $ **** **Problem 15:** Suppose $A$ is an $n$-by-$n$ matrix and $1 \leq j, k \leq n$. Show that the entry in row $j$, column $k$, of $A^3$ (which is defined to mean $AAA$) is $\sum_{p=1}^{n} \sum_{r=1}^{n} A_{j,p}\, A_{p,r}\, A_{r,k}.$ By definition of [[3C3 - Matrix Multiplication|matrix multiplication]], $ A^{2}_{j,r}=(AA)_{j,r}=\sum _{p=1}^{n}A_{j,p}\times A_{p,r} $ Then, $ \begin{align} A^{3}_{j,k} & =((A^{2})A)_{j,k} \\ & = \sum _{r=1}^{n}(A^{2})_{j,r}\times A_{r,k} \\ & =\sum _{r=1}^{n}\sum _{p=1}^{n}A_{j,p}\times A_{p,r}\times A_{r,k} \end{align} $