Formal Rules

1.1.Typical structures

1.2.Vector subspaces

A central interest in data science is to seek simple description of complex objects. A typical situation is that many instances of some object of interest are initially given as an $m$-tuple $𝒗\in {ℝ}^m$ with large $m$. Assuming that addition and scaling of such objects can cogently be defined, a vector space is obtained, say over the field of reals with an Euclidean distance, $E_m$. Examples include for instance recordings of medical data (electroencephalograms, electrocardiograms), sound recordings, or images, for which $m$ can easily reach in to the millions. A natural question to ask is whether all the $m$ real numbers are actually needed to describe the observed objects, or perhaps there is some intrinsic description that requires a much smaller number of descriptive parameters, that still preserves the useful idea of linear combination. The mathematical transcription of this idea is a vector subspace.

Definition. (Vector Subspace) . $𝒰=(U,S,+,\cdot )$, $U\ne \varnothing$, is a vector subspace of vector space $𝒱=(V,S,+,\cdot )$ over the same field of scalars S, denoted by $𝒰\le 𝒱$, if $U\subseteq V$ and $\forall a,b\in S$, $\forall 𝒖,𝒗\in U$, the linear combination $a𝒖+b𝒗\in U$.

The above states a vector subspace must be closed under linear combination, and have the same vector addition and scaling operations as the enclosing vector space. The simplest vector subspace of a vector space is the null subspace that only contains the null element, $U=\left\{𝟎\right\}$. In fact any subspace must contain the null element $𝟎$, or otherwise closure would not be verified for the particular linear combination $𝒖+(-𝒖)=𝟎$. If $U\subset V$, then $𝒰$ is said to be a proper subspace of $𝒱$, denoted by $𝒰<𝒱$.

Setting $n-m$ components equal to zero in the real space ${ℛ}_m$ defines a proper subspace whose elements can be placed into a one-to-one correspondence with the vectors within ${ℛ}_n$. For example, setting component $m$ of $𝒙\in {ℝ}^m$ equal to zero gives $𝒙={\left[\begin{array}{ccccc}{x}_1& x_2& \dots & x_{m-1}& 0\end{array}\right]}^T$ that while not a member of ${ℝ}^{m-1}$, is in a one-to-one relation with ${𝒙}^{\text{'}}={\left[\begin{array}{cccc}{x}_1& x_2& \dots & x_{m-1}\end{array}\right]}^T\in {ℝ}^{m-1}$. Dropping the last component of $𝒚\in {ℝ}^m$, $𝒚={\left[\begin{array}{ccccc}{y}_1& y_2& \dots & y_{m-1}& y_m\end{array}\right]}^T$ gives vector ${𝒚}^{\text{'}}=\left[\begin{array}{cccc}{y}_1& y_2& \dots & y_{m-1}\end{array}\right]\in {ℝ}^{m-1}$, but this is no longer a one-to-one correspondence since for some given ${𝒚}^{\text{'}}$, the last component $y_m$ could take any value.

octave] 

m=3; x=[1; 2; 0]; xp=x(1:2); disp(xp)

octave] 

y=[1; 2; 3]; yp=y(1:2); disp(yp)

octave] 

Vector subspaces arise in decomposition of a vector space. The converse, composition of vector spaces $𝒰=(U,S,+,\cdot )$ $𝒱=(V,S,+,\cdot )$ is also defined in terms of linear combination. A vector $𝒙\in {ℝ}^3$ can be obtained as the linear combination

but also as

for some arbitrary $a\in ℝ$. In the first case, $𝒙$ is obtained as a unique linear combination of a vector from the set $U=\left\{{\left[\begin{array}{ccc}{x}_1& 0& 0\end{array}\right]}^T|x_1\in ℝ.\right\}$ with a vector from $V=\left\{{\left[\begin{array}{ccc}{0}_{}& x_2& x_3\end{array}\right]}^T|x_2,x_3\in ℝ.\right\}$. In the second case, there is an infinity of linear combinations of a vector from $V$ with another from $W=\left\{{\left[\begin{array}{ccc}{x}_1& x_2& 0\end{array}\right]}^T|x_1,x_2\in ℝ.\right\}$ to the vector $𝒙$. This is captured by a pair of definitions to describe vector space composition.

Definition. Given two vector subspaces $𝒰=(U,S,+,\cdot )$, $𝒱=(V,S,+,\cdot )$ of the space $𝒲=(W,S,+,\cdot )$, the sum is the vector space $𝒰+𝒱=(U+V,S,+,\cdot )$, where the sum of the two sets of vectors $U,V$ is $U+V=\{𝒖+𝒗|𝒖\in U,𝒗\in V\}$.

Definition. Given two vector subspaces $𝒰=(U,S,+,\cdot )$, $𝒱=(V,S,+,\cdot )$ of the space $𝒲=(W,S,+,\cdot )$, the direct sum is the vector space $𝒰\oplus 𝒱=(U\oplus V,S,+,\cdot )$, where the direct sum of the two sets of vectors $U,V$ is $U\oplus V=\{𝒖+𝒗|\exists !𝒖\in U,\exists !𝒗\in V\}$. (unique decomposition)

Since the same scalar field, vector addition, and scaling is used , it is more convenient to refer to vector space sums simply by the sum of the vector sets $U+V$, or $U\oplus V$, instead of specifying the full tuplet for each space. This shall be adopted henceforth to simplify the notation.

octave] 

u=[1; 0; 0]; v=[0; 2; 3]; vp=[0; 1; 3]; w=[1; 1; 0]; disp([u+v vp+w]) 

octave] 

In the previous example, the essential difference between the two ways to express $𝒙\in {ℝ}^3$ is that $U\cap V=\left\{𝟎\right\}$, but $V\cap W=\left\{{\left[\begin{array}{ccc}0& a& 0\end{array}\right]}^T|a\in ℝ.\right\}\ne \left\{𝟎\right\}$, and in general if the zero vector is the only common element of two vector spaces then the sum of the vector spaces becomes a direct sum.In practice, the most important procedure to construct direct sums or check when an intersection of two vector subspaces reduces to the zero vector is through an inner product.

Definition. Two vector subspaces $U,V$ of the real vector space ${ℝ}^m$ are orthogonal, denoted as $U\perp V$ if ${𝒖}^T𝒗=0$ for any $𝒖\in U,𝒗\in V$.

Definition. Two vector subspaces $$U,V of $U+V$ are orthogonal complements, denoted $U=V^{\perp }$, $V=U^{\perp }$ if they are orthogonal subspaces, $U\perp V$, and $U\cap V=\left\{𝟎\right\}$, i.e., the null vector is the only common element of both subspaces.

octave] 

disp([u'*v vp'*w])

octave] 

The above concept of orthogonality can be extended to other vector subspaces, such as spaces of functions. It can also be extended to other choices of an inner product, in which case the term conjugate vector spaces is sometimes used.

The concepts of sum and direct sum of vector spaces used linear combinations of the form $𝒖+𝒗$. This notion can be extended to arbitrary linear combinations.

Definition. In vector space $𝒱=(V,S,+,\cdot )$, the span of vectors ${𝒂}_1,{𝒂}_2,\dots ,{𝒂}_n\in V,$is the set of vectors reachable by linear combination

Note that for real vector spaces a member of the span of the vectors $\{{𝒂}_1,{𝒂}_2,\dots ,{𝒂}_n\}$ is the vector $𝒃$ obtained from the matrix vector multiplication

From the above, the span is a subset of the co-domain of the linear mapping $𝒇\left(𝒙\right)=𝑨𝒙$.

2.Vector subspaces of a linear mapping

The wide-ranging utility of linear algebra essentially results a complete characterization of the behavior of a linear mapping between vector spaces $𝒇:U\to V$, $𝒇(a𝒖+b𝒗)=a𝒇\left(𝒖\right)+b𝒇\left(𝒗\right)$. For some given linear mapping the questions that arise are:

1. Can any vector within $V$ be obtained by evaluation of $𝒇$?

2. Is there a single way that a vector within $V$ can be obtained by evaluation of $𝒇$?

Linear mappings between real vector spaces $𝒇:{ℝ}^n\to {ℝ}^m$, have been seen to be completely specified by a matrix $𝑨\in {ℝ}^{m\times n}$. It is common to frame the above questions about the behavior of the linear mapping $𝒇\left(𝒙\right)=𝑨𝒙$ through sets associated with the matrix $𝑨$. To frame an answer to the first question, a set of reachable vectors is first defined.

Definition. The column space (or range) of matrix $𝑨\in {ℝ}^{m\times n}$ is the set of vectors reachable by linear combination of the matrix column vectors

By definition, the column space is included in the co-domain of the function $𝒇\left(𝒙\right)=𝑨𝒙$, $C\left(𝑨\right)\subseteq {ℝ}^m$, and is readily seen to be a vector subspace of ${ℝ}^m$. The question that arises is whether the column space is the entire co-domain $C\left(𝑨\right)={ℝ}^m$ that would signify that any vector can be reached by linear combination. If this is not the case then the column space would be a proper subset, $C\left(𝑨\right)\subset {ℝ}^m$, and the question is to determine what part of the co-domain cannot be reached by linear combination of columns of $𝑨$. Consider the orthogonal complement of $C\left(𝑨\right)$ defined as the set vectors orthogonal to all of the column vectors of $𝑨$, expressed through inner products as

This can be expressed more concisely through the transpose operation

and leads to the definition of a set of vectors for which ${𝑨}^T𝒚=𝟎$

Definition. The left null space (or cokernel) of a matrix $𝑨\in {ℝ}^{m\times n}$ is the set

Note that the left null space is also a vector subspace of the co-domain of $𝒇\left(𝒙\right)=𝑨𝒙$, $N\left({𝑨}^T\right)\subseteq {ℝ}^m$. The above definitions suggest that both the matrix and its transpose play a role in characterizing the behavior of the linear mapping $𝒇=𝑨𝒙$, so analagous sets are define for the transpose ${𝑨}^T$.

Definition. The row space (or corange) of a matrix $𝑨\in {ℝ}^{m\times n}$ is the set

Definition. The null space of a matrix $𝑨\in {ℝ}^{m\times n}$ is the set

Examples. Consider a linear mapping between real spaces $𝒇:{ℝ}^n\to {ℝ}^m$, defined by $𝒚=𝒇\left(𝒙\right)=𝑨𝒙={\left[\begin{array}{ccc}{y}_1& \dots & y_n\end{array}\right]}^T$, with $𝑨\in {ℝ}^{m\times n}$.

1. For $n=1$, $m=3$,

   ${\displaystyle 𝑨=\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right],{𝑨}^T=\left[\begin{array}{ccc}1& 0& 0\end{array}\right],}$

   the column space $C\left(𝑨\right)$ is the $y_1$-axis, and the left null space $N\left({𝑨}^T\right)$ is the $y_2{y}_3$-plane. Vectors that span these spaces are returned by the Octave orth and null functions.

   octave]

   A=[1; 0; 0]; disp(orth(A)); disp('-----'); disp(null(A'))

   -1

   -0

   -0

   ––-

   0 0

   1 0

   0 1

   octave]

2. For $n=2$, $m=3$,

   ${\displaystyle 𝑨=\left[\begin{array}{cc}1& -1\\ 0& 0\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}{𝒂}_1& {𝒂}_2\end{array}\right],{𝑨}^T=\left[\begin{array}{ccc}1& 0& 0\\ -1& 0& 0\end{array}\right],}$

   the columns of $𝑨$ are colinear, ${𝒂}_2=-{𝒂}_1$, and the column space $C\left(𝑨\right)$ is the $y_1$-axis, and the left null space $N\left({𝑨}^T\right)$ is the $y_2{y}_3$-plane, as before.

   octave]

   A=[1 -1; 0 0; 0 0]; disp(orth(A)); disp('-----'); disp(null(A'))

   -1.00000

   -0.00000

   -0.00000

   ––-

   0 0

   1 0

   0 1

   octave]

3. For $n=2$, $m=3$,

   ${\displaystyle 𝑨=\left[\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\end{array}\right],{𝑨}^T=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\end{array}\right],}$

   the column space $C\left(𝑨\right)$ is the $y_1{y}_2$-plane, and the left null space $N\left({𝑨}^T\right)$ is the $y_3$-axis.

   octave]

   A=[1 0; 0 1; 0 0]; disp(orth(A)); disp('-----'); disp(null(A'))

   -1 -0

   -0 -1

   -0 -0

   ––-

   0

   0

   1

   octave]

4. For $n=2$, $m=3$,

   ${\displaystyle 𝑨=\left[\begin{array}{cc}1& 1\\ 1& -1\\ 0& 0\end{array}\right],{𝑨}^T=\left[\begin{array}{ccc}1& 1& 0\\ 1& -1& 0\end{array}\right],}$

   the same $C\left(𝑨\right)$, $N\left({𝑨}^T\right)$ are obtained, albeit with a different set of spanning vectors returned by orth.

   octave]

   A=[1 1; 1 -1; 0 0]; disp(orth(A)); disp('-----'); disp(null(A'))

   0.70711 0.70711

   0.70711 -0.70711

   -0.00000 -0.00000

   ––-

   0

   0

   1

   octave]

5. For $n=3$, $m=3$,

   ${\displaystyle 𝑨=\left[\begin{array}{ccc}1& 1& 3\\ 1& -1& -1\\ 1& 1& 3\end{array}\right]=\left[\begin{array}{ccc}{𝒂}_1& {𝒂}_2& {𝒂}_3\end{array}\right],}$ ${\displaystyle {𝑨}^T=\left[\begin{array}{ccc}1& 1& 1\\ 1& -1& 1\\ 3& -1& 3\end{array}\right]=\left[\begin{array}{c}{𝒂}_1^T\\ {𝒂}_2^T\\ {𝒂}_3^T\end{array}\right],{𝑨}^T𝒚=\left[\begin{array}{c}{𝒂}_1^T𝒚\\ {𝒂}_2^T𝒚\\ {𝒂}_3^T𝒚\end{array}\right]}$

   since ${𝒂}_3={𝒂}_1+2{𝒂}_2$, the orthogonality condition ${𝑨}^T𝒚=𝟎$ is satisfied by vectors of form $𝒚=\left[\begin{array}{ccc}a& 0& -a\end{array}\right]$, $a\in ℝ$.

   octave]

   A=[1 1 3; 1 -1 -1; 1 1 3]; disp(orth(A)); disp('-----'); disp(null(A'))

   0.69157 0.14741

   -0.20847 0.97803

   0.69157 0.14741

   ––-

   0.70711

   0.00000

   -0.70711

   octave]

The above low dimensional examples are useful to gain initial insight into the significance of the spaces $C\left(𝑨\right),N\left({𝑨}^T\right)$. Further appreciation can be gained by applying the same concepts to processing of images. A gray-scale image of size $p_x$ by $p_y$ pixels can be represented as a vector with $m=p_x{p}_y$ components, $𝒃\in {[0,1]}^m\subset {ℝ}^m$. Even for a small image with $p_x=p_y=128=2^7$ pixels along each direction, the vector $𝒃$ would have $m=2^{14}$ components. An image can be specified as a linear combination of the columns of the identity matrix

with $b_i$ the gray-level intensity in pixel $i$. Similar to the inclined plane example from §1, an alternative description as a linear combination of another set of vectors ${𝒂}_1,\dots ,{𝒂}_m$ might be more relevant. One choice of greater utility for image processing mimics the behavior of the set $\{1,\cos t,\cos 2t,\dots ,\sin t,\sin 2t,\dots \}$ that extends the second example in §1, would be for $m=4$