#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. Goal: Show theres a basis in $V$ where $Tv_{1}s representation in $W$ is $1w_{1}+?w_{2}+\ldots+?w_{m}$ and $Tv_{i}'s$ representation in $W$ is $0w_{1}+?w_{2}+\ldots+?w_{m}$ **Case 1**: There does not exist $v\in V$ with $Tv=\alpha w_{1}+\ldots$ and $\alpha \neq{}0$. Then any arbitrary basis of $V$ will have an associated $\mathcal{M}(T)$ with $0s for the first row. **Case 2:** There does exist a $v\in V$ with $Tv=\alpha w_{1}+\ldots$ and $\alpha \neq{}0$. Select $v_{1}=\frac{1}{\alpha}v$. Now suppose a function $\varphi: V\to F$. Where $\varphi(v)=\text{coeffcient of }w_{1}\text{ in }Tv$. Note $\varphi$ is a linear map. It maintains additivity suppose $Tv=\alpha_{1}w_{1}+\ldots$ and $Tu=\beta_{1}w_{1}+\ldots$. Since $T$ is linear $T(v+u)=Tv+Tu$ and thus $\varphi(v+u)=\alpha+\beta=\varphi v+\varphi u$. The map $\varphi$ is also homogenous, $\varphi \lambda v=\lambda\alpha=\lambda \varphi v$. By the [[3B1 - Null Space and Range|rank nullity theorem]], the dimension of null space of $\varphi$ is $m-1$. Thus, if we extend a $v_{2},\ldots,v_{m}$ to $v_{1}$ to form a basis of $v$. Then it must be that $v_{2},\ldots,v_{m}\in \text{null }\varphi$. Then first row, first column of $\mathcal{M}(T)$ is 1 and the remaining row must be all 0. --- >[!Comment ] >The above was a more top down approach by constructing a function. Below is a more constructive version that requires proving the generated list is linearly indepdenent. **Case 2:** There does exist a $v\in V$ with $Tv=\alpha w_{1}+\ldots$ and $\alpha \neq{}0$. Select $v_{1}=\frac{1}{\alpha}v$. Now extend $v_{1}$ with $x_{2},\ldots,x_{n}$ to a basis of $V$. Define a new list $v_{1},\ldots,v_{n}$ such that $v_{i}=x_{i}-\beta _{i}v_{1}$ where $\beta _{i}=\text{coefficient of }w_{1}\text{ in }Tv_{i}$ for $i=2,\ldots,n$. $v_{1},\ldots,v_{n}$ is linearly independent. Suppose $v\in V$ with $v=c_{1}+v_{1}+\ldots=c_{n}v_{n}$. Consider, $ \begin{align} 0 & =c_{1}v_{1}+c_{2}v_{2}+\ldots+c_{n}v_{n} \\ & =c_{1}v_{1}+c_{2}(x_{2}-\beta_{2}v_{1})+\ldots+c_{n}(x_{n}-\beta _{n}v_{1}) \\ & =(c_{1}-c_{2}\beta_{2}-\ldots-c_{n}\beta _{n})v_{1}+c_{2}x_{2}+\ldots+c_{n}x_{n} \end{align} $ $v_{1},x_{2},\ldots,x_{n}$ is linearly independent. Thus $c_{2}=\ldots=c_{n}=0$. And $(c_{1}-c_{2}\beta_{2}-\ldots-c_{n}\beta _{n})$ consequently becomes $c_{1}$, which then must also be $0$. Thus $v_{1},\ldots,v_{n}$ is linearly independent and a basis of $V$. _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$. Goal: Find a basis for $V$ (dim n) and $W$ (dim m) such that $Tv_{i}=w_{1}+\ldots+w_{m}$ for $i=1,\ldots,n$. $(\Rightarrow)$ Suppose $V$ and $W$ are finite-dimensional with size $n$ and $m$, respectively. And $T\in \mathcal{L}(V,W)$ with $\text{dim range }T=1$. Now suppose $u\in \text{range }T$ with $u\neq{}0$. Extend $u$ with $x_{2},\ldots,x_{m}$ to a basis of $W$. Now define $ w_{1}=u-\sum _{i=2}^{m}x_{i} $ with $w_{i}=x_{i}$ for $i=2,\ldots,m$. Note $w_{1},\ldots,w_{m}$ is linearly independent. Same setup as [[2A6 - Problem Set|2A #6]] after substitution in $c_{1}w_{1}+\ldots+c_{m}w_{m}=0$. By the [[3B1 - Null Space and Range|rank nullity theorem]], $\text{dim null }T=n-1$. Let $z_{1},\ldots,z_{n-1}$ be a basis for $\text{null }T.$ Let $v_{n}=y$ where $T(y)=u$. Note that trivially, $z_{1},\ldots,z_{n-1},y$ is linearly independent. Now define $v_{i}=z_{i}+y$ for $i=1,\ldots,n-1.$ This list is then $ y,z_{1}+y, \ldots,z_{n-1}+y $ Following the same pattern as, [[2A - Problem Set|2A #6]], the list is linearly independent. Now, observe the following. $ T(v_{n})=u $ $ T(v_{i})=T(z_{i}+v_{n})=Tz_{i}+Tv_{n}=0+u=u $ So $Tv_{i}=u$ for all $i$ and the representation of $u\in W$ is $w_{1}+w_{2}\ldots+w_{m}$. Thus every column of $\mathcal{M}(T)$ is represented by 1s for every column. **** **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} $