ALG1_L11

Recall

Recall

1. An $r\times c$ matrix $A$. $f_A:{\mathbb{R}}^c\to {\mathbb{R}}^r$. $f_A(\mathbf{x})=A\mathbf{x}$. kernel of $f_A$ $\subset {\mathbb{R}}^c$, image of $f_A\subset {\mathbb{R}}^r$.
2. Dim(Ker $f_A$) = # non pivot columns in RREF(A).
3. Dim(Im$f_A$) = # of pivot columns in RREF(A).
4. Rank nullity theorem

---

Linear maps

Definition 1(Definition).

A map $T:V\to W$ is called linear if it satisfies

1. $T({\mathbf{v}}_1+{\mathbf{v}}_2)=T({\mathbf{v}}_1)+T({\mathbf{v}}_2)$.
2. $T(c\mathbf{v})=cT(\mathbf{v})$ for all $c\in \mathbb{R}$, $\mathbf{v}\in V$

Linear map and linear transformation are synonyms.

The goal: to show “Dim(Ker $T$)+ Dim(Im $T$)=Dim $V$” for any linear map $T:V\to W$.

Remarks (prove as necessary)

1. A linear map $T$ is a map that preserves the vector space structure, i.e, first adding in V and then applying T is the same as applying T first and then adding in W.
2. Clearly, $T$ preserves linear combinations.
3. Kernel of $T$ is a subspace.
   1. $T$ must always map $0_V$ to $0_W$ ($T(0)=T(0\cdot 0)=0T(0)=0$)
   2. $T({\mathbf{v}}_1)=0,T({\mathbf{v}}_2)=0$ implies $T({\mathbf{v}}_1+{\mathbf{v}}_2)=0$.
4. Image of $T$ is a subspace of $W$.
5. If $S\subset V$ spans $V$, then $T(S)$ spans $T(V)$, i.e, image of $T$.
6. if $S\subset V$ is linearly dependent, then $T(S)$ is linearly dependent.

Examples

1. The set of functions $f_A$ associated with $r\times c$ matrices
2. $V$= set of all differentiable functions $f:\mathbb{R}\to \mathbb{R}$.
   $W$= set of all functions $g:\mathbb{R}\to \mathbb{R}$.
   Consider $D:V\to W$, $D(f)=f^{\prime }$.
   $(f+g{)}^{\prime }=f^{\prime }+g^{\prime }$, $(cf{)}^{\prime }=c{f}^{\prime }$.
   The kernel of $D$ is the set of all constant functions.
   Consider the same map on the subspace $P_n$ of polynomial of degree $\le n$.
   $P_n\stackrel{\text{D}}{\to }{P}_{n-1}$ .
   $P_n$ has dimension $n$, and $P_{n-1}$ has dimension $n-1$. Also, Dim(Ker $D$) = 1.
   So, Dim(Ker D)+Dim(Im D)=Dim(Domain D).
3. $V$= set of $n\times n$ matrices.
   $W=\mathbb{R}$
   $T:V\to W$, $T(A)=\text{Tr }(A)$.
   Check the dimension formula holds, find a basis for the kernel.

Neither homogeneity nor additivity alone is enough to imply that a function is a linear map.

• $\varphi :{\mathbb{R}}^2\to \mathbb{R}$, $(x,y)\stackrel{\varphi }{\mapsto }\frac{x^2}{y}$ is an example of a function which satisfies $\varphi (a\mathbf{v})=a\varphi (\mathbf{v})$ for all $a\in \mathbb{R}$ and $\mathbf{v}\in {\mathbb{R}}^2$ but is not linear since it does not satisfy additivity.
• $\varphi :\mathbb{C}\to \mathbb{C}$, $x+iy\stackrel{\varphi }{\mapsto }x-iy$ is an example of a function which satisfies additivity but is not linear since it is not homogeneous ($\mathbb{C}$ is though of as a complex vector space, i.e, the scalars are drawn from $\mathbb{C}$). $\varphi (i\times i)=\varphi (-1)=-1$, but $i\varphi (i)=1$. There also exists a function $\varphi :\mathbb{R}\to \mathbb{R}$ such that $\varphi$ satisfies the additivity condition but is not homogeneous. However, showing the existence of such a function involves considerably more advanced tools.

---

Rank nullity theorem for general linear maps over fdvsps

Theorem 2(Theorem).

For a linear map $T:V\to W$, where $V$ is a fdvsp, dim(ker T) + dim(im T)= dim V.

Proof
We will show that (Basis of ker $T$) $\cup$ (some disjoint set of size dim Im T)=(a basis of $V$). Take a basis ${\mathbf{k}}_1,{\mathbf{k}}_2,\dots ,{\mathbf{k}}_t$ of ker T. Extend it to get a basis ${\mathbf{k}}_1,\dots ,{\mathbf{k}}_t,{\mathbf{v}}_1,\dots ,{\mathbf{v}}_r$ of $V$. Dim Ker $T$ = $r$, dim $V$ = $t+r$. We have to show that Dim Im $T$ = $r$. We guess that $T({\mathbf{v}}_1),T({\mathbf{v}}_2),\dots ,T({\mathbf{v}}_r)$ is a basis of $\mathrm{Im}(T)$, i.e, they span $\mathrm{Im}(T)$ and are linearly independent.

These vectors span Im T
Since $\{{\mathbf{k}}_1,\dots ,{\mathbf{k}}_t,{\mathbf{v}}_1,\dots ,{\mathbf{v}}_r\}$ is a basis of (in particular, spans) $V$, $\{T({\mathbf{k}}_1),\dots ,T({\mathbf{k}}_t),T({\mathbf{v}}_1),\dots ,T({\mathbf{v}}_r)\}$ span $T(V)=\mathrm{Im}(T)$. Since $\{T({\mathbf{k}}_1),\dots ,T({\mathbf{k}}_t)\}$ has span $\{0\}$, $\{T({\mathbf{v}}_1),\dots ,T({\mathbf{v}}_r)\}$ must span $\mathrm{Im}(T)$.

These vectors are linearly independent
Consider a linear combination of the vectors thats equals 0.

${\sum }_{i=1}^r{c}_{i}T({\mathbf{v}}_i)=0$.

Then, $T\left({\sum }_{i=1}^r{c}_i{\mathbf{v}}_i\right)=0$.

Therefore, ${\sum }_{i=1}^r{c}_i{\mathbf{v}}_i\in \text{Ker }(T)$.

So, ${\sum }_{i=1}^r{c}_i{\mathbf{v}}_i={\sum }_{j=1}^t{a}_j{\mathbf{k}}_j$.

So, ${\sum }_{i=1}^r{c}_i{\mathbf{v}}_i-{\sum }_{j=1}^t{a}_j{\mathbf{k}}_j=0$.

Since ${\mathbf{k}}_1,\dots ,{\mathbf{k}}_t,{\mathbf{v}}_1,\dots ,{\mathbf{v}}_r$ forms a basis of $V$, all $c_i$ and $a_i$ must be $0$. In particular, all $c_i$ must be $0$. Thus, $T({\mathbf{v}}_1),T({\mathbf{v}}_2),\dots ,T({\mathbf{v}}_r)$ are linearly independent. ❏