Vector Spaces, Subspaces and Bases

Introduction and Context

Linear algebra provides the language for representing data, transformations, and constraints in artificial intelligence and machine learning. Images can be represented as vectors of pixel intensities, documents as vectors of word or embedding coordinates, and model parameters as vectors in high-dimensional spaces. To reason correctly about these objects, it is not enough to manipulate arrays mechanically. We must understand the structures in which vectors live, the relationships among vectors, and the dimensions of the information they contain.

This chapter develops the central ideas of span, linear independence, basis, dimension, coordinates, the four fundamental subspaces of a matrix, orthogonal complements, and the rank–nullity theorem. These concepts explain when a collection of features is redundant, how a lower-dimensional representation can be constructed, and why linear systems may have unique, multiple, or no solutions.

Learning Objectives

By the end of this chapter, you should be able to:

1. Define a vector space and identify common examples.

2. Determine the span and test linear independence of vectors.

3. Construct and interpret a basis and calculate dimension.

4. Express vectors using coordinates relative to a basis.

5. Identify the row space, column space, and null space of a matrix.

6. Explain orthogonal complements and compute them in common settings.

7. Apply the rank–nullity theorem to matrices and linear transformations.

8. Relate these ideas to dimensionality reduction, feature design, and machine learning models.

1. Vector Spaces and Linear Combinations

A vector space over the real numbers is a set V equipped with vector addition and scalar multiplication that satisfy the usual algebraic rules, including closure, associativity, commutativity of addition, existence of a zero vector, additive inverses, and compatibility of scalar multiplication. In this chapter, the scalars are generally real numbers.

The most familiar example is R^n, the set of all ordered n-tuples of real numbers. For x, y in R^n and scalar c, addition and scalar multiplication are defined componentwise:

x + y = (x_1 + y_1, ..., x_n + y_n),

cx = (cx_1, ..., cx_n).

Other examples include the set of polynomials of degree at most d, the set of m by n real matrices, and spaces of functions. Thus, a vector need not be a geometric arrow; it may be a polynomial, an image, or a parameter vector.

A linear combination of vectors v_1, ..., v_k is an expression

c_1v_1 + c_2v_2 + ... + c_kv_k,

where c_1, ..., c_k are scalars. The coefficients are called weights or combination coefficients. Linear combinations are fundamental because a model can often represent a new observation, feature, or prediction as a weighted combination of existing vectors.

Span

The span of a set of vectors is the set of every linear combination of those vectors:

span{v_1, ..., v_k} = {c_1v_1 + ... + c_kv_k : c_i in R}.

The span is always a subspace. It contains the zero vector, is closed under addition, and is closed under scalar multiplication.

For example, let

v_1 = (1, 0, 1), v_2 = (0, 1, 1).

Then

span{v_1, v_2} = {(a, b, a+b) : a,b in R}.

This is a plane through the origin in R^3. The vector (2, 3, 5) belongs to this span because it equals 2v_1 + 3v_2. The vector (2, 3, 6) does not belong to it, since its third coordinate is not the sum of its first two coordinates.

A set of vectors spans V if every vector in V can be written as a linear combination of the set. Span describes what can be generated; it does not by itself indicate whether the generating vectors contain redundancy.

2. Linear Independence and Dependence

Vectors v_1, ..., v_k are linearly independent if the equation

c_1v_1 + ... + c_kv_k = 0

has only the trivial solution c_1 = ... = c_k = 0. If a nontrivial solution exists, the vectors are linearly dependent.

Dependence means that at least one vector can be expressed as a linear combination of the others. For example,

v_1 = (1, 2), v_2 = (2, 4)

are dependent because v_2 = 2v_1. In contrast, (1, 0) and (0, 1) are independent.

A set containing the zero vector is automatically dependent. More generally, in R^n no set containing more than n vectors can be linearly independent. This fact is useful when assessing feature sets: a large number of features does not necessarily imply a large amount of independent information.

Testing Independence Using a Matrix

Place the vectors as columns of a matrix A. The vectors are linearly independent precisely when the homogeneous system Ax = 0 has only the zero solution. Row reduction can therefore be used to test independence.

Consider

A = [[1, 2, 1], [0, 1, 1], [1, 3, 2]].

The third row is the sum of the first two rows, and column 3 is column 2 minus column 1? More directly, solving Ax = 0 gives equations

x_1 + 2x_2 + x_3 = 0,

x_2 + x_3 = 0,

x_1 + 3x_2 + 2x_3 = 0.

The third equation is the sum of the first two. From the second equation x_2 = -x_3; substituting in the first gives x_1 = x_3. Letting x_3 = t produces

x = (t, -t, t) = t(1,-1,1).

Since nonzero solutions exist, the columns are linearly dependent.

3. Subspaces

A subset W of a vector space V is a subspace if:

1. The zero vector belongs to W.

2. If u and v belong to W, then u + v belongs to W.

3. If u belongs to W and c is a scalar, then cu belongs to W.

The set of all solutions to a homogeneous system Ax = 0 is a subspace. A line or plane through the origin is a subspace of R^3; a line or plane not passing through the origin is not a subspace because it does not contain the zero vector.

Every span is a subspace, but not every subset is a subspace. For example, the set {(x,y): x+y=1} is a line in R^2 but is not a subspace because (0,0) is not included.

Subspaces allow complex problems to be decomposed into meaningful components. In matrix analysis, the row space records possible linear measurements of input vectors, the column space records attainable outputs, and the null space records input directions that produce no output.

4. Basis and Dimension

A basis for a vector space V is a set of vectors that both spans V and is linearly independent. These two requirements are essential:

• Spanning ensures that every vector in V can be represented.
• Independence ensures that the representation is not redundant.

The standard basis for R^3 is

e_1=(1,0,0), e_2=(0,1,0), e_3=(0,0,1).

Every vector (x_1,x_2,x_3) has the representation x_1e_1+x_2e_2+x_3e_3.

The dimension of a finite-dimensional vector space is the number of vectors in any basis. Although a space can have many different bases, all bases have the same number of elements. Thus, dimension measures the number of independent degrees of freedom.

Finding a Basis from a Spanning Set

Suppose the columns of a matrix are

a_1=(1,0,1), a_2=(2,0,2), a_3=(0,1,1).

Since a_2=2a_1, it is redundant. The vectors a_1 and a_3 are independent, so {a_1,a_3} is a basis for the column span. The dimension of that span is 2.

Row reduction provides a systematic method. The pivot columns of the original matrix form a basis for its column space. It is important to select pivot columns from the original matrix, not from the reduced matrix, because row operations generally change the column space.

5. Coordinates Relative to a Basis

Let B = {b_1, ..., b_n} be a basis for V. Every vector v in V has a unique representation

v = c_1b_1 + ... + c_nb_n.

The coordinate vector of v relative to B is

[v]_B = [c_1, ..., c_n]^T.

Uniqueness follows from linear independence. If two different coordinate representations existed, subtracting them would produce a nontrivial linear combination of basis vectors equal to zero.

For example, let

B = {(1,1), (1,-1)}, and v=(5,1).

We seek c_1 and c_2 such that

c_1(1,1)+c_2(1,-1)=(5,1).

Thus c_1+c_2=5 and c_1-c_2=1. Adding equations gives 2c_1=6, so c_1=3 and c_2=2. Therefore,

[v]_B=(3,2)^T.

Coordinates depend on the chosen basis. The geometric or abstract vector does not change, but its numerical description does. This principle is central to feature representations and changes of coordinates in machine learning.

If B is the ordered basis and P_B is the matrix whose columns are b_1,...,b_n in standard coordinates, then

v = P_B[v]_B.

If P_B is square and invertible, then [v]_B=P_B^{-1}v.

6. Fundamental Matrix Subspaces

Let A be an m by n matrix, viewed as a linear transformation from R^n to R^m:

T(x)=Ax.

Four subspaces are especially important.

6.1 Column Space

The column space of A, denoted Col(A), is the span of the columns of A. It is a subspace of R^m and equals the range or image of the transformation. It contains exactly the vectors b for which Ax=b has at least one solution.

The dimension of Col(A) is called the rank of A. A basis can be obtained from the pivot columns of A's row-reduced form, selected in the original matrix.

6.2 Row Space

The row space of A, denoted Row(A), is the span of the rows of A. It is a subspace of R^n. The nonzero rows of a row-echelon form provide a basis for the row space because elementary row operations preserve row spaces.

The row space describes the independent linear measurements that A applies to an input vector. The row space and column space have the same dimension, namely rank(A).

6.3 Null Space

The null space or kernel of A is

Null(A)={x in R^n: Ax=0}.

It is a subspace of R^n. Its vectors represent input directions that are completely eliminated by A. The dimension of the null space is called the nullity of A.

For example, let

A = [[1,2,3],[2,4,6]].

The equation Ax=0 reduces to x_1+2x_2+3x_3=0. Let x_2=s and x_3=t. Then x_1=-2s-3t, so

x=s(-2,1,0)+t(-3,0,1).

A basis for Null(A) is {(-2,1,0),(-3,0,1)}, and the nullity is 2.

6.4 Left Null Space

The left null space is

Null(A^T)={y in R^m: A^Ty=0}.

It is a subspace of R^m and consists of vectors orthogonal to every column of A. It is important in understanding consistency conditions and least-squares residuals.

7. Orthogonality and Orthogonal Complements

Using the standard dot product, two vectors u and v in R^n are orthogonal if

u^Tv=0.

For a subspace W of R^n, its orthogonal complement is

W^perp={x in R^n: x^Tw=0 for every w in W}.

The orthogonal complement is itself a subspace. If W has dimension r in R^n, then

dim(W)+dim(W^perp)=n.

For a matrix A with n columns and m rows, two fundamental relationships are

Row(A)^perp = Null(A),

Col(A)^perp = Null(A^T).

To verify the first relationship, x belongs to Null(A) exactly when every row r_i of A satisfies r_i x=0. Thus x is orthogonal to every row and therefore to the row space.

Orthogonal complements support projection, least squares, and residual analysis. In least-squares regression, the residual is orthogonal to the column space of the design matrix. This means the unexplained component cannot be reduced further by any linear combination of the model's predictors.

8. Rank–Nullity Theorem

For a linear transformation T:R^n to R^m represented by an m by n matrix A,

rank(A)+nullity(A)=n.

Equivalently,

dim(Col(A))+dim(Null(A))=number of columns of A.

The theorem states that each input degree of freedom either contributes to the effective output variation or belongs to a direction that is lost in the transformation.

For the matrix

A=[[1,2,3],[2,4,6]],

there is one pivot, so rank(A)=1. Since A has three columns, nullity(A)=3-1=2, agreeing with the explicit null-space calculation.

Rank–nullity does not state that rank plus the number of rows equals the number of columns. The correct relation uses nullity, not the total number of rows. Also, rank cannot exceed either the number of rows or the number of columns.

9. A Detailed Applied Case: Redundant Features in an AI Classifier

Background

Consider an illustrative binary classification system that uses three standardized numerical features for each customer: x_1, monthly activity; x_2, number of weekly sessions; and x_3, a feature engineered as twice monthly activity plus weekly sessions. The feature vector is x=(x_1,x_2,x_3)^T.

Problem

Because x_3=2x_1+x_2 for every observation, the three features cannot provide three independent directions of information. A linear classifier may still assign three coefficients, but the resulting score

w_1x_1+w_2x_2+w_3x_3

can be rewritten as

(w_1+2w_3)x_1+(w_2+w_3)x_2.

Thus different coefficient vectors can produce exactly the same predictions.

Analysis

The feature-generation relationship can be represented by the matrix

A = [[1,0,2],[0,1,1]],

which maps (x_1,x_2) to (x_1,x_2,2x_1+x_2) after adopting the appropriate input-output orientation. Its output features lie in a two-dimensional subspace of R^3. The feature covariance matrix is therefore singular in the ideal exact-relation case, and parameter estimates are not uniquely identified without additional constraints or regularization.

Approach and Solution

A data scientist can remove x_3, retain x_1 and x_2, or replace the original features with a basis for their span. If the relationship is only approximate, singular-value decomposition or principal component analysis can identify directions with very small variance. Regularization can stabilize estimation, but it does not create new independent information.

Outcome

Removing exact redundancy reduces storage and computation, improves interpretability, and avoids non-identifiability. The predictive information is unchanged because x_3 was already determined by the other features.

Learning Points

First, the number of recorded variables may exceed the dimension of the feature space. Second, basis selection is a principled way to remove redundancy. Third, rank deficiency affects optimization and parameter interpretation. Finally, dimensionality reduction must be validated against predictive performance and fairness: removing a feature can affect subgroups differently if the feature encodes socially relevant information.

10. Practical Computation and Best Practices

When analyzing a matrix, first record its dimensions and specify whether vectors are rows or columns. Then use row reduction to determine pivots, rank, and solutions to homogeneous systems. Preserve the original matrix when extracting a column-space basis. Use nonzero reduced rows for a row-space basis. Parameterize free variables clearly when finding a null-space basis.

For numerical data, exact dependence may be obscured by rounding. In floating-point computation, rank depends on a tolerance, often related to singular values. A very small singular value may indicate near dependence rather than exact dependence. Therefore, numerical rank should be interpreted in relation to measurement precision, scaling, and the application.

In machine learning, feature scaling is important because norms, dot products, and numerical conditioning depend on units. Orthogonality in the ordinary dot product is not automatically meaningful when features have incompatible scales. Standardization, domain-specific metrics, or a carefully chosen inner product may be required.

11. Challenges, Limitations, and Contemporary Relevance

The geometric intuition developed in two and three dimensions remains valuable, but AI commonly operates in thousands or millions of dimensions. High-dimensional spaces exhibit phenomena such as concentration of distances and computational costs that make explicit basis construction impractical. Algorithms therefore use QR factorization, singular-value decomposition, randomized projections, and iterative methods.

A basis is not automatically the best representation for a task. A mathematically valid basis may be difficult to interpret, numerically unstable, or unsuitable for downstream prediction. Orthogonal bases are often computationally attractive, while sparse bases may be more interpretable. These goals can conflict.

Ethically, dimensionality reduction and feature deletion should not be treated as purely technical operations. A removed feature may be a proxy for protected characteristics, and a low-variance direction may still matter for a minority population. Governance requires documenting transformations, testing subgroup performance, and preserving reproducibility. Linear algebra identifies structure; responsible deployment requires social and institutional judgment as well.

Chapter Summary

A vector space is a setting in which vectors can be added and multiplied by scalars while satisfying consistent algebraic rules. Linear combinations generate spans, and a basis is an independent spanning set. Dimension counts the number of independent degrees of freedom, while coordinates describe vectors relative to a selected basis.

For a matrix A, the column space contains attainable outputs, the row space contains independent linear measurements, the null space contains input directions mapped to zero, and the left null space is the orthogonal complement of the column space. Orthogonal complements formalize perpendicular directions and underpin projection and least-squares methods. The rank–nullity theorem states that rank plus nullity equals the number of columns, providing a central accounting identity for information preserved and lost by a linear transformation.

These concepts are directly relevant to AI and ML. They explain redundant features, non-unique parameterizations, dimensionality reduction, singular covariance matrices, and the geometry of regression. Good practice requires attention to numerical precision, scaling, interpretability, subgroup effects, and reproducibility.

Key Terms

Vector space: A set closed under vector addition and scalar multiplication and satisfying the vector-space axioms.

Linear combination: A weighted sum of vectors.

Span: The set of all linear combinations of a given collection of vectors.

Subspace: A subset that contains zero and is closed under addition and scalar multiplication.

Linear independence: A property in which only the trivial linear combination equals zero.

Linear dependence: A condition in which a nontrivial linear combination equals zero.

Basis: A linearly independent spanning set.

Dimension: The number of vectors in a basis.

Coordinate vector: The coefficients representing a vector relative to an ordered basis.

Column space: The span of a matrix's columns.

Row space: The span of a matrix's rows.

Null space: The set of vectors x satisfying Ax=0.

Left null space: The set of vectors y satisfying A^Ty=0.

Rank: The dimension of the column space, equivalently the row space.

Nullity: The dimension of the null space.

Orthogonal complement: The set of vectors perpendicular to every vector in a subspace.

Pivot: A leading nonzero entry identifying an independent direction in row reduction.

Rank–nullity theorem: The identity rank(A)+nullity(A)=number of columns of A.

Numerical rank: An effective rank determined using a tolerance in floating-point computation.

Review Questions

Short Answer Questions

1. What is the difference between the span of vectors and their linear independence?

2. State the conditions that make a subset a subspace.

3. Why do the pivot columns of the original matrix form a basis for the column space?

4. Define the null space of a matrix.

5. State the rank–nullity theorem.

Long Answer Questions

1. Explain why a basis must both span a vector space and be linearly independent. Illustrate with an example in R^3.

2. Describe the four fundamental subspaces of a matrix and state the ambient space in which each is located.

3. Explain how coordinates change when the basis changes, including the role of the basis matrix.

4. Derive the relationship Row(A)^perp=Null(A) and explain its significance.

5. Discuss how rank deficiency affects a machine-learning model with redundant features.

Analytical / Application Questions

1. For A=[[1,2,1],[0,1,1],[1,3,2]], find the rank, determine whether its columns are independent, and give a basis for its null space.

2. A data matrix has 12 columns and rank 8. Determine its nullity and interpret the result in terms of feature redundancy.

3. Explain how you would decide whether a very small singular value represents meaningful low-dimensional structure or merely numerical noise in an AI dataset.

Multiple Choice Questions with Answers

Question 1

Which condition defines linear independence of vectors v1,...,vk?

A. Every vector has at least two representations

B. Only the trivial coefficients solve c1v1+...+ckvk=0

C. The vectors all have unit length

D. The vectors span a space of dimension zero

Correct Answer: B. Only the trivial coefficients solve c1v1+...+ckvk=0

Question 2

What is the dimension of the span of (1,0,1) and (0,1,1)?

A. 0

B. 1

C. 2

D. 3

Correct Answer: C. 2

Question 3

For a matrix A, which set is the null space?

A. All y such that A^T y=0

B. The span of the rows of A

C. The span of the columns of A

D. All x such that Ax=0

Correct Answer: D. All x such that Ax=0

Question 4

Which rows form a basis for the row space after row reduction?

A. All original rows only

B. The nonzero rows of an echelon form

C. The pivot columns of the original matrix

D. The zero rows only

Correct Answer: B. The nonzero rows of an echelon form

Question 5

A matrix has 7 columns and rank 4. What is its nullity?

A. 3

B. 4

C. 7

D. 11

Correct Answer: A. 3

Question 6

If W is a subspace of R^n with dimension r, what is dim(W^perp)?

A. n+r

B. r-n

C. n-r

D. r

Correct Answer: C. n-r

Question 7

Which relationship is correct for a matrix A?

A. Row(A)^perp=Null(A)

B. Row(A)^perp=Col(A)

C. Null(A)^perp=Null(A^T)

D. Col(A)^perp=Row(A)

Correct Answer: A. Row(A)^perp=Null(A)

Question 8

Why must pivot columns for a column-space basis be taken from the original matrix?

A. Row operations preserve columns exactly

B. Row operations can change the column space

C. Reduced matrices have no pivots

D. Original matrices always have independent columns

Correct Answer: B. Row operations can change the column space

Question 9

For B={(1,1),(1,-1)}, what are the coordinates of (5,1) relative to B?

A. (2,3)

B. (3,2)

C. (5,1)

D. (1,5)

Correct Answer: B. (3,2)

Question 10

What does rank measure for a matrix viewed as a linear transformation?

A. The number of all entries

B. The dimension of the attainable output space

C. The number of zero rows

D. The number of free variables only

Correct Answer: B. The dimension of the attainable output space