Basis and Rank
Table of contents
Generating Set
Let $V = (\mathcal{V}, +, \cdot)$ be a vector space and set of vectors $\mathcal{A} \subseteq \mathcal{V}$.
If every $v \in \mathcal{V}$ can be expressed as a linear combination of $\mathbf{x}_i \in \mathcal{A}$, then $\mathcal{A}$ is a generating set of $V$.
Generating set does not have to be linearly independent.
Span
The span of $\mathcal{A}$ is the set of all linear combinations of $\mathcal{A}$.
When $\mathcal{A}$ is a generating set of $V$, we say that $\mathcal{A}$ spans $V$.
$$ V = \mathrm{span}[\mathcal{A}] $$
Minimal Generating Set
If there is no smaller subset of $\mathcal{V}$ that spans $V$, then $\mathcal{A}$ is a minimal generating set of $V$.
Basis
Every linearly independent generating set of $V$ is minimal. Such a set is called a basis of $V$.
- The difference from generating set is that basis is linearly independent.
- Every vector space has a basis, but it is not unique.
- The number of basis vectors, called the dimension of the vector space, is the same for all bases of a vector space.
- A basis is a minimal generating set and also a maximal linearly independent set of vectors in $\mathcal{V}$.
- Every linear combination of a basis is unique.
Dimension of Vector Space
For a finite-dimensional vector space $V$, the dimension of $V$ is the number of basis vectors of $V$.
Denoted:
$$ \dim(V) $$
- $U \subseteq V \implies \dim(U) \leq \dim(V)$
- $\dim(U) = \dim(V) \iff U = V$
Finding Basis from a Generating Set
If $\mathcal{A} = \{\mathbf{x}_1, \dots, \mathbf{x}_n\}$ is a generating set of $V$, then we can find a basis of $V$ by:
- Form a matrix $A = [\mathbf{x}_1\, \dots\, \mathbf{x}_n]$ whose columns are the spanning vectors in $\mathcal{A}$.
- Find the row echelon form of $A$.
- The spanning vectors corresponding to the pivot columns of the reduced row echelon form of $A$ form a basis of $V$.
Example: Standard Basis of $\mathbb{R}^3$
The canonical or standard basis of $\mathbb{R}^3$ is:
\[\mathcal{B} = \left\{ \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \right\}\]- It is true that we can generate any vector in $\mathbb{R}^3$ with $\mathcal{B}$.
- It is true that there is no smaller set that can span $\mathbb{R}^3$.
- It is true that $\mathcal{B}$ is linearly independent.
- It is true that there is no other vector we can add to the set without making it linearly dependent.
Example: Other Bases of $\mathbb{R}^3$
\[\mathcal{B}' = \left\{ \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \right\}\]Ordered Basis
While a basis is a set of vectors expressed $\mathcal{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$, an ordered basis is expressed with a tuple of specific order.
$$ B = (\mathbf{b}_1, \dots, \mathbf{b}_n) $$
Coordinate Vector
Why would we want to order the basis? It is useful when representing a coordinate system.
Let $V$ be a vector space with an ordered basis $B = (\mathbf{b}_1, \dots, \mathbf{b}_n)$.
Any vector $\mathbf{x} \in V$ can be expressed as a linear combination of $B$:
\[\mathbf{x} = \alpha_1 \mathbf{b}_1 + \dots + \alpha_n \mathbf{b}_n\]Then
\[\boldsymbol{\alpha} = \begin{bmatrix} \alpha_1 \\ \vdots \\ \alpha_n \end{bmatrix}\]is the coordinate vector of $\mathbf{x}$ with respect to $B$, and this vector is unique to $\mathbf{x}$.
A fixed ordering is important in having a consistent representation of coordinates.
Standard Basis
Standard basis is an example of an ordered basis.
When we talk about some vector $\mathbf{x} \in \mathbb{R}^n$, we often implicitly refer to the coordinate vector of $\mathbf{x}$ with respect to the standard basis.
With Respect to Other Ordered Bases
A coordinate vector can be expressed with respect to any ordered basis.
We denote the coordinate vector of $\mathbf{x}$ with respect to some $B$ as:
$$ [\mathbf{x}]_B $$
Example
If $B = ([1, 2]^\top, [3, 4]^\top)$ is an ordered basis of $\mathbb{R}^2$, then the coordinate vector of $\mathbf{x} = [1, 0]^\top$ with respect to $B$ is:
\[\mathbf{x} = -2 \cdot [1, 2]^\top + 1 \cdot [3, 4]^\top\] \[[\mathbf{x}]_B = \begin{bmatrix} -2 \\ 1 \end{bmatrix}\]- $[\mathbf{x} + \mathbf{y}]_B = [\mathbf{x}]_B + [\mathbf{y}]_B$
- $[c \mathbf{x}]_B = c [\mathbf{x}]_B$
Change of Basis Matrix
A change of basis matrix $P$ is a matrix that transforms the coordinate vector of $\mathbf{x}$ with respect to some $B$ ($[\mathbf{x}]_B$) to the coordinate vector of $\mathbf{x}$ with respect to some other basis $C$ ($[\mathbf{x}]_C$).
When $B = (\mathbf{b}_1, \dots, \mathbf{b}_n)$, the change of basis matrix is:
$$ P_{C \leftarrow B} = [\, [\mathbf{b}_1]_C\, \dots\, [\mathbf{b}_n]_C\,] $$
Every change of basis matrix is invertible.
If we have the coordinate vector of $\mathbf{x}$ with respect to $B$, we can find the coordinate vector of $\mathbf{x}$ with respect to $C$:
\[P [\mathbf{x}]_B = [\mathbf{x}]_C\]Example
Let $B = ([1, 2]^\top, [3, 4]^\top)$ and $C$ be the standard basis of $\mathbb{R}^2$.
We showed above that the coordinate vector of $\mathbf{x} = [1, 0]^\top$ with respect to $B$ is:
\[[\mathbf{x}]_B = \begin{bmatrix} -2 \\ 1 \end{bmatrix}\]The change of basis matrix is:
\[P_{C \leftarrow B} = \begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix}\]Then the coordinate vector of $\mathbf{x}$ with respect to $C$ is:
\[P_{C \leftarrow B} [\mathbf{x}]_B = \begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} -2 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} = [\mathbf{x}]_C\]When converting to a standard basis, the change of basis matrix has the basis vectors of old basis as columns.
Rank
The rank of a matrix $A \in \mathbb{R}^{m \times n}$ is the number of linearly independent columns of $A$.
Also called column rank.
It is denoted:
$$ \mathrm{rank}(A) \quad \mathrm{or} \quad \mathrm{rk}(A) $$
- Column rank is the same as row rank: $\mathrm{rank}(A) = \mathrm{rank}(A^T)$
The columns of $A$ span any subspace $U \subseteq \mathbb{R}^m$ where $\mathrm{rank}(A) = \dim(U)$
This column space is called image/range.
- The rows of $A$ (or columns of $A^T$) span any subspace $W \subseteq \mathbb{R}^n$ where $\mathrm{rank}(A) = \dim(W)$
- $\forall A \in \mathbb{R}^{m \times m}$, $A$ is invertible $\iff \mathrm{rank}(A) = m$
$\forall A \in \mathbb{R}^{m \times n}$ and $\mathbf{b} \in \mathbb{R}^m$, the system $A \mathbf{x} = \mathbf{b}$ has a solution $\iff \mathrm{rank}(A) = \mathrm{rank}(A \mid \mathbf{b})$
Where $A \mid \mathbf{b}$ is the augmented matrix.
For $A \in \mathbb{R}^{m \times n}$, the solution space of a homogeneous system ($A \mathbf{x} = \mathbf{0}$) is a vector subspace of $\mathbb{R}^n$ with dimension $n - \mathrm{rank}(A)$
This solution space is called kernel/nullspace.
Full Rank
A matrix $A \in \mathbb{R}^{m \times n}$ has full rank if $\mathrm{rank}(A) = \min(m, n)$.
Otherwise, it is rank deficient.