3 - Linear Maps

Vector space

A set $V$ and a field $F$ with $(V, +)$ being an abelian group, and a scalar multiplication $(\cdot, \cdot) : F \times V ⟶ V$ That is associative, with $1 \in F$ producing the identity map $1 v = v$ , and distributive laws both ways between $+$ on $V$ and $+$ on $F$ , and the scalar multiplication of a product in $F$ is the composition of the scalar multiplications.
Elements in $V$ are called vectors, and elements of $F$ are called scalars.
$U \subset V$ is a subspace of $V$ if $U$ is closed under vector addition and scalar multiplication, inherited from $V$ , and also contains the $0$ vector.

I don't know why I wrote the definition like this, maybe I am lazy to type

Linear combination

Let $V$ over $F$ be a vector space, $< v_{i} >$ a list of vectors, and $< a_{i} >$ a list of scalars. The linear combination of these lists is a vector $u = \sum_{i = 1}^{n} a_{i} v_{i}$ .
The set of all linear combinations of $< v_{i} >$ is called $Span (< v_{i} >)$ and is a subspace of $V$ , as choosing all scalars to be zero gives the zero vector in the span, and also by definition, the span is closed under both operations.
if there exists a list of scalars $< a_{i} >$ not all zero for which $0 = \sum_{i = 1} a_{i} v_{i}$ , then the list of vectors $< v_{i} >$ is called linearly dependent.
On the other hand if $0 = \sum_{i = 1} a_{i} v_{i}$ if and only if each $a_{i} = 0$ , then the list of vectors is linearly independent.
The dimension of a vector space is the length of the smallest list of vectors that spans it. The same applies for subspaces.
for a linearly dependent list of vectors, the dimension of the subspace induced by its span is at most the length of the list minus one, as one of these vectors is already in the span, so we need not include it in the list, and we can still span this subspace.
if $V$ is a vector space, any smallest list of linearly independent vectors that span $V$ are called "basis" vectors.

Linear map

if $U, V$ are vector spaces, (on fields $F_{U}, F_{V}$ ) then a function $f : U \to V$ is a linear map if:

$f (u_{1} + u_{2}) = f (u_{1}) + f (u_{2})$
$F_{U} = F_{V}$ (upto isomorphism).
$f (λ u) = λ f (u)$
The linear map is a homomorphism between two vector spaces. let $< e_{i} >$ be a basis list of $U$ . Then for any vector $v \in RANGE (f)$ we have $\mathbf{u} = \sum_{i=1}{#na_}{i}\mathbf{e_{i}}$ such that $f (u) = v$
Therefore, $f (\sum_{i = 1}^{n} a_{i} e_{i}) = \sum_{i = 1}^{n} a_{i} f (e_{i})$ .
This allows us to write a matrix $$
M = \begin{bmatrix} \uparrow \ f(\mathbf{e_{1}} ) \dots f(\mathbf{e_{n}}) \ \downarrow
\end{bmatrix}$$ Whose columns are the image of each basis, and when we write $u$ as a column vector $[a_{1}, a_{2}, \dots, a_{n}]^{T}$ , with components wrt the same basis, The application $f (u)$ is equivalent to the matmul $M u$ .
Also $f (U)$ (also called $RANGE (f)$ ) is a subspace of $V$ , simple due to the structure preserving nature of the linear map: if $f (u) \in f (U)$ , then $λ f (u) = f (λ u) \in f (U)$ . Similiary, if $f (u_{1}), f (u_{2}) \in f (U)$ , then $f (u_{1}) + f (u_{2}) = f (u_{1} + u_{2}) \in f (U)$ . Zero vector is in there too.
Hence, we are concerned about the dimension of $f (U) \leq d i m (V)$ . To see if our linear map $f$ squashes the space $U$ into a lower dimension than $U$ .

Rank of a linear map

Let $U$ be a vector space with $d i m (U) = n$ , and $< e_{i} >$ a basis of $U$ , and let $V$ also be a vector space, both over a scalar field $F$ .
then the rank of the linear map $f : U \to V$ is the dimension of $f (U)$ .
By definition, the list $< f (e_{i}) >$ spans $f (U)$ and has length $n$ . Therefore, $d i m (f (U))$ is at most $n$ ( We may find smaller spanning lists for $f (U)$ ).
In other words, $rank (f) \leq d i m (U)$ .

Kernel of a linear map

for linear map $f : U \to V$ , the kernel of $f$ , is the subset of $U$ that maps to the zero vector in $V$ .
$Kern(f) \subset U$ such that for all $u \in Kern (f)$ , $f (u) = 0 \in V$ .
We notice that $Kern (f)$ is a subspace of $U$ . if $f (u) = 0$ then, $f (λ u) = λ f (u) = 0$ . Similarly, if $f (u_{1}) = 0$ and $f (u_{2}) = 0$ , then $f (u_{1} + u_{2}) = f (u_{1}) + f (u_{2}) = 0$ . Finally, notice that $f (0 + 0) = f (0) + f (0)$ hence $f (0) = f (0) + f (0)$ , but $f (0)$ has some additive inverse in $V$ , therefore $0 \in V = f (0)$ .

We need some nice spanning list and linear independent list lemmas from LADR for this one

2.19 Linear Dependence Lemma

Suppose $v_{1}, \dots, v_{m}$ is a linearly dependent list in $V$ . Then there exists $k \in {1, 2, \dots, m}$ such that

v_{k} \in span (v_{1}, \dots, v_{k - 1}) .

Furthermore, if $k$ satisfies the condition above and the $k$ th term is removed from $v_{1}, \dots, v_{m}$ , then the span of the remaining list equals $span (v_{1}, \dots, v_{m})$ .

Proof

Because the list $v_{1}, \dots, v_{m}$ is linearly dependent, there exist numbers $a_{1}, \dots, a_{m} \in F$ , not all 0, such that

a_{1} v_{1} + \dots + a_{m} v_{m} = 0.

Let $k$ be the largest element of ${1, \dots, m}$ such that $a_{k} \neq 0$ . Then

v_{k} = - \frac{a_{1}}{a_{k}} v_{1} - \dots - \frac{a_{k - 1}}{a_{k}} v_{k - 1},

which proves that $v_{k} \in span (v_{1}, \dots, v_{k - 1})$ , as desired.

Length of any linearly independent list is at most length of any spanning list

let $U$ be a vector space, $< u_{i} >$ a linearly independent list of length $m$ in $U$ , $< w_{i} >$ a spanning list of length $n$ in $U$ .
Then, $m \leq n$ .
$* p r o o f * :$
Consider the following process:

step 1: create the list $L_{1} = u_{1}, w_{1}, \dots, w_{n}$ of length $n + 1$ . This list is linearly dependent because $u_{1} \in Span < w_{i} >$ , but $u_{1} \neq 0$ as it comes from a linearly independent list. Hence there exist some $w_{j} \in Span L_{1}$ , which we can remove to get $L_{1}^{*}$ which is still a spanning list of $U$
step k: Repeating this process to get $L_{k - 1}^{*}$ which contains $u_{k - 1}, \dots u_{1}$ and the rest are the remaining $w^{'} s$ . make $L_{k}$ by adding $u_{k}$ to $L_{k - 1}^{*}$ . $L_{k}$ is a list of length $n + 1$ and is linearly dependent as (by induction) $L_{k - 1}^{*}$ was a spanning list. Yet again, there is some removable $w_{j} \in span L_{k} [1. . j - 1]$ (linear dependence lemma) and it can't be any one of the $u^{'} s$ as they are all preceding by other $u^{'} s$ which are all linearly independent. Remove $w_{j}$ to obtain $L_{k}^{*}$ .
At the end of this process, we obtain $L_{m}^{*}$ , which is a spanning list, obtained by removing (at least) $m$ number of $w^{'} s$ . This means than $m \leq n$ .
$◻$

All basis have the same length, allowing the definition of a dimension (finite dimension vector space obviously)

if $V$ is a vector space, and $L =< u_{i} >$ and $L^{'} =< v_{i} >$ and $L, L^{'}$ are both linearly independent and spanning lists (they're both basis), then they have the same length
Moreover, any linearly independent list of this length is a basis of $V$ .

$* p r o o f * :$ let $| L | = m$ , $| L^{'} | = n$ . Apply the above lemma, treating $L$ as a linearly independent list and $L^{'}$ as a spanning list, to get $m \leq n$ . Now do it the other way around to get $m \leq n$ and hence $m = n := d i m (V)$ .
For the second part, let $L^{*} =< e_{i} >$ be a linearly independent list with length $n = d i m (V)$ . Do the replacement process, treating $L^{*}$ are linearly independent, and a basis $L$ as the spanning list, both of the same length. This allows us to add an element of $L^{*}$ to $L$ and remove an element which was in $L$ , and still maintaining that the list is spanning throughout the process. so we modify $L$ to become $L^{*}$ while maintaning "spanning Ness" at each step. Therefore $L^{*}$ is spanning. Hence $L^{*}$ is a basis.

$◻$

Rank Nullity theorem

Let $U, V$ be vector spaces over $F$ and $f : U \to V$ a linear map. Then, $d i m (U) = rank(f) + d i m (kern (f))$ .

$* p r o o f * :$ let $K =< k_{i} >$ be a basis for $Kern (f)$ of length $m$ . let $E =< e_{i} >$ be a basis of $U$ of length $n = d i m (U)$ . Using the process described in the above lemma, treating $K$ as the linearly independent list, $E$ as the spanning list, create $L^{*} = k_{1}, \dots, k_{m}, e_{m + 1} \dots e_{n}$ . This list spans $U$ . moreover, since $E$ and $K$ are both linearly independent, at each step, after adding a $k_{i}$ when we remove an $e_{j}$ we have a linearly independent list (this can be again shown by induction on the same process). Therefore $L^{*}$ is a linearly independent list. Since it is also of length $n = d i m (U)$ , $L^{*}$ is a basis of $U$ . Hence $f (L^{*}) := f (k_{1}), \dots f (k_{m}), f (e_{m + 1}), \dots f (e_{n})$ spans $V$ (refer to def of linear map). Since any $k_{t} \in Kern (f)$ each $f (k_{i} = 0)$ . Therefore, $f L^{* *} := f (e_{m + 1}), \dots f (e_{n})$ still spans $V$ . We claim $f L^{* *}$ is linearly independent.
Otherwise we have $0 \in V = \sum_{j = m + 1}^{n} a_{j} f (e_{j}) = f (\sum_{j = m + 1}^{n} a_{j} e_{j})$ . This means that $t^{*} = \sum_{j = m + 1}^{n} a_{j} e_{j} \in Kern (f)$ , and hence, $t^{*} \in s p a n (K)$ .If $t^{*} \neq 0 \in U$ , then $t^{*}$ can be written as a linear combination in two ways, one using just $K$ and other one using just $E [m + 1 . . n]$ . Subtracting the two, we get $0 = \sum_{j = 1}^{m} λ_{j} k_{j} - \sum_{j = m + 1}^{n} a_{j} e_{j}$ . so if even one $a_{j} \neq 0 \in F$ , then we contradict the linear independence of $L^{*}$ (and even $E$ for that matter). Hence, bubbling back, $f L^{* *}$ is linearly independent, as each $a_{j}$ has to be zero whenever $0 \in V = \sum_{j = m + 1}^{n} a_{j} f (e_{j})$ .
$◻$

In pratice, if $M$ is a matrix representing a linear map from $U$ to $V$ , then by solving for the kernel/nullspace of $U$ by $M x = 0$ and finding the dimension of this nullspace, we can say that the rank/dimension of the image of this linear map $M$ is equal to the dimension of $U$ minus the dimension of the nullspace/kernel of $M$ .

Invertible linear maps

Linear maps from smaller to larger dimensions are not surjective

Let $U, V$ be vector spaces, $d i m (U) = m < d i m (V) = n$ , $f : U \to V$ a linear map. Since $d i m (f (U)) = rank (f) \leq d i m (U) = m < d i m (V) = n$ , $f (U)$ cannot span $V$ . Hence $f$ is not surjective. (refer definition of rank of linear map, or use rank-nullity theorem to conclude $d i m (f (U)) \leq d i m (U)$ ).

Linear maps from larger to smaller dimensions are not injective

Let $U, V$ be vector spaces, $d i m (U) > d i m (V)$ and $f : U \to V$ a linear map. Using rank-nullity theorem, we have $d i m (U) = d i m (f (U)) + d i m (kern (f))$ Hence, $d i m (kern (f)) = d i m (U) - d i m (f (U)) > d i m (V) - d i m (f (U)) \geq 0$ (the rightmost inequality owing to the fact that f(U) lives in V so its dimension is at most V), Finally, $d i m (k e r n (f)) > 0$ , which means that the kernel of $f$ is not the trivial subspace {0}. Therefore, there are at least two vectors in the kernel, both of which (by definition) map to zero in $V$

Combining the two above ideas, and stating with a little flair, we have:

Invertible linear maps

A linear map $f : U \to V$ is bijective if and only if $d i m (U) = d i m (V)$ and $Kern (f) = {0}$ .

$* p r o o f * :$ Necessity of the two conditions are already clear from the above two theorems. We just have to show sufficiency.
Well, given $Kern (f) = {0}$ and $d i m (U) = d i m (V)$ , suppose $f$ is not injective. then there exists vectors $u \neq v$ such that $f (u) = f (v)$ , since the two vectors are not equal, at least one of them is non zero. However, it follows that $f (u - v) = 0 \in V$ . hence $u - v \neq 0 \in Kern (f)$ , contradicting that kern(f) = {0}. Moreover, using rank nullity, along with $d i m (Kern (f)) = 0$ , We see that $d i m (f (U)) = d i m (U) = d i m (V)$ . It is a trivial fact that the $0$ and highest dimensional subspaces, are uniquely the trivial subspace and the original space itself respectively. Therefore $f (U) = V$ . showing surjectivity.

$◻$

Maps on the same vector space.

Eigenvectors of a linear map

Let $f$ be a linear map on a vector space $V$ (to itself). Then the Eigenvectors of $f$ : $E^{f} = {v \in V : f (v) = λ v, \exists λ \in F}$ . The $λ$ here is called an eigenvalue of $f$ . The set of all eigenvalues of $f$ is called the spectrum of $f$ and denoted $Spec (f)$ . If we define $E_{λ}^{f}$ as the set that contains all vectors $v$ for which $f (v) = λ v$ ofr that particular lambda, then we have $E^{f} = ⋃_{λ \in spec (f)} E_{λ}^{f}$ .
For any particular $λ \in spec (f)$ and a linear map $f$ , $E_{λ}^{f} \cup {0}$ is a subspace of $V$ : Notice that $f (v_{1}) = λ v_{1}, f (v_{2}) = λ v_{2} ⟹ f (v_{1} + v_{2}) = λ (v_{1} + v_{2})$ , and $f (v) = λ v ⟹ f (c v) = c (λ v) = λ (c v)$ .

The set of eigenvectors of f,

E^{f}

itself, without fixing those eigenvectors with a particular eigenvalue IS NOT ALWAYS A SUBSPACE of V!!!

For example just think about $f (v_{1}) = λ_{1} v_{1}, f (v_{2}) = λ_{2} v_{2}$ then, $f (v_{1} + v_{2}) = λ_{1} v_{1} + λ_{2} v_{2}$ .

This is pretty cool, so when we transform a vector space $V$ , there are subspaces of $V$ which contain vectors that each just get scaled by a particular amount $λ$ under the transform.
The eigenvalue and eigenvector sections are pure gold. Read them :) (LADR)

The idea is to have Invariant subspaces :

Operator, invariant subspace

If $V$ is a vector space, a linear map $f$ on $V$ (to $V$ ) is called an operator. A subspace $U$ is invariant under $f$ if $f (u) \in U$ for each $u \in U$ . In other words, the restriction $f |_{U}$ is an operator on $U$ .

Let's talk about one dimensional Invariant subspaces, pick a particular $v \in V$ . Let $U = {λ v : λ \in F}$ . Then, if $f$ is an invariant on $U$ , then for any $u \in U$ , $f u \in U$ . But any $u = λ v$ for some $λ \in F$ . since $f$ is linear, $f λ v = λ f (v)$ . This means that the map $f$ is defined by the image of $v$ itself, and that image is in $U$ therefore there has to be some unique scalar $κ$ for which $f (v) = κ v$ . (note that $U = span (v)$ ).
Conversely if there exists an operator $f$ such that for some $v \in V$ , $f (v) = κ v$ for some scalar $κ \in F$ , then $span (v)$ is an invariant subspace under $f$ .

eigenvalue

if $f$ is an operator on $V$ , then $λ$ is an eigenvalue of $f$ if there exists a non zero $v \in V$ such that $f (v) = λ v$ . Writing $f$ as a matrix $T$ , We have $(T - λ I) v = 0$ . Since $v$ is non zero, the linear map $(T - λ I) \equiv f - λ ι$ has a non trivial kernel/null space. As we know, (from the discussion on invertibility), This is equivalent to saying, $f - λ ι$ is not injective. Using rank nullity theorem, Since the kernel is non trivial, the dimension of $(f - λ ι) (V)$ is smaller than the dimension $V$ which means that this map is also not surjective. Hence finally this map is not invertible.

Linearly independent eigen vectors

If $f$ is an operator on $V$ , if we pick a list of distinct eigenvectors, each associated with it's own distinct eigen value, then that list is linearly independent. That is if $L =< v_{i} >$ such that $v_{i} \in E_{λ_{i}}^{f}$ , then $L$ is linearly independent.

$* p r o o f * :$ since each $v_{i}$ is non zero (by definition), pick the smallest subset of $L$ , $L^{*} =< v_{i}^{*} >$ of length $m \geq 2$ , such that there exists a linear combination $G = \sum_{i=1}{#ma_}{i}\mathbf{v^*_{i}} = \mathbf{0}$ such that each $a_{i}$ is non zero (if an $a_{i}$ is zero, just drop it).
Using matrix notation apply $T - λ_{m}$ to $G$ , since $(T - λ_{m}) {v^{*}}_{m} = 0$ , we obtain a smaller sublist $G^{'}$ (of length m-1) that is also linearly dependent, contradicting the minimality of $G$ .

$◻$

The number of eigenvalues is at most the dimension of the space

if $f$ is an operator on $V$ , then the number of distinct eigenvalues of $f$ is at most $d i m (V)$

$* p r o o f * :$ Pick a list $L$ of eigenvectors, one for each distinct eigenvalue. Then since this list is linearly independent (form the theorem above), it's length is at most $d i m (V)$ .

$◻$