(sec:la:vector-spaces)= # Vector Spaces (sec:la:algebraic_structure)= ## Algebraic Structures In mathematics, the term *algebraic structure* refers to an arbitrary set with one or more operations defined on it. * Simpler algebraic structures include groups, rings, and fields. * More complex algebraic structures like vector spaces are built on top of the simpler structures. We will develop the notion of vector spaces as a progression of these algebraic structures. ### Groups A group is a set with a single binary operation. It is one of the simplest algebraic structures. ````{prf:definition} Group :label: def-la-group Let $G$ be a set. Let $* : G \times G \to G$ be a binary operation defined on $G$ mapping $(g_1, g_2) \to * (g_1, g_2)$ and denoted as $$ * (g_1, g_2)\triangleq g_1 * g_2. $$ If the binary operation $*$ satisfies the following properties: 1. [Closure] The set $G$ is closed under the binary operation $*$. i.e. $$ \forall g_1, g_2 \in G, g_1 * g_2 \in G. $$ 1. [Associativity] For every $g_1, g_2, g_3 \in G$ $$ g_1 * (g_2 * g_3) = (g_1 * g_2) * g_3 $$ 1. [Identity element] There exists an element $e \in G$ such that $$ g * e = e * g = g \quad \forall g \in G $$ 1. [Inverse element] For every $g \in G$ there exists an element $g^{-1} \in G$ such that $$ g * g^{-1} = g^{-1} * g = e $$ then the set $G$ together with the operator $*$ denoted as $(G, *)$ is known as a *group*. ```` Above properties are known as *group axioms*. Note that commutativity is not a requirement of a group. ```{prf:remark} :label: rem-la-group-operation-add-mult Frequently, the group operation is the regular mathematical addition. In those cases, we write $g_1 * g_2$ as $g_1 + g_2$. Otherwise, we will write $g_1 * g_2$ as $g_1 g_2$. Often, we may simply write a group $(G, *)$ as $G$ when the underlying operation $*$ is clear from the context. ``` ### Commutative groups A commutative group is a richer structure than a group. Its elements also satisfy the commutativity property. ````{prf:definition} Commutative group :label: def-la-commutative-group Let $(G, *)$ be a group such that its binary operation $*$ satisfies an additional property: 1. [Commutativity] For every $g_1, g_2 \in G$ $$ g_1 g_2 = g_2 g_1 $$ Then $(G,*)$ is known as a *commutative group* or an *Abelian group*. ```` ### Rings A ring is a set with two binary operations defined over it with some properties as described below. (def:alg:associative_ring)= ````{prf:definition} Associative ring :label: def-la-associative-ring Let $R$ be a set with two binary operations $+ : R \times R \to R$ (addition) mapping $(r_1, r_2) \mapsto r_1 + r_2$ and $\cdot : R \times R \to R$ (multiplication) mapping $(r_1, r_2) \mapsto r_1 \cdot r_2$ such that $(R, +, \cdot)$ satisfies following properties: 1. $(R, +)$ is a commutative group. 1. $R$ is closed under multiplication. $$ r_1 \cdot r_2 \in R \quad \forall r_1, r_2 \in R $$ 1. Multiplication is associative. $$ r_1 \cdot (r_2 \cdot r_3) = (r_1 \cdot r_2) \cdot r_3 \quad \forall r_1, r_2, r_3 \in R $$ 1. Multiplication distributes over addition. $$ \begin{aligned} &r_1 \cdot (r_2 + r_3) = (r_1 \cdot r_2) + (r_1 \cdot r_3) \quad \forall r_1, r_2, r_3 \in R\\ &(r_1 + r_2) \cdot r_3 = (r_1 \cdot r_3) + (r_2 \cdot r_3) \quad \forall r_1, r_2, r_3 \in R \end{aligned} $$ Then, $(R, +, \cdot)$ is known as an *associative ring*. We denote the identity element for $+$ as $0$ and call it additive identity. ```` ```{prf:remark} :label: rem-la-ring-dot-as-ab In the sequel we will write $r_1 \cdot r_2$ as $r_1 r_2$. We may simply write a ring $(R, +, \cdot)$ as $R$ when the underlying operations $+,\cdot$ are clear from the context. ``` There is a hierarchy of ring like structures. In particular we mention: 1. Associative ring with identity 1. Field ````{prf:definition} Associative ring with identity :label: def-la-associative-ring-identity Let $(R, +, \cdot)$ be an associate ring with the property that there exists an element $1 \in R$ (known as multiplicative identity) such that $$ 1 \cdot r = r \cdot 1 = r \quad \forall r \in R. $$ Then $(R, +, \cdot)$ is known as an *associative ring with identity*. ```` ### Fields Field is the richest algebraic structure on one set with two operations. ````{prf:definition} Field :label: def-la-field Let $F$ be a set with two binary operations $+: F \times F \to F$ (addition) mapping $(x_1, x_2) \mapsto x_1 + x_2$ and $\cdot: F \times F \to F$ (multiplication) mapping $(x_1, x_2) \mapsto x_1 \cdot x_2$ such that $(F, +, \cdot)$ satisfies following properties: 1. $(F, +)$ is a commutative group (with additive identity as $0 \in F$). 1. $(F \setminus \{0\}, \cdot)$ is a commutative group (with multiplicative identity as $1 \in F$). 1. Multiplication distributes over addition: $$ \alpha \cdot (\beta + \gamma) = (\alpha \cdot \beta) + (\alpha \cdot \gamma) \quad \forall \alpha, \beta, \gamma \in F $$ Then $(F, +, \cdot)$ is known as a *field*. ```` The definition above implies a number of properties. For any $a,b,c \in F$, we have: * Closure: $a + b \in F$, $a b \in F$. * Associativity of addition and multiplication: $a + (b + c) = (a + b) + c$ and $a (b c) = (a b) c$. * Commutativity of addition and multiplication: $a + b = b + a$ and $a b = b a $. * Additive identity: $0 + a = a + 0 = a$. * Multiplicative identity: $1 a = a 1 = a$. * Additive inverses: $a + (-a) = (-a) + a = 0$. * Multiplicative inverses for every $a \neq 0$: $ a a^{-1} = a^{-1} a = 1$. * Distributivity: $a ( b + c) = (a b) + (a c)$. ````{prf:example} Examples of fields :label: ex-la-field-1 * The set of real numbers $\RR$ is a field. * The set of complex numbers $\CC$ is a field. * The Galois field GF-2 is the the set $\{ 0, 1 \}$ with modulo-2 additions and multiplications. ```` ## Vector Spaces We are now ready to define a vector space. A vector space involves two sets. One set $\VV$ contains the vectors. The other set $\FF$ (a field) contains scalars which are used to scale the vectors. ````{prf:definition} Vector space :label: def-la-vector-space A set $\VV$ is called a *vector space* over the field $\FF$ (or a $\FF$-vector space) if there exist two mappings: * Vector addition: $+ : \VV \times \VV \to \VV$ mapping $(\bv_1, \bv_2) \to \bv_1 + \bv_2$ for any $\bv_1, \bv_2 \in \VV$ to another vector in $\VV$ denoted by $\bv_1 + \bv_2$ * Scalar multiplication: $\cdot : \FF \times \VV \to \VV$ mapping $(\alpha, \bv) \to \alpha \cdot \bv$ with $\alpha \in \FF$ and $\bv \in \VV$ to another vector in $\VV$ denoted by $\alpha \cdot \bv$ or just $\alpha \bv$ which satisfy following requirements: 1. $(\VV, +)$ is a commutative group. 1. Scalar multiplication $\cdot$ distributes over vector addition $+$: $$ \alpha (\bv_1 + \bv_2) = \alpha \bv_1 + \alpha \bv_2 \quad \forall \alpha \in \FF; \forall \bv_1, \bv_2 \in \VV. $$ 1. Addition in $\FF$ distributes over scalar multiplication $\cdot$: $$ ( \alpha + \beta) \bv = (\alpha \bv) + (\beta \bv) \quad \forall \alpha, \beta \in \FF; \forall \bv \in \VV. $$ 1. Multiplication in $\FF$ commutes over scalar multiplication: $$ (\alpha \beta) \cdot \bv = \alpha \cdot (\beta \cdot \bv) = \beta \cdot (\alpha \cdot \bv) = (\beta \alpha) \cdot \bv \quad \forall \alpha, \beta \in \FF; \forall \bv \in \VV. $$ 1. Scalar multiplication from multiplicative identity $1 \in \FF$ satisfies the following: $$ 1 \bv = \bv \quad \forall \bv \in \VV. $$ ```` Some remarks are in order: * $\VV$ as defined above is also known as a $\FF$ vector space. * Elements of $\VV$ are known as vectors. * Elements of $\FF$ are known as scalars. * There are two $0$s involved: $0 \in \FF$ and $\bzero \in \VV$. It should be clear from context which $0$ is being referred to. * $\bzero \in \VV$ is known as the zero vector. * All vectors in $\VV \setminus \{\bzero\}$ are non-zero vectors. * We will typically denote elements of $\FF$ by $\alpha, \beta, \dots$. * We will typically denote elements of $\VV$ by $\bv_1, \bv_2, \dots$. We quickly look at some vector spaces which will appear again and again in our discussions. ### N-Tuples ````{prf:example} $n$-tuples as a vector space :label: def-la-n-tuple-vector-space Let $\FF$ be some field. The set of all $n$-tuples $(a_1, a_2, \dots, a_n)$ with $a_1, a_2, \dots, a_n \in \FF$ is denoted as $\FF^n$. This is a vector space over $\FF$ with the operations of coordinate-wise addition and scalar multiplication. Let $\bu, \bv \in \FF^n$ with $$ \bu = (u_1, \dots, u_n) $$ and $$ \bv = (v_1, \dots, v_n). $$ Vector addition is defined as $$ \bu + \bv \triangleq (u_1 + v_1, \dots, u_n + v_n). $$ The zero vector is defined as: $$ \bzero = (0, \dots, 0). $$ Let $c \in \FF$. Scalar multiplication is defined as $$ c \bu \triangleq (c u_1, \dots, c u_n). $$ $\bu, \bv$ are called equal if $u_1 = v_1, \dots, u_n = v_n$. In matrix notation, vectors in $\FF^n$ can also be written as row vectors: $$ \bu = \begin{bmatrix} u_1 & \dots & u_n \end{bmatrix} $$ or column vectors: $$ \bu = \begin{bmatrix} u_1 \\ \vdots \\ u_n \end{bmatrix}. $$ We next verify that $\FF^n$ equipped with the vector addition and scalar multiplication defined above satisfies all the properties of a vector space. Let us assume $\bx, \by, \bz \in \FF^n$ and $\alpha, \beta, \gamma \in \FF$. We can now verify all the properties of the vector space: 1. $\FF^n$ is closed under vector addition. $$ \bx + \by = (x_1 + y_1, \dots, x_n + y_n). $$ Since $x_i + y_i \in \FF$, hence $\bx + \by \in \FF^n$. 1. Vector addition is associative. $$ \bx + (\by + \bz) &= (x_1, \dots, x_n) + ((y_1, \dots, y_n) + (z_1, \dots, z_n))\\ &= (x_1, \dots, x_n) + (y_1 + z_1, \dots, y_n + z_n)\\ &= (x_1 + (y_1 + z_1), \dots, x_n + (y_n + z_n))\\ &= ((x_1 + y_1) + z_1, \dots, (x_n + y_n) + z_n)\\ &= (x_1+y_1, \dots, x_n + y_n) + (z_1, \dots, z_n)\\ &= ((x_1, \dots, x_n) + (y_1, \dots, y_n)) + (z_1, \dots, z_n)\\ &= (\bx + \by) + \bz. $$ 1. Vector addition is commutative. $$ \bx + \by = (x_1 + y_1, \dots, x_n + y_n) = (y_1 + x_1, \dots, y_n + x_n) = \by + \bx . $$ 1. Additive identity: $$ \bx + \bzero = (x_1, \dots, x_n) + (0, \dots, 0) = (x_1, \dots, x_n) = \bx. $$ Since commutativity is already established, hence: $$ \bzero + \bx = \bx + \bzero = \bx. $$ Thus, $\bzero$ is the additive identity element. 1. Additive inverse: Let $$ \bu = (-x_1, \dots, -x_n). $$ Then, $$ \bx + \bu = (x_1, \dots, x_n) + (-x_1, \dots, -x_n) = (x_1 + (-x_1), \dots, x_n + (-x_n)) = (0, \dots, 0) = \bzero. $$ By commutativity $\bu + \bx = \bx + \bu = \bzero$. Thus, every vector has an additive inverse. We can write $\bu = -\bx$. 1. Scalar multiplication distributes over vector addition. $$ \alpha (\bx + \by) &= \alpha (x_1 + y_1, \dots, x_n + y_n) \\ &= (\alpha (x_1 + y_1), \dots, \alpha (x_n + y_n))\\ &= (\alpha x_1 + \alpha y_1, \dots, \alpha x_n + \alpha y_n)\\ &= (\alpha x_1, \dots, \alpha x_n) + (\alpha y_1, \dots, \alpha y_n)\\ &= \alpha (x_1, \dots, x_n) + \alpha (y_1, \dots, y_n)\\ &= \alpha \bx + \alpha \by. $$ 1. Addition in $\FF$ distributes over scalar multiplication. $$ (\alpha + \beta) \bx &= (\alpha + \beta) (x_1, \dots, x_n)\\ &= ((\alpha + \beta) x_1, \dots, (\alpha + \beta)x_n)\\ &= (\alpha x_1 + \beta x_1, \dots, \alpha x_n + \beta x_n)\\ &= (\alpha x_1, \dots, \alpha x_n) + (\beta x_1, \dots, \beta x_n)\\ &= \alpha \bx + \beta \bx. $$ 1. Multiplication commutes over scalar multiplication: $$ (\alpha \beta) \bx &= (\alpha \beta) (x_1, \dots, x_n)\\ &= ((\alpha \beta)x_1, \dots, (\alpha \beta)x_n)\\ &= (\alpha (\beta x_1), \dots, \alpha (\beta x_n))\\ &= \alpha (\beta x_1, \dots, \beta x_n)\\ &= \alpha (\beta (x_1, \dots, x_n))\\ &= \alpha (\beta \bx). $$ Similarly, $$ (\alpha \beta) \bx = (\beta \alpha) \bx = \beta (\alpha \bx). $$ 1. Scalar multiplication from multiplicative identity of $\FF$. $$ 1 \bx = 1 (x_1, \dots, x_n) = (x_1, \dots, x_n) = \bx. $$ Thus, $\FF^n$ supports all the properties of a vector space. It is indeed a vector space. ```` ```{prf:example} A field is a vector space :label: ex-field-is-vector-space A field of scalars $\FF$ is a vector space over $\FF$ in its own right. One way to see this is by treating the scalar as a tuple with one value (i.e., 1-tuple). So, we can write it as $\FF^1$. The real line $\RR$ is a vector space in its own right as $\RR^1$. Similarly, the complex plane $\CC$ is a vector space. More formally, let $\VV = \FF$. We will call the element of $\VV$ as vectors and elements of $\FF$ as scalars. 1. For every $x \in \FF$, let $\bx$ be corresponding vector in $\VV$ with $\bx = x$. 1. Define vector addition on $\VV$ as as the corresponding addition in the field $\FF$: $$ \bx + \by = x + y \Forall \bx, \by \in \VV. $$ 1. Define scalar multiplication on $\VV$ as the corresponding multiplication in the field $\FF$: $$ \alpha \bx = \alpha x \Forall \alpha \in \FF and \bx \in \VV. $$ 1. Define zero vector as $0 \in \FF$: $\bzero = 0$. We can now verify all the properties of the vector space: 1. $\VV$ is closed under vector addition. Let $\bx + \by \in \VV$. Then, $\bx + \by = x + y$. Since $x + y \in \FF$, hence $\bx + \by \in \VV$. 1. Vector addition is associative. For every $\bx, \by, \bz \in \VV$: $$ \bx + (\by + \bz) = x + (y + z) = (x + y) + z = (\bx + \by) + \bz. $$ 1. Vector addition is commutative. $$ \bx + \by = x + y = y + x = \by + \bx. $$ 1. For every $\bx \in \VV$, $$ \bx + \bzero = x + 0 = x = \bx = x = 0 + x = \bzero + \bx. $$ Thus, $\bzero$ is the additive identity element. 1. Let $\bx \in \VV$. Define $\by = -x$. Since $-x \in \FF$, hence $\by \in \VV$. Now, $$ \bx + \by = x + (-x) = 0 = \bzero. $$ Thus, every vector has an additive inverse. 1. Scalar multiplication distributes over vector addition. Let $\alpha \in \FF$ and $\bx, \by \in \VV$. $$ \alpha (\bx + \by) = \alpha (x + y) = \alpha x + \alpha y = \alpha \bx + \alpha \by. $$ 1. Addition in $\FF$ distributes over scalar multiplication. Let $\alpha, \beta \in \FF$ and $\bx \in \VV$. $$ (\alpha + \beta) \bx = (\alpha + \beta) x = \alpha x + \beta x = \alpha \bx + \beta \bx. $$ 1. Multiplication commutes over scalar multiplication: $$ (\alpha \beta) \bx = (\alpha \beta) x = \alpha (\beta x) = \alpha (\beta \bx). $$ 1. Scalar multiplication from multiplicative identity of $\FF$. $$ 1 \bx = 1 x = x = \bx. $$ Thus, $\VV=\FF$ satisfies all requirements of being a vector space. It is indeed a vector space in its own right. ``` ### Matrices ````{prf:example} Matrices :label: def-la-matrix-vector-space Let $\FF$ be some field. A matrix is an array of the form $$ \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1N} \\ a_{21} & a_{22} & \dots & a_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{M 1} & a_{M 2} & \dots & a_{MN} \\ \end{bmatrix} $$ with $M$ rows and $N$ columns where $a_{ij} \in \FF$. The set of these matrices is denoted as $\FF^{M \times N}$ which is a vector space with operations of matrix addition and scalar multiplication. Let $A, B \in \FF^{M \times N}$. Matrix addition is defined by $$ (A + B)_{ij} \triangleq A_{ij} + B_{ij}. $$ Let $c \in \FF$. Scalar multiplication is defined by $$ (cA)_{ij} \triangleq c A_{ij}. $$ ```` ### Polynomials ````{prf:example} Polynomials :label: def-la-polynomial-vector-space Let $\FF[x]$ denote the set of all polynomials with coefficients drawn from field $\FF$. i.e. if $f(x) \in \FF[x]$, then it can be written as $$ f(x) = a_n x^n + a_{n-1}x^{n -1} + \dots + a_1 x + a_0 $$ where $a_i \in \FF$. The set $\FF[x]$ is a vector space with usual operations of addition and scalar multiplication $$ f(x) + g(x) = (a_n + b_n)x^n + \dots + (a_1 + b_1 ) x + (a_0 + b_0). $$ $$ c f(x) = c a_n x^n + \dots + c a_1 x + c a_0. $$ ```` ### Vector Space Identities Some useful identities are presented here. ````{prf:theorem} Uniqueness of additive identity :label: res-la-vec-space-zero-unique The $\bzero$ vector in a vector space $\VV$ is unique. ```` ```{prf:proof} Assume that there is another vector $\bo$ satisfying $$ \bv + \bo = \bo + \bv = \bv \Forall \bv \in \VV. $$ Then, in particular, it satisfies: $\bzero + \bo = \bzero$. At the same time, we have $\bo = \bo + \bzero$. Thus, $$ \bzero = \bzero + \bo = \bo + \bzero = \bo. $$ Thus, $\bzero$ is unique. ``` ````{prf:theorem} Cancellation law :label: res-la-vs-cancellation-law Let $\VV$ be an $\FF$ vector space. Let $\bx, \by, \bz$ be some vectors in $\VV$ such that $\bx + \bz = \by + \bz$. Then $\bx = \by$. ```` ```{prf:proof} Since $\bz \in \VV$, there exists an additive inverse $\bv \in \VV$ such that $\bz + \bv = \bzero$. Now $$ \bx = \bx + \bzero = \bx + (\bz + \bv) = (\bx + \bz) + \bv = (\by + \bz) + \bv = \by + (\bz + \bv) = \by + \bzero = \by. $$ ``` ````{prf:corollary} Uniqueness of additive inverse :label: res-la-vec-space-add-inv-unique The additive inverse of a vector $\bx$ in $\VV$ is unique. ```` ```{prf:proof} Let $\by$ and $\bz$ be additive inverses of $\bx$. Then, we have: $$ \bx + \by = \bzero = \bx + \bz. $$ By cancellation law, $\by = \bz$. Thus, the additive inverse of a vector is unique. ``` ````{prf:theorem} :label: res-la-vec-space-props-zero-vec In a vector space $\VV$ the following statements are true 1. $0 \bx = \bzero \Forall \bx \in \VV$. 1. $a \bzero = \bzero \Forall a \in \FF$. 1. $(-a)\bx = - (a \bx) = a(- \bx) \Forall a \in \FF \text{ and } \bx \in \VV$. ```` ```{prf:proof} (1) $0 \bx = \bzero \Forall \bx \in \VV$. By distributive law: $$ 0 \bx = (0 + 0) \bx = 0 \bx + 0 \bx. $$ By existence of zero vector: $$ 0 \bx = \bzero + 0 \bx. $$ Thus, $$ 0 \bx = 0 \bx + 0 \bx = \bzero + 0 \bx. $$ Now, by cancellation law: $$ 0 \bx = \bzero. $$ (2) $a \bzero = \bzero \Forall a \in \FF$. Due to additive identity and distribution law: $$ a \bzero = a (\bzero + \bzero) = a \bzero + a \bzero. $$ Due to additive identity: $$ a \bzero = \bzero + a \bzero. $$ Combining $$ a \bzero + a \bzero = \bzero + a \bzero. $$ Now applying the cancellation law, we get: $$ a \bzero = \bzero. $$ (3) $(-a)\bx = - (a \bx) = a(- \bx) \Forall a \in \FF \text{ and } \bx \in \VV$. We start with $$ \bzero = 0 \bx = (a + (-a)) \bx = a \bx + (-a)\bx. $$ Thus, $(-a)\bx$ is the additive inverse of $a \bx$. Thus, $ (-a)\bx = -(a\bx)$. Similarly, $$ \bzero = a \bzero = a (\bx + (-\bx)) = a \bx + a (-\bx). $$ Thus, $a (-\bx)$ is also additive inverse of $a \bx$. Thus, $a (-\bx) = - (a \bx)$. ``` ## Linear Independence ````{prf:definition} Linear combination :label: def-la-linear-combination A *linear combination* of two vectors $\bv_1, \bv_2 \in \VV$ is defined as $$ \alpha \bv_1 + \beta \bv_2 $$ where $\alpha, \beta \in \FF$. A *linear combination* of $p$ vectors $\bv_1,\dots, \bv_p \in \VV$ is defined as $$ \sum_{i=1}^{p} \alpha_i \bv_i $$ where $\alpha_i \in \FF$. ```` Note that a linear combination *always* consists of a *finite* number of vectors. ````{prf:definition} Linear combination vector :label: def-la-linear-combination-2 Let $\VV$ be a vector space and let $S$ be a nonempty subset of $\VV$. A vector $\bv \in \VV$ is called a *linear combination* of vectors of $S$ if there exist a finite number of vectors $\bs_1, \bs_2, \dots, \bs_n \in S$ and scalars $a_1, \dots, a_N$ in $\FF$ such that $$ \bv = a_1 \bs_1 + a_2 \bs_2 + \dots a_n \bs_n. $$ We also say that $v$ is a linear combination of $\bs_1, \bs_2, \dots, \bs_n$ and $a_1, a_2, \dots, a_n$ are the coefficients of linear combination. ```` ```{prf:definition} Trivial linear combination :label: def-la-trivial-linear-comb A linear combination $a_1 \bs_1 + a_2 \bs_2 + \dots a_n \bs_n$ is called *trivial* if $a_1 = a_2 = \dots = a_n = 0$. $\bzero$ is a trivial linear combination of any subset of $\VV$ as: $$ \bzero = 0 \bs_1 + 0 \bs_2 + \dots 0 \bs_n. $$ ``` A linear combination may refer to the expression itself or its value. e.g. two different linear combinations may have same value. ````{prf:definition} Linear dependence :label: def-la-linearly-dependent A finite set of non-zero vectors $\{\bv_1, \cdots, \bv_p\} \subset \VV$ is called *linearly dependent* if there exist $\alpha_1,\dots,\alpha_p \in \FF$ not all $0$ such that $$ \sum_{i=1}^{p} \alpha_i \bv_i = \bzero. $$ ```` Since $\alpha_i$ are not all zero, hence, it is a non-trivial combination. ````{prf:definition} Linearly dependent set :label: def-la-linearly-dependent-set A set $S \subseteq \VV$ is called *linearly dependent* if there exist a finite number of distinct vectors $\bu_1, \bu_2, \dots, \bu_n \in S$ and scalars $a_1, a_2, \dots, a_n \in \FF$ not all zero, such that $$ a_1 \bu_1 + a_2 \bu_2 + \dots + a_n \bu_n = \bzero. $$ ```` In other words, there exists a non-trivial linear combination which equals $\bzero$. ````{prf:definition} Linearly independent set :label: def-la-linearly-independent-set A set $S \subseteq \VV$ is called *linearly independent* if it is not linearly dependent. ```` ````{prf:definition} Linearly independent vectors :label: def-la-linearly-independent-vectors More specifically a finite set of non-zero vectors $\{\bv_1, \dots, \bv_n\} \subset \VV$ is called *linearly independent* if $$ \sum_{i=1}^{n} \alpha_i \bv_i = 0 \implies \alpha_i = \bzero \Forall 1 \leq i \leq n. $$ ```` In other words, the only linear combination giving us $\bzero$ vector is the trivial linear combination. ````{prf:example} Examples of linearly dependent and independent sets :label: ex-la-lin-dep-ind-sets-1 * The empty set is linearly independent. * A set of a single non-zero vector $\{\bv\}$ is always linearly independent. Prove! * If two vectors are linearly dependent, we say that they are *collinear*. * Alternatively if two vectors are linearly independent, we say that they are not *collinear*. * If a set $\{\bv_1, \dots, \bv_p\}$ is linearly independent, then any subset of it will be linearly independent. Prove! * Adding another vector $\bv$ to the set may make it linearly dependent. When? * It is possible to have an infinite set to be linearly independent. Consider the set of polynomials $\{1, x, x^2, x^3, \dots\}$. This set is infinite, yet linearly independent. ```` ````{prf:theorem} :label: res-la-set-lin-dep-super-set-lin-dep Let $\VV$ be a vector space. Let $S_1 \subseteq S_2 \subseteq \VV$. If $S_1$ is linearly dependent, then $S_2$ is linearly dependent. ```` ````{prf:corollary} :label: res-la-set-lin-ind-subset-lin-ind Let $\VV$ be a vector space. Let $S_1 \subseteq S_2 \subseteq \VV$. If $S_2$ is linearly independent, then $S_1$ is linearly independent. ```` ## Span Vectors can be combined to form other vectors. It makes sense to consider the set of all vectors which can be created by combining a given set of vectors. ````{prf:definition} Span :label: def-la-span Let $S \subset \VV$ be a subset of vectors. The *span* of $S$ denoted as $\langle S \rangle$ or $\span S$ is the set of all possible linear combinations of vectors belonging to $S$. $$ \span S = \langle S \rangle \triangleq \{ \bv \in \VV \ST \bv = \sum_{i=1}^{p} \alpha_i \bv_i \quad \text{for some} \quad \bv_i \in S;\; \alpha_i \in \FF; \; p \in \mathbb{N}\} $$ For convenience we define $\span \EmptySet = \{ \bzero\}$. ```` Span of a finite set of vectors $\{\bv_1, \cdots, \bv_p\}$ is denoted by $\langle \bv_1, \cdots, \bv_p \rangle$. $$ \langle \bv_1, \cdots, \bv_p \rangle = \left \{\sum_{i=1}^{p} \alpha_i \bv_i \ST \alpha_i \in \FF \right \}. $$ We say that a set of vectors $S \subseteq \VV$ spans $\VV$ if $\langle S \rangle = \VV$. ````{prf:proposition} :label: res-la-span-subset-of-vec-space Let $S \subseteq \VV$, then $\Span (S) \subseteq \VV$. ```` ````{prf:definition} Spanning a vector space :label: def-la-spans-generates-vec-space Let $S \subset \VV$. We say that $S$ *spans (or generates)* $\VV$ if $$ \langle S \rangle = \VV. $$ In this case we also say that vectors of $S$ span (or generate) $\VV$. ```` ````{prf:theorem} :label: res-la-ind-set-span-plus-vec-dependent Let $S$ be a linearly independent subset of a vector space $\VV$ and let $\bv \in \VV \setminus S$. Then $S \cup \{ v \}$ is linearly dependent if and only if $ v \in \Span(S)$. ```` ## Basis ````{prf:definition} :label: def-la-basis A set of linearly independent vectors $\BBB$ is called a *basis* of $\VV$ if $\langle \BBB \rangle = \VV$; i.e., $\BBB$ spans $\VV$. ```` ````{prf:example} Basis examples :label: def-la-standard-basis * Since $\Span(\EmptySet) = \{ \bzero \}$ and $\EmptySet$ is linearly independent, $\EmptySet$ is a basis for the zero vector space $\{ 0 \}$. * The basis $\{ \be_1, \dots, \be_N\}$ with $\be_1 = (1, 0, \dots, 0)$, $\be_2 = (0, 1, \dots, 0)$, $\dots$, $\be_N = (0, 0, \dots, 1)$, is called the *standard basis* for $\FF^N$. * The set $\{1, x, x^2, x^3, \dots\}$ is the *standard basis* for $\FF[x]$. Indeed, an infinite basis. Note that though the basis itself is infinite, yet every polynomial $p \in \FF[x]$ is a linear combination of finite number of elements from the basis. ```` We review some properties of bases. ````{prf:theorem} Unique representation :label: res-la-basis-characterization-unique-rep Let $\VV$ be a vector space and $\BBB = \{ \bv_1, \bv_2, \dots, \bv_n\}$ be a subset of $\VV$. Then $\BBB$ is a basis for $\VV$ if and only if each $v \in \VV$ can be uniquely expressed as a linear combination of vectors of $\BBB$. In other words: $$ \bv = a_1 \bv_1 + a_2 \bv_2 + \dots + a_n \bv_n $$ for unique scalars $a_1, \dots, a_n$. ```` This theorem states that a basis $\BBB$ provides a unique representation to each vector $v \in \VV$ where the representation is defined as the $n$-tuple $(a_1, a_2, \dots, a_n)$. ```{prf:proof} Assume that each $\bv \in \VV$ can be expressed uniquely as a linear combination of vectors of $\BBB$. 1. Then $\bzero$ is a unique linear combination of $\BBB$. 1. But $\bzero = 0 \bv_1 + \dots + 0 \bv_n$. 1. Thus, $\BBB$ is linearly independent. 1. Also, $\BBB$ spans $\VV$ since every vector can be expressed as a linear combination. 1. Thus, $\BBB$ is a basis. Assume that $\BBB$ is a basis for $\VV$. 1. Then, $\BBB$ is linearly independent and $\BBB$ spans $\VV$. 1. Let $\bv \in \VV$. 1. Let $\bv = \sum_{i=1}^n a_i \bv_i$ and $\bv = \sum_{i=1}^n b_i \bv_i$ be two different representations of $\bv$ in $\BBB$. 1. Then, $$ &\sum_{i=1}^n a_i \bv_i = \sum_{i=1}^n b_i \bv_i\\ &\iff \sum_{i=1}^n (a_i - b_i) \bv_i = 0. $$ 1. But $\BBB$ is linearly independent. 1. Hence, $a_i - b_i = 0$ for $i = 1, \dots, n$. 1. Thus, $a_i = b_i$ for $i=1,\dots,n$. 1. Hence, every $\bv \in \VV$ has a unique representation as a linear combination of $\BBB$. ``` If the basis is infinite, then the above theorem needs to be modified as follows: ````{prf:theorem} Unique representation for infinite basis :label: res-la-infinite-basis-characterization-unique-rep Let $\VV$ be a vector space and $\BBB$ be a subset of $\VV$. Then $\BBB$ is a basis for $\VV$ if and only if each $\bv \in \VV$ can be uniquely expressed as a linear combination of vectors of $\BBB$: $$ \bv = a_1 \bv_1 + a_2 \bv_2 + \dots + a_n \bv_n $$ for unique scalars $a_1, \dots, a_n$ and unique vectors $\bv_1, \bv_2, \dots \bv_n \in \BBB$. ```` ````{prf:theorem} :label: res-la-finite-basis If a vector space $\VV$ is spanned by a finite set $S$, then some subset of $S$ is a basis for $\VV$. Hence $\VV$ has a finite basis. ```` ````{prf:theorem} Replacement theorem :label: res-la-replacement-theorem Let $\VV$ be a vector space that is spanned by a set $G$ containing exactly $n$ vectors. Let $L$ be a linearly independent subset of $\VV$ containing exactly $m$ vectors. Then $m \leq n$ and there exists a subset $H$ of $G$ containing exactly $n-m$ vectors such that $L \cup H$ spans $\VV$. ```` ````{prf:corollary} :label: res-la-basis-finite-same-cardinality Let $\VV$ be a vector space having a finite basis. Then, every basis for $\VV$ contains the same number of vectors. ```` ## Dimension ````{prf:definition} Dimension of vector space :label: def-la-dimension A vector space $\VV$ is called *finite-dimensional* if it has a basis consisting of a finite number of vectors. This unique number of vectors in any basis $\BBB$ of the vector space $\VV$ is called the *dimension* or *dimensionality* of the vector space. It is denoted as $\dim \VV$. We say: $$ \dim \VV \triangleq |\BBB| $$ If $\VV$ is not finite-dimensional, then we say that $\VV$ is *infinite-dimensional*. ```` ````{prf:example} Vector space dimensions :label: ex-la-vec-space-dimensions-1 * Dimension of $\FF^N$ is $N$. * Dimension of $\FF^{M \times N}$ is $MN$. * The vector space of polynomials $\FF[x]$ is infinite dimensional. ```` ````{prf:proposition} :label: res-la-n-dim-vec-space-set-span-basis-lin-ind Let $\VV$ be a vector space with dimension $n$. 1. Any finite spanning set for $\VV$ contains at least $n$ vectors, and a spanning set that contains exactly $n$ vectors is a basis for $\VV$. 1. Any linearly independent subset of $\VV$ that contains exactly $n$ vectors is a basis for $\VV$. 1. Every linearly independent subset of $\VV$ can be extended to a basis for $\VV$. ```` ## Ordered Basis ````{prf:definition} Ordered basis :label: def-la-ordered-basis For a finite dimensional vector space $\VV$, an *ordered basis* is a basis for $\VV$ with a specific order. In other words, it is a finite *sequence* (or tuple) of linearly independent vectors in $\VV$ that spans $\VV$. ```` Typically, we will write an ordered basis as $\BBB = \{ \bv_1, \bv_2, \dots, \bv_n\}$ and assume that the basis vectors are ordered in the order they appear. With the help of an ordered basis, we can define a coordinate vector. ````{prf:definition} Coordinate vector :label: def-la-coordinate-vector Let $\BBB = \{ \bv_1, \dots, \bv_n\}$ be an ordered basis for $\VV$. For any $\bx \in \VV$, let $\alpha_1, \dots, \alpha_n$ be unique scalars such that $$ x = \sum_{i=1}^n \alpha_i \bv_i. $$ The *coordinate vector* of $\bx$ relative to $\BBB$ is defined as $$ [\bx]_{\BBB} = \begin{bmatrix} \alpha_1\\ \vdots\\ \alpha_n \end{bmatrix}. $$ ```` ## Subspaces ````{prf:definition} Subspace :label: def-la-subspace Let $\WW$ be a subset of $\VV$. Then $\WW$ is called a *subspace* if $\WW$ is a vector space in its own right under the same vector addition $+$ and scalar multiplication $\cdot$ operations. i.e. $$ \begin{aligned} + : &\WW \times \WW \to \WW\\ &(\bw_1, \bw_2) \to \bw_1 + \bw_2 \quad \bw_1, \bw_2 \in \WW \end{aligned} $$ $$ \begin{aligned} \cdot : &\FF \times \WW \to \WW\\ &(\alpha, \bw) \to \alpha \cdot \bw \triangleq \alpha \bw \quad \alpha \in \FF; \bw \in \WW \end{aligned} $$ are defined by restricting $+ : \VV \times \VV \to \VV$ and $\cdot : \VV \times \VV \to \VV$ to $\WW$ and $\WW$ is closed under these operations. ```` ````{prf:example} Trivial subspaces :label: ex-la-trivial-subspaces-1 * $\VV$ is a subspace of $\VV$. * $\{\bzero\}$ is a subspace of any $\VV$. ```` ````{prf:theorem} Subspace characterization :label: res-subspace-verification-condition A subset $\WW \subseteq \VV$ is a subspace of $\VV$ if and only if * $\bzero \in\WW $. * $\bx + \by \in\WW $ whenever $\bx, \by \in\WW$. * $\alpha \bx \in\WW $ whenever $\alpha \in \FF$ and $\bx \in\WW $. In other words, a subset of $\VV$ is a subspace if and only if it contains the zero vector and is closed under vector addition and scalar multiplication. ```` ````{prf:example} Symmetric matrices :label: ex-la-symmetric-matrix-subspace A matrix $M \in \FF^{M \times N}$ is *symmetric* if $$ M^T = M. $$ The set of symmetric matrices forms a subspace of set of all $M\times N$ matrices. ```` ````{prf:example} Diagonal matrices :label: ex-la-diagonal-matrix-subspace A matrix $M$ is called a *diagonal* if $M_{ij} = 0$ whenever $i \neq j$. The set of diagonal matrices is a subspace of $\FF^{M \times N}$. ```` ```{prf:definition} Proper subspace :label: def-la-proper-subspace A subspace $\WW$ of $\VV$ is called a *proper subspace* if $\VV \setminus \WW \neq \EmptySet$. In other words, there are vectors in $\VV$ which are not included in $\WW$. ``` ````{prf:theorem} Intersection of subspaces :label: res-la-subspace-intersection Any intersection of subspaces of a vector space $\VV$ is a subspace of $\VV$. ```` ```{prf:proof} Let $\{W_i \}_{i \in I}$ be a family of subspaces of a vector space $\VV$ indexed by $I$. Let the intersection of the subspaces be: $$ W = \bigcap_{i \in I} W_i. $$ [Zero vector] 1. Since $\bzero \in W_i$ for every $i \in I$, hence $\bzero \in W$. [Vector addition] 1. Let $\bx, \by \in W_i$ for every $i \in I$. 1. Then, $\bx + \by \in W_i$ for every $i \in I$ since $W_i$ are closed under vector addition. 1. Then, $\bx + \by \in W$. 1. Thus, $W$ is closed under vector addition. [Scalar multiplication] 1. Let $\bx \in W_i$ for every $i \in I$ and let $t \in \FF$. 1. Then, $t \bx \in W_i$ for ever $i \in I$ since $W_i$ are closed under scalar multiplication. 1. Thus, $t \bx \in W$. 1. Thus, $W$ is closed under scalar multiplication. Thus, $W$ is a subspace of $\VV$. ``` We note that a union of subspaces is not necessarily a subspace, since its not closed under addition. ````{prf:theorem} Span is a subspace :label: res-la-span-as-subspace Let $\VV$ be a vector space. The span of a set $S \subset \VV$ given by $\span S$ is a subspace of $\VV$. Moreover, any subspace of $\VV$ that contains $S$ must also contain the span of $S$. ```` ```{prf:proof} If $S = \EmptySet$, then by convention, $\span S = \{ \bzero \}$. This happens to be the trivial subspace. We now consider $S$ to be nonempty (possibly infinite). [Zero vector] 1. Since $S$ is nonempty, hence there exists some $\bv \in S$. 1. Then, $0 \bv = \bzero \in \span S$ as it is a linear combination of elements of $S$. [Scalar multiplication] 1. Let $\bv \in \span S$. 1. Then, $\bv = \sum_{i=1}^p t_i \bv_i$ where $\bv_i \in S$, $t_i \in \FF$, $p \in \Nat$. 1. But then for any $t \in \FF$: $$ t \bv = t \left ( \sum_{i=1}^p t_i \bv_i \right ) = \sum_{i=1}^p (t t_i) \bv_i. $$ 1. Thus, $t\bv$ is also a linear combination of elements of $S$. 1. Thus, $\span S$ is closed under scalar multiplication. [Vector addition] 1. Let $\bx, \by \in \span S$. 1. Let $\bx = \sum_{i=1}^p r_i \bx_i$ and $\by = \sum_{i=1}^q t_i \by_i$ be linear combinations of elements of $S$. 1. Then, $$ \bx + \by = \sum_{i=1}^p r_i \bx_i + \sum_{i=1}^q t_i \by_i $$ is also a linear combination of (up to $p+q$) elements of $S$. 1. Thus, $\bx + \by \in \span S$. 1. Thus, $\span S$ is closed under vector addition. Combining, $\span S$ is a linear subspace. Let $W$ be a subspace such that $S \subseteq W$. 1. Let $\bv \in \span S$. 1. Then, $\bv = \sum_{i=1}^p t_i \bv_i$ is a linear combination of elements of $S$. 1. But $W$ is closed under linear combinations and $S \subseteq W$. 1. Thus, $\bv \in W$. 1. Thus, $\span S \subseteq W$. ``` This theorem is quite useful. It allows us to construct subspaces from a given basis. Let $\BBB$ be a basis of an $n$ dimensional space $\VV$. There are $n$ vectors in $\BBB$. We can create $2^n$ distinct subsets of $\BBB$. Thus we can easily construct $2^n$ distinct subspaces of $\VV$. Choosing some other basis lets us construct another set of subspaces. An $n$-dimensional vector space has infinite number of bases. Correspondingly, there are infinite possible subspaces. ```{prf:definition} Partial order on subspaces :label: def-la-subspace-partial-order Let $\VV$ be a vector space. If $\WW_1$ and $\WW_2$ are two subspaces of $\VV$ then we say that $\WW_1$ is *smaller than* $\WW_2$ if $\WW_1 \subset \WW_2$; i.e., $\WW_1$ is a proper subset of $\WW_2$. We denote this partial order by $\WW_1 \prec \WW_2$. If $\WW_1 \subseteq \WW_2$, we denote this is $\WW_1 \preceq \WW_2$. ``` ````{prf:theorem} Span as the smallest subspace :label: res-la-span-is-smallest Let $\VV$ be a vector space. Let $\bv_1, \dots, \bv_p$ be some arbitrary vectors in $\VV$. Let $S = \{ \bv_1, \dots, \bv_p \}$. Let the span of $S$ be denoted as $$ U = \span S = \langle \bv_1, \dots, \bv_p \rangle. $$ Let $W$ be the smallest subspace containing the vectors in $S$. Then $$ \WW = U. $$ i.e. $\WW$ is same as the span of $\{ \bv_1, \dots, \bv_p \}$. In other words, $\span S$ is the smallest subspace containing $S$. ```` ```{prf:proof} Since $\WW$ contains $S$, hence $\span S \subseteq W$ due to {prf:ref}`res-la-span-as-subspace`. $\span S$ is also a linear subspace. So $\WW = \span S$ must hold. ``` If the vector space $\VV$ is not finite dimensional, then its subspaces may or may not be finite dimensional. E.g., if $W$ is a span of a fixed $p$ number of vectors from $\VV$, then it is finite dimensional with $\dim W \leq p$ irrespective of whether $\VV$ is finite dimensional or not. However, if $\VV$ is finite dimensional, then its subspaces must be finite dimensional. ````{prf:theorem} Subspaces of a finite dimensional vector space :label: res-la-subspace-dimension Let $\WW$ be a subspace of a finite-dimensional vector space $\VV$. Then $\WW$ is finite dimensional and $$ \dim \WW \leq \dim \VV. $$ Moreover, if $$ \dim \WW = \dim \VV, $$ then $\WW = \VV$. ```` ```{prf:proof} If $\VV$ is finite dimensional, then it has a finite basis of say $n$ basis vectors. Since $\WW \subseteq \VV$ hence the basis spans $\WW$ too. Thus, dimension of $\WW$ cannot be greater than $n$. Now, assume that $$ n = \dim \WW = \dim \VV. $$ 1. Let $\BBB$ be a basis for $\WW$. 1. Then $\BBB$ spans $\WW$ and contains $n$ linearly independent vectors. 1. Since $\WW \subseteq \VV$, hence $\BBB \subseteq \VV$. 1. But $n = \dim \VV$. 1. Hence, any set of $n$ linearly independent vectors must be a basis for $\VV$ too. 1. Thus, $\BBB$ is a basis for $\VV$. 1. Thus, $\VV = \WW = \span \BBB$. ``` ````{prf:corollary} :label: res-la-subspace-basis-extend-full-basis If $\WW$ is a subspace for a finite-dimensional vector space $\VV$ then any basis for $\WW$ can be extended to a basis for $\VV$. ```` ````{prf:definition} Subspace codimension :label: def-subspace-codimension Let $\VV$ be a finite dimensional vector space and $\WW$ be a subspace of $\VV$. The *codimension* of $\WW$ is defined as $$ \text{codim} \WW = \dim \VV - \dim \WW. $$ ```` ## Direct Sum of Vector Spaces Consider two vector spaces $\VV$ and $\WW$ over same scalar field $\FF$. Often, it is useful to consider the Cartesian product set $\VV \times \WW$ and add a vector space structure to it. One common example is $\VV=\RR^n$, $\WW=\RR^m$ and $\VV \times \WW = \RR^{n+m}$. ```{prf:definition} Direct sum of vector spaces :label: def-vs-direct-sum-vector-spaces Let $\VV$ and $\WW$ be two different vector spaces over some field $\FF$. A vector space structure over the field $\FF$ can be introduced to the set $\VV \times \WW$ as per the following definitions. 1. Let $\bzero_v \in \VV$ and $\bzero_w \in \WW$ be the additive identities of $\VV$ and $\WW$ respectively. The additive identity of $\VV \times \WW$ is given by $$ \bzero = (\bzero_v, \bzero_w). $$ 1. [Vector addition] Let $(\bx, \bu)$ and $(\by, \bv)$ be in $\VV \times \WW$. Then, their sum is defined as: $$ (\bx, \bu) + (\by, \bv) \triangleq (\bx + \by, \bu + \bv). $$ 1. [Scalar multiplication] Let $(\bx, \bu) \in \VV \times \WW$ and $\alpha \in \FF$. Then, the scalar multiplication is defined as: $$ \alpha (\bx, \bu) \triangleq (\alpha \bx, \alpha \bu). $$ $\VV \times \WW$ equipped with these definitions is a vector space over $\FF$ in its own right and is called the *direct sum* of $\VV$ and $\WW$ denoted by $\VV \oplus \WW$. ``` ```{note} Some authors prefer to call $\VV \oplus \WW$ as *direct product* (Cartesian product with vector space structure) and reserve the term *direct sum* for the sums within the same vector space ({prf:ref}`def-vs-direct-sum-same-space` below). For them, external direct sum is a direct product and internal direct sum is a direct sum. ``` ```{prf:example} :label: ex-la-direct-sum-1 With the definition of direct sum given above, we have: $$ \FF^2 = \FF \oplus \FF $$ or more generally, $$ \FF^{n} = \FF \oplus \FF \oplus \dots \oplus \FF = \bigoplus_{i=1}^n \FF. $$ Specifically, $$ \RR^n = \bigoplus_{i=1}^n \RR. $$ Also, $$ \RR^{n + m} = \RR^n \times \RR^m. $$ ``` (sec:la:set-arithmetic)= ## Sets in Vector Spaces ### Set Arithmetic ```{prf:definition} Arithmetic on sets :label: def-vs-set-arithmetic Let $C$, $D$ be subsets of an $\FF$ vector space $\VV$. Let $\bz \in \VV$. Let $\lambda \in \FF$. Let $\Lambda \subseteq \FF$. The addition of sets is defined as: $$ C + D \triangleq \{ \bx + \by \ST \bx \in C, \by \in D \}. $$ The subtraction of sets is defined as: $$ C - D \triangleq \{ \bx - \by \ST \bx \in C, \by \in D \}. $$ Addition of a set with a vector is defined as: $$ \bz + C \triangleq \{ \bz + \bx \ST \bx \in C\} = \{ \bz \} + C. $$ Subtraction of set with a vector is defined as: $$ C - \bz \triangleq \{ \bx - \bz \ST \bx \in C\} = C - \{ \bz \}. $$ Scalar multiplication of a set with a scalar is defined as: $$ \lambda C \triangleq \{ \lambda \bx \ST \bx \in C \}. $$ Multiplication of a set of scalars with a set of vectors is defined as: $$ \Lambda C \triangleq \bigcup_{\lambda \in \Lambda} \lambda C. $$ Multiplication of a set of scalars with a vector is defined as: $$ \Lambda \bz \triangleq \Lambda \{ \bz \} = \{ \lambda \bz \ST \lambda \in \Lambda\}. $$ ``` ### Symmetry ```{prf:definition} Symmetric reflection :label: def-vs-symmetric-reflection The *symmetric reflection* of a set $C$ across the origin is given by $-C = (-1) C$. ``` ```{prf:definition} Symmetric set :label: def-vs-symmetric-set A set $C$ is said to be *symmetric* if $-C = C$ holds true. ``` If a nonempty set is symmetric, it must contain $\bzero$ since $-\bzero = \bzero$. ### Set Arithmetic Properties ```{prf:theorem} Set vector arithmetic identities :label: res-vs-set-vec-arithmetic Let $C$, $D$ be subsets of an $\FF$ vector space $\VV$. Let $\bz \in \VV$. Let $\lambda \in \FF$. Let $\Lambda \subseteq \FF$. $$ C = (C + \bz) - \bz. $$ $$ C \subseteq D \iff C + \bz \subseteq D + \bz. $$ ``` ```{prf:proof} We show that $C = (C + \bz) - \bz$. 1. Let $\bx \in C$. 1. Then, $\bx = (\bx + \bz) - \bz$. 1. Then, $\bx + \bz \in C+\bz$. 1. Then, $(\bx + \bz) - \bz \in (C + \bz) - \bz$. 1. Thus, $C \subseteq (C + \bz) - \bz$. 1. Conversely, let $\bx \in (C + \bz) - \bz$. 1. Then, $\bx + \bz \in C+\bz$. 1. But then, $\bx \in C$. 1. Thus, $(C + \bz) - \bz \subseteq C$. 1. Combining $C = (C + \bz) - \bz$. We show that $C \subseteq D \iff C + \bz \subseteq D + \bz$. Assume $C \subseteq D$. 1. Let $\bx \in C + \bz$. 1. Then, $\bx - \bz \in C$. 1. Then, $\bx - \bz \in D$ since $C \subseteq D$. 1. Then, $\bx \in D + \bz$. 1. Thus, $C + \bz \in D + \bz$. Now, assume $C + \bz \subseteq D + \bz$. 1. Let $\bx \in C$. 1. Then, $\bx + \bz \in C + \bz$. 1. Then, $\bx + \bz \in D + \bz$ since $C + \bz \subseteq D + \bz$. 1. Then, $\bx \in D$. 1. Thus, $C \subseteq D$. ``` ```{prf:theorem} Properties of set arithmetic :label: res-vs-set-arithmetic-props Let $\VV$ be a vector space over a field $\FF$. Let $C, D, E \subseteq \VV$ and $\alpha, \beta \in \FF$. 1. Set addition is commutative: $$ C + D = D + C. $$ 1. Set addition is associative: $$ C + (D + E) = (C + D) + E. $$ 1. Scalar multiplication with a set commutes with multiplication in $\FF$: $$ \alpha (\beta C) = (\alpha \beta) C = (\beta \alpha )C = \beta (\alpha C). $$ 1. Scalar multiplication distributes over set addition: $$ \alpha (C + D) = (\alpha C) + (\alpha D). $$ 1. The set $\{ \bzero \}$ is the identity element for set addition: $$ C + \{ \bzero \} = \{ \bzero \} + C = C. $$ 1. The set $F = C + (-C)$ is symmetric and $\bzero \in F$. 1. $ (\alpha + \beta) C \subseteq \alpha C + \beta C$. ``` ```{prf:proof} We shall prove some of the properties. [Commutativity] 1. Let $\bu \in C + D$. 1. Then, there exists, $\bx \in C$ and $\by \in D$ such that $\bu = \bx + \by$. 1. But then, $\bu = \by + \bx$ since vector addition is commutative. 1. Thus, $\bu \in D + C$. 1. Thus, $C + D \subseteq D + C$. 1. Similarly, $D + C \subseteq C + D$. [Associativity] 1. Let $\ba \in C + (D + E)$. 1. Then, there exists $\bc \in C$ and $\bb \in D + E$ such that $\ba = \bc + \bb$. 1. Then, there exists $\bd \in D$ and $\be \in E$ such that $\bb = \bd + \be$. 1. Thus, $\ba = \bc + (\bd + \be)$. 1. But vector addition is associative. 1. Thus, $\ba = (\bc + \bd) + \be$. 1. Then, $\bc + \bd \in C + D$. 1. Thus, $\ba \in (C + D) + E$. 1. Thus, $C + (D + E) \subseteq (C + D) + E$. 1. Similarly reasoning shows that $(C + D) + E \subseteq C + (D + E)$. $ (\alpha + \beta) C \subseteq \alpha C + \beta C$ 1. Let $\bx \in (\alpha + \beta) C$. 1. Then, there exists $\by \in C$ such that $\bx = (\alpha + \beta) \by$. 1. Then, $\bx = \alpha \by + \beta \by$. 1. Then, $\alpha \by \in \alpha C$ and $\beta \by \in \beta C$. 1. Thus, $\bx \in \alpha C + \beta C$. 1. Thus, $(\alpha + \beta) C \subseteq \alpha C + \beta C$. ``` Additive inverses don't exist for sets containing more than one element. ```{prf:theorem} Distributive law for set sum over intersection :label: res-vs-set-intersect-sum-dist Let $\VV$ be a vector space over a field $\FF$. Let $C, D, E \subseteq \VV$. Then $$ (C \cap D) + E \subseteq (C + E) \cap (D + E). $$ ``` ```{prf:proof} We show that $(C \cap D) + E \subseteq (C + E) \cap (D + E)$. 1. Let $\bv \in (C \cap D) + E$. 1. Then, $\bv = \bx + \by$ such that $\bx \in (C \cap D)$ and $\by \in E$. 1. Then, $\bx \in C$, $\bx \in D$ and $\by \in E$. 1. Thus, $\bx + \by \in C + E$ and $\by + \by \in D + E$. 1. Thus, $\bv = \bx + \by \in (C + E) \cap (D + E)$. 1. Thus, $(C \cap D) + E \subseteq (C + E) \cap (D + E)$. We mention that $ (C + E) \cap (D + E) \not\subseteq (C \cap D) + E$ in general. Here is an example. 1. Consider $\VV = \RR^2$. 1. Let $C$ to be the $x$-axis. 1. Let $D$ to be the $y$-axis. 1. Let $E$ to be the line $\{ (x, y) \ST x = y \}$. 1. Both $C+E$ and $D+E$ are the whole plane $\RR^2$. 1. Thus, $(C + E) \cap (D + E) = \RR^2$. 1. But $C \cap D = \{ \bzero \}$. 1. Thus, $(C \cap D) + E = E$. 1. Clearly, $(C + E) \cap (D + E) \not\subseteq (C \cap D) + E$. ``` ### Direct Sums ```{prf:definition} (External) direct sum over two different vector spaces :label: def-vs-direct-sum-two-spaces Let $\VV$ and $\WW$ be vector spaces over $\FF$. Let $C \subseteq \VV$ and $D \subseteq \WW$. Then, the *direct sum* of $C$ and $D$ is defined as $$ C \oplus D \triangleq \{ \bx = (\by, \bz) \ST \by \in C, \bz \in D \}. $$ $C \oplus D$ is a subset of the {prf:ref}`(direct sum) vector space ` $\VV \oplus \WW$. ``` ```{prf:definition} (Internal) direct sum of sets in same vector space :label: def-vs-direct-sum-same-space Let $C,D$ be subsets of $\VV$. If each vector $\bx \in C+D$ can be expressed *uniquely* in the form $$ \bx = \by + \bz, \by \in C, \bz \in D; $$ then the sum $C + D$ is called a *direct sum* of $C$ and $D$ and is denoted by $C \oplus D$. ``` The key idea behind a direct sum is that it enables a unique decomposition of a vector into its components belonging to individual sets. ```{prf:theorem} :label: res-la-valid-direct-sum-on-subsets Two subsets $C, D$ of $\VV$ are eligible for a direct sum if and only if the symmetric sets $C - C$ and $D - D$ have only the zero vector $\bzero$ in common. ``` If two subspaces of $\VV$ have only $\bzero$ in common, then any vector in their sum can be decomposed uniquely between the two subspaces. ## Sums of Subspaces ```{prf:definition} (Internal) direct sum of subspaces :label: def-vs-direct-sum-subspaces If $\WW_1$ and $\WW_2$ are two subspaces of $\VV$ such that $\WW_1 \cap \WW_2 = \{ \bzero \}$, then the *direct sum* of $\WW_1$ and $\WW_2$ is defined as: $$ \WW_1 \oplus \WW_2 \triangleq \WW_1 + \WW_2 = \{ \bx_1 + \bx_2 \ST \bx_1 \in \WW_1, \bx_2 \in \WW_2 \}. $$ If, in particular, $\VV = \WW_1 + \WW_2$, we say that $\VV$ is a *direct sum* of its subspaces $\WW_1$ and $\WW_2$ and write as $\VV = \WW_1 \oplus \WW_2$. ``` ```{prf:example} Vector space as direct sum of spans of basis vectors :label: ex-la-vec-space-dir-sum-basis-vec-spans The spans of basis vectors have only $\bzero$ in common. They indeed offer a unique decomposition of any vector in the space. Thus, for a finite dimensional space $\VV$ with a basis $\BBB = \{\bv_1, \dots \bv_n \}$ $$ \VV = \bigoplus_{i=1}^n \span \{ \bv_i \}. $$ ``` ```{prf:theorem} Dimension of sum of subspaces :label: res-la-dim-sum-subspaces Let $W_1$ and $W_2$ be finite dimensional subspaces of a vector space $\VV$. Then $$ \dim (W_1 + W_2) = \dim W_1 + \dim W_2 - \dim (W_1 \cap W_2). $$ ``` ```{prf:theorem} Dimension of direct sum of subspaces :label: res-la-dim-direct-sum-subspaces Let $W_1$ and $W_2$ be finite dimensional subspaces of a vector space $\VV$ such that $W_1 \cap W_2 = \{\bzero \}$. Then $$ \dim (W_1 \oplus W_2) = \dim W_1 + \dim W_2. $$ ``` ```{prf:proof} We note that $W_1 \cap W_2 = \{\bzero \}$ implies that $\dim (W_1 \cap W_2) = 0$. Rest follows from the previous result {prf:ref}`res-la-dim-sum-subspaces`. ``` ## Real Vector Spaces ```{prf:definition} Real vector space :label: def-la-real-vector-space A *real vector space* $\VV$ is a vector space defined over the real field $\RR$. In other words, the scalars come from the field of real numbers. ``` There are several features associated with the real field. * $\RR$ is {prf:ref}`totally ordered `. * $\RR$ is {prf:ref}`complete `.