线性基

概述

基(basis)是线性代数中的一个概念,它是描述、刻画向量空间的基本工具。

线性无关

在线性代数里,向量空间的一组元素中,若没有向量可用有限个其他向量的线性组合所表示,则称为线性无关或线性独立(linearly independent),反之称为线性相关(linearly dependent)。

假设V是在域K上的向量空间。如果v1, v2, ..., vn 是V的向量,称它们为线性相关,如果从域K 中有非全零的元素a1, a2, ..., an,使得
a1v1+a2v2++anvn=0a_1 \mathbf{v}_1 + a_2 \mathbf{v}_2 + \cdots + a_n \mathbf{v}_n = \mathbf{0}

(注意右边的零是V的零向量,不是K的零元。)

如果K中不存在这样的元素,那么v1, v2, ..., vn是线性无关。

对线性无关可以给出更直接的定义。向量v1, v2, ..., vn线性无关,当且仅当它们满足以下条件:如果a1, a2, ..., an是K的元素,适合:

a1v1 + a2v2 + ... + anvn = 0,
那么对所有i = 1, 2, ..., n都有ai = 0。

在V中的一个无限集,如果它任何一个有限子集都是线性无关,那么原来的无限集也是线性无关。

线性相关性是线性代数的重要概念,因为线性无关的一组向量可以生成一个向量空间,而这组向量则是这向量空间的基。

算法比赛中的线性基

  1. 异或运算下的基
  2. 对质数取模下的基
    可以通过高斯消元的方法来求解。

参考题目

bzoj 2844

bzoj 3811

bzoj 4004

hdu 3949

参考资料

https://en.wikipedia.org/wiki/Linear_independence

https://blog.sengxian.com/algorithms/linear-basis

  1. 线性基
    1. 概述
    2. 线性无关
    3. 算法比赛中的线性基
    4. 参考题目
    5. 参考资料