Fundamental Matrix Spaces

A central interest in scientific computation is to seek simple descriptions of complex objects. A typical situation is specifying an instance of some object of interest through 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 into 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 $𝒰<𝒱$.

∴ 

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

∴ 

y=[1; 2; 3]; yp=y[1:2]

∴ 

Vector subspaces arise in decomposition or partitioning of a vector space. The converse, composition of vector spaces $𝒰=(U,S,+,\cdot )$, $𝒱=(V,S,+,\cdot )$ is 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)

∴ 

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

∴ 

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.

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 results from 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 $𝒇:{ℝ}^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.

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.

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.

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.

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 ℝ$.

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$

4.Basis and dimension

Vector spaces are closed under linear combination, and the span of a vector set $ℬ=\{{𝒂}_1,{𝒂}_2,\dots \}$ defines a vector subspace. If the entire set of vectors can be obtained by a spanning set, $V=\mathrm{span}ℬ$, extending $ℬ$ by an additional element $𝒞=ℬ\cup \left\{𝒃\right\}$ would be redundant since $\mathrm{span}ℬ=\mathrm{span}𝒞$. This is recognized by the concept of a basis, and also allows leads to a characterization of the size of a vector space by the cardinality of a basis set.

Definition. A set of vectors ${𝒖}_1,\dots ,{𝒖}_n\in V$ is a basis for vector space $𝒱=(V,S,+,\cdot )$ if

Definition. The number of vectors ${𝒖}_1,\dots ,{𝒖}_n\in V$ within a basis is the dimension of the vector space $𝒱=(V,S,+,\cdot )$.

5.Dimension of matrix spaces

The domain and co-domain of the linear mapping $𝒇:U\to V$, $𝒇\left(𝒙\right)=𝑨𝒙$, are decomposed by the spaces associated with the matrix $𝑨$. When $U={ℝ}^n$, $V={ℝ}^m$, the following vector subspaces associated with the matrix $𝑨\in {ℝ}^{m\times n}$ have been defined:

• $C\left(𝑨\right)$ the column space of $𝑨$

• $C\left({𝑨}^T\right)$ the row space of $𝑨$

• $N\left(𝑨\right)$ the null space of $𝑨$

• $N\left({𝑨}^T\right)$ the left null space of $𝑨$, or null space of ${𝑨}^T$

Definition. The rank of a matrix $𝑨\in {ℝ}^{m\times n}$ is the dimension of its column space and is equal to the dimension of its row space.

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

Summary.

• Vector subspaces are subsets of a vector space closed under linear combination

• The simplest vector subspace is $\left\{𝟎\right\}$

• Linear mappings are represented by matrices

• Associated with matrix $𝑨\in {ℝ}^{m\times n}$ that represents mapping $f:{ℝ}^n\to {ℝ}^m$ are four fundamental subspaces:

  1. $C\left(𝑨\right)<{ℝ}^m$ the column space of $𝑨$ containing vectors $𝒃$reachable by $𝑨𝒙$, $𝒃=𝑨x$

  2. $N\left({𝑨}^T\right)<{ℝ}^m$ the left null space of $𝑨$ containing vectors $𝒚$ orthogonal to columns $𝑨$, ${𝑨}^T𝒚=0$

  3. $C\left({𝑨}^T\right)<{ℝ}^n$ the row space of $𝑨$

  4. $N\left(𝑨\right)<{ℝ}^n$ the null space of $𝑨$