# Linear Algebra Done Right (notes)

This page is a collection of notes (definitions/propositions/theorems without proofs) written down while going through the Linear Algebra Done Right by Sheldon Axler. There will also be code in Scala which will possibly help me in trying to understand the concepts.

# Vectors and vector spaces

We will work with spaces of vectors in complex ($\C$) and real ($\R$) domains. They both are represent a field, i.e. they have the following properties:

• Commutativity: $a + b = b + a$
• Associativity: $a + (b + c) = (a + b) + c$ and $(ab)v = a(bv)$
• Identities: $a + 0 = a$ and $a1 = a$
• Additive inverse: $\forall a, \quad \exists (-a)$ such that $a + (-a) = 0$
• Multiplicative inverse: $a * 1/a = 1$
• Distributive property: $x(a + b) = xa + xb$
forAll { (x: Double, y: Double, z: Double) => {
x + y == y + x &&
x + (y + z) == (x + y) + z &&
x + 0 == x &&
x + (-x) = 0 &&
x * 1/x = 1 &&
x * (y + z) = x * y + x * z
}}


Throughout the book, $F$ stands for $\R$ and $\C$.

## Vector spaces

A vector space is a set $V$ along with an addition and a scalar multiplication on $V$ that satisfy the below properties:

• Commutativity
• Associativity
• Multiplicative identity
• Distributive properties
/**
* Let's constrain vector spaces to finite-dimensional ones. We also make a
* huge simplification of a model and use Set as a container for vectors (which
* obviously makes it finite).
*/
class VectorSpace[T](val dimension: Int, val vectors: Set[Vector[T]]) {
val zero: Vector[T] = new Vector(Stream.continually(0).take(dimension).toList)

def additiveIdentity(v: Vector[T]): Vector[T] = vectors.find(_ + v == v)
def additiveInverse(v: Vector[T]): Vector[T] = vectors.find(_ + v == 0)
def multiplicativeIdentity(v: Vector[T]): Vector[T] = vectors.find(_ * v == v)
def multiplicativeInverse(v: Vector[T]): Vector[T] = vectors.find(_ * v == 1)
}


Elements of a vector space are called vectors or points.

class Vector[T : Numeric](val components: IndexedSeq[T]) {
def apply(position: Int): T = components(position)
def +(v: Vector[T]) = new Vector((components zip v.components) map (_._1 + _._2))
def *(x: T) = new Vector(components map (_ * x))
def unary_-: Vector[T] = this * (-1)
}


1.2 Proposition: A vector space has a unique additive identity.

forAll { (space: VectorSpace[T], v1: Vector[T], v2: Vector[T]) => {
}}


1.3 Proposition: Every element in a vector space has a unique additive inverse.

forAll { (space: VectorSpace[T], v1: Vector[T], v2: Vector[T]) => {
}}


1.4 Proposition: $0v = 0, \quad \forall v \in V$.

forAll { (space: VectorSpace[T], v: Vector[T]) => {
v * 0 == space.zero
}}


1.5 Proposition: $a0 = 0, \quad \forall a \in F$.

forAll { (space: VectorSpace[T], x: T) => {
space.zero * x == space.zero
}}


1.6 Proposition: $(-1)v = -v, \quad \forall v \in V$.

forAll { (space: VectorSpace[T], v: Vector[T]) => {
v * (-1) == -v
}}


## Vector subspaces

A subset $U$ of $V$ is called a subspace if $U$ is also a vector space. If $U$ is a subset of $V$ then to know that $U$ is indeed a subspace we need to check:

• Additive identity: $0 \in U$
• Closure under addition: $if \quad a, b \in U: \quad a + b \in U$
• Closure under multiplication: $if \quad a \in U, x \in F: \quad ax \in U$
/**
* We can now simplify VectorSpace according to the propositions in the
* previous chapter and enrich it with the subspace concept.
*/
class VectorSpace[T](val dimension: Int, val vectors: Set[Vector[T]]) {
private[this] def constant(value: T): Vector[T] =
new Vector(Stream.continually(0).take(dimension).toList)
val zero: Vector[T] = constant(0)
val one: Vector[T] = constant(1)

def additiveIdentity(v: Vector[T]): Vector[T] = zero
def additiveInverse(v: Vector[T]): Vector[T] = -v
def multiplicativeIdentity(v: Vector[T]): Vector[T] = one
def multiplicativeInverse(v: Vector[T]): Vector[T] = vectors.find(_ * v == 1)

def isSubspace(other: VectorSpace[T]): Boolean = vectors contains other.vectors
}


## Sums and direct sums

The sum of $U_1,\dotsc,U_m$, denoted $U_1 + \dotsb + U_m$ is a set of all possible sums of elements of $U_1,\dotsc,U_m$.

$$U_1 + \dotsb + U_m = \left\{ {u_1 + \dotsb + u_m: u_1 \in U_1,\dotsc,u_m \in U_m}\right\}$$

object VectorSpace {
def sum[T](spaces: Iterable[VectorSpace[T]): VectorSpace[T] = ...
}


The direct sum of subspaces $U_1,\dotsc,U_m$, written

$$V = U_1 \bigoplus ... \bigoplus U_m$$

is a sum where each element of $V$ can be written uniquely as a sum $u_1 + \dotsb + u_m$, where each $u_j \in U_j$ .

1.8 Proposition: Suppose that $U_1,\dotsc,U_m$ are subspaces of $V$. Then $V = U_1 \bigoplus ... \bigoplus U_m$ if and only if :

• $V = U_1 + \dotsb + U_m$
• the only way to write 0 as a sum $u_1 + \dotsb + u_n$, where each $u_j \in U_j$, is by taking all the $u_j$’s equal to 0 .

1.9 Proposition: Suppose that $U$ and $W$ are subspaces of $V$. Then $V = U \bigoplus W$ if and only if $V = U + W$ and $U \cap W = \varnothing$.

## Finite-Dimensional vector spaces

A linear combination of a list $(v_1,\dotsc,v_m)$ of vectors in $V$ is a vector of the form $a_1v_1 + \dotsb + a_mv_m$, where $a_1,\dotsc,a_m \in F$.

The set of all linear combinations of $(v_1,\dotsc,v_m)$ is called the span of $(v_1,\dotsc,v_m)$, denoted $span(v_1,\dotsc,v_m)$.

$$span(v_1,\dotsc,v_m) = \left\{ {a_1v_1 + \dotsb + a_mv_m : a_1,\dotsc,a_m \in F}\right\}$$

A vector space is called finite dimensional if some list of vectors in it spans the space.

A polynomial $p \in P(F)$ is said to have degree $m$ if there exist scalars $a_0,\dotsc,a_m \in F$ with $a_m \not= 0$ such that

$$p(z) = a_0 + a_1z + \dotsb + a_mz^m$$

A vector space that is not finite dimensional is called infinite dimensional.

A list $(v_1,\dotsc,v_m)$ of vectors in V is called linearly independent if the only choice of $a_1,\dotsc,a_m \in F$ that makes $a_1v_1 + \dotsb + a_mv_m = 0$ is $a_1 = \dotsb = a_m = 0$.

A list of vectors in $V$ is called linearly dependent if it is not linearly independent.

2.4 Linear Dependence Lemma: If $(v_1,\dotsc,v_m)$ is linearly dependent in $V$ and $v_1 \not= 0$, then there exists $j \in \left\{ {2,\dotsc,m}\right\}$ such that the following hold:

• $v_j \in span(v_1,\dotsc,v_m)$
• if the $j^{th}$ term is removed from $(v_1,\dotsc,v_m)$, the span of the remaining list equals $span(v_1,\dotsc,v_m)$.

2.6 Theorem: In a finite-dimensional vector space, the length of every linearly independent list of vectors is less than or equal to the length of every spanning list of vectors.

2.7 Proposition: Every subspace of a finite-dimensional vector space is finite dimensional.

### Bases

A basis of $V$ is a list of vectors in $V$ that is linearly independent and spans $V$.

A standard basis of $F^n$ is a list

$$((1,0,\dotsc,0),(0,1,0,\dotsc,0),\dotsc,(0,\dotsc,0,1))$$

2.8 Proposition: A list $(v_1,\dotsc,v_n)$ of vectors in $V$ is a basis of $V$ if and only if every $v \in V$ can be written uniquely in the form $v = a_1v_1 + \dotsb + a_nv_n$, where $a_1,\dotsc,a_n \in F$.

2.10 Theorem: Every spanning list in a vector space can be reduced to a basis of the vector space.

2.11 Corollary: Every finite-dimensional vector space has a basis.

2.12 Theorem: Every linearly independent list of vectors in a finite-dimensional vector space can be extended to a basis of the vector space.

2.13 Proposition: Suppose $V$ is finite dimensional and $U$ is a sub-space of $V$. Then there is a subspace $W$ of $V$ such that $V = U \bigoplus W$.

### Dimension

2.14 Theorem: Any two bases of a finite-dimensional vector space have the same length.

The dimension of a finite-dimensional vector space is defined to be the length of any basis of the vector space.

2.15 Proposition: If $V$ is finite-dimensional and $U$ is a subspace of $V$, then $dimU \leq dimV$.

2.16 Proposition: If $V$ is finite-dimensional, then every spanning list of vectors in $V$ with length $dimV$ is a basis of $V$.

2.17 Proposition: If $V$ is finite-dimensional, then every linearly independent list of vectors in $V$ with length $dimV$ is a basis of $V$.

2.18 Theorem: If $U_1$ and $U_2$ are subspaces of a finite-dimensional vector space, then $dim(U_1 + U_2) = dimU_1 + dimU_2 - dim(U_1 \cap U_2)$.

2.19 Proposition: Suppose $V$ is finite-dimensional and $U_1,\dotsc,U_m$ are subspaces of $V$ such that $V = U_1 + \dotsb + U_m$ and $dimV = dimU_1 + \dotsb + dimU_m$. Then $V = U_1 \bigoplus \dotsb \bigoplus U_m$.

## Linear Maps

A linear map from $V$ to $W$ is a function $T: V \rightarrow W$ with the following properties:

• Additivity: $T(u + v) = Tu + Tv$ for all $u, v \in F$
• Homogeneity: $T(av) = a(Tv)$ for all $a \in F$ and all $v \in V$.

If $S$ and $T$ are linear maps, $ST$ (their product) is a linear map too, with the following properties:

• Associativity: $(T_1T_2)T_3 = T_1(T_2T_3)$ when the products make sense.
• Identity: $TI_v = I_wT$ when $T \in \mathcal{L}(V, W)$.
• Distributive properties: $(S_1 + S_2)T = S_1T + S_2T$ and $S(T_1 + T_2) = ST_1 + ST_2$.

## Null Spaces and Ranges

For $T \in \mathcal{L}(V, W)$, the null space of $T$ denoted $nullT$, is:

$$nullT = \left\{ {v \in V: Tv = 0}\right\}$$

3.1 Proposition: If $T \in \mathcal{L}(V, W)$, then $nullT$ is a subspace of $V$.

A linear map $T: V \rightarrow W$ is called injective if whenever $u,v \in V$ and $Tu = Tv$, $u = v$.

3.2 Proposition: Let $T \in \mathcal{L}(V, W)$. Then $T$ is injective if and only if $nullT = {0}$.

For $T \in \mathcal{L}(V, W)$, the range of $T$, denoted $rangeT$, is:

$$rangeT = \left\{ {Tv: v \in V}\right\}$$

3.3 Proposition: If $T \in \mathcal{L}(V, W)$, then $rangeT$ is a subspace of $W$.

A linear map $T: V \rightarrow W$ is called surjective if its range equals $W$.

3.4 Theorem: If $V$ is finite-dimensional and $T \in \mathcal{L}(V, W)$, then $rangeT$ is a finite-dimensional subspace of $W$ and

$$dimV = dim(nullT) + dim(rangeT)$$