Basis and Dimension

Basis and Dimension

---

---

Vector Space Axioms

---

Subspace

---

Linear Combinations

---

Span

---

Linear Independence

---

Basis

---

Dimension

---

Change of Basis

import numpy as np

# Change of basis
B = np.array([[1, 1], [1, -1]])  # New basis vectors as columns
B_inv = np.linalg.inv(B)

# Vector in standard basis
x_standard = np.array([3, 1])

# Coordinates in basis B
x_in_B = B_inv @ x_standard
print(f"Coordinates in new basis: {x_in_B}")  # [2. 1.]

# Verify: reconstruct from new coordinates
x_reconstructed = B @ x_in_B
print(f"Reconstructed: {x_reconstructed}")  # [3. 1.]

---

Rank

---

Null Space

import numpy as np
from scipy.linalg import null_space

A = np.array([[1, 2, 0],
              [0, 0, 1],
              [0, 0, 0]])

ns = null_space(A)
print("Null space basis:")
print(ns)
# [[-0.89442719]
#  [ 0.4472136 ]
#  [ 0.        ]]

---

Column Space

---

Python Implementation

import numpy as np
from scipy.linalg import null_space, orth

def analyze_vector_space(A):
    """Comprehensive analysis of a matrix's vector space properties."""
    m, n = A.shape
    
    print(f"Matrix A ({m}x{n}):")
    print(A)
    print()
    
    # Rank
    rank = np.linalg.matrix_rank(A)
    print(f"Rank: {rank}")
    
    # Nullity
    nullity = n - rank
    print(f"Nullity: {nullity}")
    print(f"Rank + Nullity = {rank} + {nullity} = {rank + nullity} = n ✓")
    
    # Null space
    ns = null_space(A)
    print(f"\nNull space basis ({nullity} vectors):")
    print(ns) if ns.size > 0 else print("  {0}")
    
    # Column space
    cs = orth(A)
    print(f"\nColumn space basis ({rank} vectors):")
    print(cs)
    
    # Check if Ax = b has solutions
    b = np.array([1, 2, 3])
    try:
        x, residuals, rank_check, sv = np.linalg.lstsq(A, b, rcond=None)
        if np.allclose(A @ x, b):
            print(f"\nAx = b has solution: x = {x}")
        else:
            print(f"\nAx = b has no solution (b not in column space)")
    except:
        print(f"\nAx = b has no solution")
    
    return rank, nullity

# Example
A = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]])

rank, nullity = analyze_vector_space(A)

print("\n" + "="*50)

# Finding a basis for the column space
def column_space_basis(A):
    """Find a basis for the column space using row reduction."""
    # Row reduce and find pivot columns
    U = np.array(A, dtype=float)
    pivot_cols = []
    row, col = 0, 0
    
    while row < U.shape[0] and col < U.shape[1]:
        # Find pivot
        max_row = np.argmax(np.abs(U[row:, col])) + row
        if U[max_row, col] == 0:
            col += 1
            continue
        
        # Swap rows
        U[[row, max_row]] = U[[max_row, row]]
        pivot_cols.append(col)
        
        # Eliminate below
        for i in range(row + 1, U.shape[0]):
            if U[i, col] != 0:
                U[i] -= U[i, col] / U[row, col] * U[row]
        
        row += 1
        col += 1
    
    return A[:, pivot_cols], pivot_cols

basis, pivots = column_space_basis(A)
print(f"Pivot columns: {pivots}")
print(f"Column space basis:")
print(basis)

# Linear independence check
def check_linear_independence(vectors):
    """Check if a set of vectors is linearly independent."""
    if vectors.shape[1] == 0:
        return True
    rank = np.linalg.matrix_rank(vectors)
    return rank == vectors.shape[1]

# Examples
v1 = np.array([[1], [0], [0]])
v2 = np.array([[0], [1], [0]])
v3 = np.array([[1], [1], [0]])
v4 = np.array([[1], [1], [1]])

print("\n{[1,0,0], [0,1,0]}:", check_linear_independence(np.hstack([v1, v2])))
print("{[1,0,0], [0,1,0], [1,1,0]}:", check_linear_independence(np.hstack([v1, v2, v3])))
print("{[1,0,0], [0,1,0], [1,1,1]}:", check_linear_independence(np.hstack([v1, v2, v4])))

# Change of basis
def change_of_basis(x_standard, P):
    """Change coordinates from standard basis to basis P."""
    P_inv = np.linalg.inv(P)
    return P_inv @ x_standard

# Vector in standard basis
x = np.array([3, 1])

# New basis: rotated 45 degrees
theta = np.pi / 4
P = np.array([[np.cos(theta), -np.sin(theta)],
              [np.sin(theta),  np.cos(theta)]])

x_new = change_of_basis(x, P)
print(f"\nVector {x} in standard basis")
print(f"Coordinates in rotated basis: {x_new}")
print(f"Verification: {P @ x_new}")

---

Applications in AI/ML

Dimensionality Reduction

• PCA (Principal Component Analysis): Finds the orthonormal basis of maximum variance. The first $k$ principal components form a basis for the $k$-dimensional subspace that best approximates the data in the least-squares sense.
• SVD (Singular Value Decomposition): Provides optimal low-rank approximation. Truncating to $k$ singular values gives the best rank-$k$ approximation.

Feature Spaces

• Kernel methods: Map data to high-dimensional feature spaces where linear separation is possible. The basis of this feature space determines the kernel function.
• Word embeddings: Words are represented as vectors in a learned basis. The dimension of the embedding space (e.g., 300 for Word2Vec) is the number of basis vectors.

Signal Processing

• Fourier transform: Decomposes signals into frequency basis vectors.
• Wavelet transform: Multi-resolution basis for time-frequency analysis.
• Compressed sensing: Exploits sparsity in a given basis for signal recovery from few measurements.

Neural Networks

• Weight matrices: Each layer's weight matrix transforms from one basis (input features) to another (hidden features). Learning is finding optimal bases.
• Batch normalization: Normalizes activations to have zero mean and unit variance, effectively choosing a convenient basis for each layer.

# PCA as change of basis
from sklearn.decomposition import PCA
import numpy as np

# Generate sample data
np.random.seed(42)
n_samples = 200
X = np.random.randn(n_samples, 2) @ np.array([[3, 1], [1, 2]])

# PCA finds the optimal basis
pca = PCA(n_components=2)
X_transformed = pca.fit_transform(X)

print("Original data shape:", X.shape)
print("Transformed data shape:", X_transformed.shape)
print("Explained variance ratio:", pca.explained_variance_ratio_)
print("Principal components (new basis):")
print(pca.components_)  # These are the basis vectors

# The principal components form an orthonormal basis
dot_product = np.dot(pca.components_[0], pca.components_[1])
print(f"Dot product of components (should be 0): {dot_product:.10f}")

# Reconstruction: X ≈ X_transformed @ pca.components_
X_reconstructed = X_transformed @ pca.components_ + pca.mean_
reconstruction_error = np.mean((X - X_reconstructed) ** 2)
print(f"Reconstruction MSE: {reconstruction_error:.6f}")

---

Common Mistakes

---

Interview Questions

Q1: What is the difference between a basis and a spanning set?

A spanning set generates the entire space but may contain redundant vectors. A basis is a spanning set with no redundancy — it is linearly independent. Every spanning set can be reduced to a basis by removing dependent vectors.

Q2: How do you find a basis for the null space of a matrix?

Solve $A\vec{x} = \vec{0}$ via row reduction. Express the solution in parametric vector form. The vectors multiplying each free variable form a basis for the null space.

Q3: Why is the dimension of $\mathbb{R}^n$ equal to $n$?

Because any basis for $\mathbb{R}^n$ must have exactly $n$ vectors. The standard basis $\{\vec{e_1}, \ldots, \vec{e_n}\}$ has $n$ vectors, and by the dimension theorem, all bases have the same size.

Q4: What is the relationship between rank, column space, and null space?

• $\text{rank}(A) = \dim(\text{col}(A))$ = number of pivots.
• $\text{nullity}(A) = \dim(\ker(A))$ = number of free variables.
• By rank-nullity: $\text{rank}(A) + \text{nullity}(A) = n$ (columns).
• The column space tells you which $\vec{b}$ allow solutions to $A\vec{x} = \vec{b}$.
• The null space tells you the solutions when they exist (particular + null space).

Q5: Can a matrix have the same row space and column space?

Yes. Example: $A = \begin{bmatrix}1&0\\0&1\end{bmatrix}$ (identity matrix). Row space = column space = $\mathbb{R}^2$. But generally, row space $\subseteq \mathbb{R}^n$ and column space $\subseteq \mathbb{R}^m$ are in different ambient spaces unless $m = n$.

Q6: How does change of basis relate to diagonalization?

If $A$ is diagonalizable, $A = PDP^{-1}$ where $D$ is diagonal and $P$'s columns are eigenvectors. This means: in the eigenbasis, $A$ acts as scaling by eigenvalues. Change of basis to the eigenbasis simplifies matrix operations from $O(n^2)$ to $O(n)$.

Q7: What is the rank of the product $AB$?

$\text{rank}(AB) \leq \min(\text{rank}(A), \text{rank}(B))$. Equality holds when the column space of $B$ intersects the null space of $A$ only at $\vec{0}$.

---

Practice Problems

---

Quick Reference

---

Cross-References

• Previous topic: 019 - Linear Algebra Span
• Next topic: 021 - Linear Algebra Eigenvalues
• Related concepts:
  • Linear Transformations — basis determines matrix representation
  • Matrix Multiplication — change of basis is matrix multiplication
  • Determinant — $A$ is invertible iff $\det(A) \neq 0$ iff columns form a basis
  • Orthogonal Basis — orthonormal basis simplifies computations
  • SVD — provides optimal basis for low-rank approximation