Basis and Rank

Table of contents

1. Generating Set
   1. Span
   2. Minimal Generating Set
2. Basis
   1. Dimension of Vector Space
   2. Finding Basis from a Generating Set
   3. Example: Standard Basis of ${\mathbb{R}}^3$
   4. Example: Other Bases of ${\mathbb{R}}^3$
3. Ordered Basis
   1. Coordinate Vector
   2. Standard Basis
   3. With Respect to Other Ordered Bases
   4. Change of Basis Matrix
4. Rank
   1. Full Rank
   2. Rank-Nullity Theorem

---

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⟹\dim (U)\le \dim (V)$
• $\dim (U)=\dim (V)⟺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:

1. Form a matrix $A=[{\mathbf{x}}_1\dots {\mathbf{x}}_n]$ whose columns are the spanning vectors in $\mathcal{A}$.
2. Find the row echelon form of $A$.
3. 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{array}{c}1\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 1\end{array}\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}}^{\prime }=\{\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}1\\ 1\\ 1\end{array}\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+\cdots +{\alpha }_n{\mathbf{b}}_n$$

Then

$$\mathit{\alpha }=\left[\begin{array}{c}{\alpha }_1\\ ⋮\\ {\alpha }_n\end{array}\right]$$

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{]}^{\mathrm{\top }},[3,4{]}^{\mathrm{\top }})$ is an ordered basis of ${\mathbb{R}}^2$, then the coordinate vector of $\mathbf{x}=[1,0{]}^{\mathrm{\top }}$ with respect to $B$ is:

$$\mathbf{x}=-2\cdot [1,2{]}^{\mathrm{\top }}+1\cdot [3,4{]}^{\mathrm{\top }}$$ $$[\mathbf{x}{]}_B=\left[\begin{array}{c}-2\\ 1\end{array}\right]$$

• $[\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{]}^{\mathrm{\top }},[3,4{]}^{\mathrm{\top }})$ and $C$ be the standard basis of ${\mathbb{R}}^2$.

We showed above that the coordinate vector of $\mathbf{x}=[1,0{]}^{\mathrm{\top }}$ with respect to $B$ is:

$$[\mathbf{x}{]}_B=\left[\begin{array}{c}-2\\ 1\end{array}\right]$$

The change of basis matrix is:

$$P_{C\leftarrow B}=\left[\begin{array}{cc}1& 3\\ 2& 4\end{array}\right]$$

Then the coordinate vector of $\mathbf{x}$ with respect to $C$ is:

$$P_{C\leftarrow B}[\mathbf{x}{]}_B=\left[\begin{array}{cc}1& 3\\ 2& 4\end{array}\right]\left[\begin{array}{c}-2\\ 1\end{array}\right]=\left[\begin{array}{c}1\\ 0\end{array}\right]=[\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)\mathrm{or}\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)$
• $\mathrm{\forall }A\in {\mathbb{R}}^{m\times m}$, $A$ is invertible $⟺\mathrm{rank}(A)=m$

• $\mathrm{\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 $⟺\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.

Rank-Nullity Theorem

See here