2.6 Basis and Rank

2.6.1 Generating Set and Basis

Definition 2.26 Let \(V = (V, +, \cdot)\) be a vector space and \(A = \{ \mathbf{x}_1, \ldots, \mathbf{x}_k \} \subseteq V\). If every vector \(\mathbf{v} \in \mathbf{V}\) can be written as a linear combination of \(\mathbf{x}_1, \ldots, \mathbf{x}_k\), then \(A\) is called a generating set of \(\mathbf{V}\).

The set of all such linear combinations is called the span of \(A\), denoted by: \[ V = \text{span}[A] = \text{span}[\mathbf{x}_1, \ldots, \mathbf{x}_k]. \]

A generating set spans the entire vector space, meaning every vector can be expressed as a combination of those in the set.

Definition 2.27 A generating set \(A \subseteq V\) is minimal if no smaller subset \(\tilde{A} \subset A\) spans \(V\). Every linearly independent generating set of \(V\) is minimal and is called a basis of \(V\).

Equivalently:

  • A basis is a minimal generating set.
  • A basis is also a maximal linearly independent set (adding any new vector makes it dependent).

Theorem 2.3 For a basis \(B = \{\mathbf{b}_1, \ldots, \mathbf{b}_k\}\), every vector \(\mathbf{x} \in V\) can be expressed uniquely as: \[ \mathbf{x} = \sum_{i=1}^{k} \lambda_i \mathbf{b}_i = \sum_{i=1}^{k} \psi_i \mathbf{b}_i, \] where \(\lambda_i = \psi_i\) for all \(i = 1, \ldots, k\).

Example 2.49 The standard basis is: \[ B= \left\{ \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \right\}. \]

Other valid bases include: \[ B_1 = \left\{ \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \right\}, \quad B_2 = \left\{ \begin{bmatrix} 0.5 \\ 0.8 \\ 0.4 \end{bmatrix}, \begin{bmatrix} 1.8 \\ 0.3 \\ 0.3 \end{bmatrix}, \begin{bmatrix} -2.2 \\ -1.3 \\ 3.5 \end{bmatrix} \right\}. \]

Every vector space \(V\) has a basis, but there are usually many possible bases. All bases of \(V\) contain the same number of vectors, called basis vectors. The dimension of \(V\), written \(\text{dim}(V)\), is the number of basis vectors. If \(U \subseteq V\) is a subspace, then: \[ \text{dim}(U) \leq \text{dim}(V), \] with equality if and only if \(U = V\).

To find a basis for a subspace \(U = \text{span}[\mathbf{x}_1, \ldots, \mathbf{x}_m] \subseteq \mathbb{R}^n\):

  1. Form a matrix \(\mathbf{A}\) with the spanning vectors as columns.
  2. Compute the row echelon form of \(\mathbf{A}\).
  3. The columns corresponding to pivot positions form a basis for \(U\).

Example 2.50 Let \(U \subseteq \mathbb{R}^5\) be spanned by the vectors: \[ \mathbf{x}_1 = \begin{bmatrix} 1 \\ 2 \\ -1 \\ -1 \\ -1 \end{bmatrix}, \quad \mathbf{x}_2 = \begin{bmatrix} 2 \\ -1 \\ 1 \\ 2 \\ -2 \end{bmatrix}, \quad \mathbf{x}_3 = \begin{bmatrix} 3 \\ -4 \\ 3 \\ 5 \\ -3 \end{bmatrix}, \quad \mathbf{x}_4 = \begin{bmatrix} -1 \\ 8 \\ -5 \\ -6 \\ 1 \end{bmatrix}. \]

After performing Gaussian elimination on the matrix \([\mathbf{x}_1 \ \mathbf{x}_2 \ \mathbf{x}_3 \ \mathbf{x}_4]\), the pivot columns correspond to \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_4\), which are linearly independent. Hence, \(\{\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_4\}\) is a basis of \(U\) and \(\text{dim}(U) = 3\). Note also that the standard basis for \(\mathbb{R}^5\) has 5 vectors (each one with 0’s in each entry other than the \(n^{th}\) spot). So, \(\text{dim}(U) < \text{dim}(V)\).

2.6.2 Rank

Definition 2.28 The rank of a matrix \(\mathbf{A} \in \mathbb{R}^{m \times n}\), denoted \(\text{rk}(\mathbf{A})\), is the number of linearly independent columns (or rows) of \(\mathbf{A}\).

Definition 2.29 Let \(\mathbf{A} \in \mathbb{R}^{m \times n}\) be a matrix. The column space of \(\mathbf{A}\), denoted as \(\text{Col}(\mathbf{A})\), is the subspace of \(\mathbb{R}^m\) spanned by the columns of \(\mathbf{A}\).

In other words, \[ \text{Col}(\mathbf{A}) = \text{span} \{ \mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n \}, \] where \(\mathbf{a}_i\) is the \(i^\text{th}\) column of \(\mathbf{A}\). The column space represents all possible vectors \(\mathbf{b}\) for which the linear system \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has a solution.

Definition 2.30 The row space of \(\mathbf{A}\), denoted as \(\text{Row}(\mathbf{A})\), is the subspace of \(\mathbb{R}^n\) spanned by the rows of \(\mathbf{A}\).

Equivalently, \[ \text{Row}(\mathbf{A}) = \text{span} \{ \mathbf{r}_1, \mathbf{r}_2, \ldots, \mathbf{r}_m \}, \] where \(\mathbf{r}_i\) is the \(i^\text{th}\) row of \(\mathbf{A}\). The row space contains all possible linear combinations of the rows of \(\mathbf{A}\).

Lemma 2.7 Properties of the rank: Let \(\mathbf{A} \in \mathbb{R}^{m \times n}\) matrix and \(\mathbf{x}\) and \(\mathbf{b}\) vectors of length \(n\).

  • \(\text{rk}(\mathbf{A}) = \text{rk}(\mathbf{A}^\top)\): column rank equals row rank.
  • The column space of \(\mathbf{A}\) has dimension \(\text{rk}(\mathbf{A})\).
  • The row space of \(\mathbf{A}\) also has dimension \(\text{rk}(\mathbf{A})\).
  • \(\mathbf{A}\) is invertible iff \(\text{rk}(\mathbf{A}) = n\) (for \(\mathbf{A} \in \mathbb{R}^{n \times n}\)).
  • The system \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has a solution iff \(\text{rk}(\mathbf{A}) = \text{rk}([\mathbf{A}|\mathbf{b}])\).
  • The null space of \(\mathbf{A}\) (solutions of \(\mathbf{A}\mathbf{x} = 0\)) has dimension \(n - \text{rk}(\mathbf{A})\).
  • A matrix has full rank if \(\text{rk}(\mathbf{A}) = \min(m, n)\).
  • If \(\text{rk}(\mathbf{A}) < \min(m, n)\), it is rank deficient.

Example 2.51 \[ \mathbf{A} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix} \Rightarrow \text{rk}(\mathbf{A}) = 2. \]

\[ \mathbf{A} = \begin{bmatrix} 1 & 2 & 1 \\ -2 & -3 & 1 \\ 3 & 5 & 0 \end{bmatrix} \Rightarrow \begin{bmatrix} 1 & 2 & 1 \\ 0 & 1 & 3 \\ 0 & 0 & 0 \end{bmatrix} \Rightarrow \text{rk}(\mathbf{A}) = 2. \]

Exercises

Exercise 2.64 Prove that \(\text{rk}(\mathbf{A}) = \text{rk}(\mathbf{A}^\top)\): column rank equals row rank.

Exercise 2.65 Prove that the column space of \(\mathbf{A}\) has dimension \(\text{rk}(\mathbf{A})\). Prove that the row space of \(\mathbf{A}\) also has dimension \(\text{rk}(\mathbf{A})\).

Exercise 2.66 Prove that \(\mathbf{A}\) is invertible iff \(\text{rk}(\mathbf{A}) = n\) (for \(\mathbf{A} \in \mathbb{R}^{n \times n}\)).

Exercise 2.67 Prove that the system \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has a solution iff \(\text{rk}(\mathbf{A}) = \text{rk}([\mathbf{A}|\mathbf{b}])\).

Exercise 2.68 Prove that the null space of \(\mathbf{A}\) (solutions of \(\mathbf{A}\mathbf{x} = 0\)) has dimension \(n - \text{rk}(\mathbf{A})\).

Exercise 2.69 Let \(\mathbf{A}\) be a regular \(2 \times 2\) (invertible) matrix. Show that \(\mathbf{A}\) has rank 2.

Exercise 2.70 In \(\mathbb{R}^{2 \times 2}\), show that \(rk(\mathbf{A}) = 1\) if \(\det(\mathbf{A}) = 0\), but \(\mathbf{A}\) is not the zero matrix.

Exercise 2.71 Find the rank of \(\mathbf{A} = \begin{bmatrix}1&0&2&1\\ 0&2&4&2\\0&2&2&1 \end{bmatrix}\).

Exercise 2.72 Find the rank of \(\mathbf{A} = \begin{bmatrix}1&2&1&-1\\ 9&5&2&2\\ 7&1&0&4 \end{bmatrix}\).

Exercise 2.73 Let \(\mathbf{x}\) be a unit vector in \(\mathbb{R}^n\). Partition \(\mathbf{x}\) as \[\mathbf{x} = \begin{bmatrix}x_1 \\ x_2 \\ \vdots \\x_n \end{bmatrix} = \begin{bmatrix} x_1 \\ \mathbf{y} \end{bmatrix}.\] Let \[\mathbf{Q} = \begin{bmatrix}x_1 & \mathbf{y}^T\\ \mathbf{y} & \mathbf{I} - \left(\dfrac{1}{1 - x_1} \right) \mathbf{y} \mathbf{y}^T \end{bmatrix}.\] \(Q\) is orthogonal. (This procedure gives a quick method for finding an orthonormal basis for \(\mathbb{R}^n\) with a prescribed first vector \(\mathbf{x}\), a construction that is frequently useful in applications). Select any non-trivial vector in \(\mathbb{R}^3\) and verify that \(\mathbf{Q}\) is orthogonal.