向量空间

What · 是什么

向量空间（线性空间）是由向量集合V、域P、加法和数乘组成的代数结构。满足8条公理（加法群公理+数乘公理）。核心概念：线性相关/无关、极大线性无关组（基）、维数、子空间、线性包（张成空间）。矩阵的行向量/列向量张成行空间/列空间，其维数即为矩阵秩。OI中常用GF(2)域上的向量空间（异或空间）和实数域上的向量空间。

Why · 为什么

How · 实现

伪代码

linear_independent(vectors):
  return rank(vectors) == len(vectors)

span_dim(vectors):
  return rank(vectors)

Python 实现

def is_linearly_independent(vectors, mod=None):
    """Check if vectors are linearly independent by computing rank."""
    if not vectors:
        return True
    n = len(vectors)
    m = len(vectors[0])
    # Transpose: treat each vector as a row
    A = [list(v) for v in vectors]
    rank = _compute_rank(A, mod)
    return rank == n

def _compute_rank(A, mod=None):
    n, m = len(A), len(A[0])
    A = [row[:] for row in A]
    rank = 0
    for col in range(m):
        if rank >= n:
            break
        pivot = -1
        for row in range(rank, n):
            val = A[row][col]
            if mod:
                val %= mod
            if val != 0:
                pivot = row
                break
        if pivot == -1:
            continue
        A[rank], A[pivot] = A[pivot], A[rank]
        if mod:
            inv = pow(A[rank][col] % mod, mod - 2, mod)
            for j in range(m):
                A[rank][j] = A[rank][j] * inv % mod
            for r in range(n):
                if r != rank and A[r][col] % mod != 0:
                    factor = A[r][col]
                    for j in range(m):
                        A[r][j] = (A[r][j] - factor * A[rank][j]) % mod
        else:
            piv = A[rank][col]
            for j in range(m):
                A[rank][j] /= piv
            for r in range(n):
                if r != rank and abs(A[r][col]) > 1e-9:
                    factor = A[r][col]
                    for j in range(m):
                        A[r][j] -= factor * A[rank][j]
        rank += 1
    return rank

def span_dimension(vectors, mod=None):
    """Dimension of the subspace spanned by given vectors."""
    if not vectors:
        return 0
    return _compute_rank([list(v) for v in vectors], mod)

if __name__ == "__main__":
    # Linearly independent
    assert is_linearly_independent([[1, 0], [0, 1]]) == True
    # Linearly dependent
    assert is_linearly_independent([[1, 2], [2, 4]]) == False
    # Three vectors in 2D are dependent
    assert is_linearly_independent([[1, 0], [0, 1], [1, 1]]) == False
    # Span dimension
    assert span_dimension([[1, 0], [0, 1]]) == 2
    assert span_dimension([[1, 2], [2, 4]]) == 1
    assert span_dimension([[1, 0, 0], [0, 1, 0], [0, 0, 1]]) == 3
    # Mod arithmetic
    assert is_linearly_independent([[1, 2], [3, 4]], mod=10**9 + 7) == True
    print("vector-space: ALL TESTS PASSED")

易错点

• 零向量与任意向量线性相关
• 向量个数>维数时必然线性相关
• 基不唯一但维数唯一
• GF(2)域上加减法=异或，数乘=与

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/linear-algebra/vector-space/
• 书籍✓ 线性代数教材