Math for Machine Learning - Chapter 3: Linear Independence and Basis

This quiz rigorously tests your understanding of linear independence, span, basis, and dimension, crucial concepts in Linear Algebra for Machine Learning. It covers identifying redundant vectors, understanding coordinate systems, and implications for feature engineering and dimensionality reduction. Expect challenging questions that require a deep conceptual grasp and analytical skills.

Key Formulae and Concepts:

• Linear Combination: A vector $\mathbf{v}$ is a linear combination of vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k$ if there exist scalars $c_1, \ldots, c_k$ such that $\mathbf{v} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \ldots + c_k\mathbf{v}_k$.

• Linear Independence: A set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$ is linearly independent if the only solution to the vector equation $c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \ldots + c_k\mathbf{v}_k = \mathbf{0}$ is $c_1 = c_2 = \ldots = c_k = 0$. If non-zero scalars exist, the vectors are linearly dependent (redundant).

• Span: The span of a set of vectors $S = \{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$, denoted by $\text{span}(S)$, is the set of all possible linear combinations of the vectors in $S$.

• Basis: A set of vectors $\mathcal{B} = \{\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d\}$ is a basis for a vector space $V$ if:

  1. $\mathcal{B}$ is linearly independent.

  2. $\text{span}(\mathcal{B}) = V$.

• Dimension: The dimension of a vector space $V$, denoted $\text{dim}(V)$, is the number of vectors in any basis for $V$. All bases for a given finite-dimensional vector space have the same number of vectors.

• Coordinate Vector: If $\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}$ is a basis for $V$, then for any $\mathbf{x} \in V$, there exist unique scalars $c_1, \ldots, c_n$ such that $\mathbf{x} = c_1\mathbf{b}_1 + \ldots + c_n\mathbf{b}_n$. The coordinate vector of $\mathbf{x}$ relative to $\mathcal{B}$ is $[\mathbf{x}]_{\mathcal{B}} = \begin{bmatrix} c_1 \\ \vdots \\ c_n \end{bmatrix}$.

• Determinant and Linear Independence: For $n$ vectors in $\mathbb{R}^n$, they are linearly independent if and only if the determinant of the matrix formed by these vectors as columns (or rows) is non-zero.

• Rank-Nullity Theorem: For an $m \times n$ matrix $A$, $\text{rank}(A) + \text{nullity}(A) = n$, where $\text{rank}(A)$ is the dimension of the column space (or row space) and $\text{nullity}(A)$ is the dimension of the null space.

• Properties:

  • Any set of $k$ vectors in an $n$-dimensional space is linearly dependent if $k > n$.

  • Any set of $k$ vectors in an $n$-dimensional space cannot span the space if $k < n$.

  • A set of vectors containing the zero vector is always linearly dependent.