Linear Basis: A Brief Tutorial (TBC)

线性 <s>Gay</s>

Pre Knowledge

线性代数:矩阵论

Preview & Introduction

线性基本来就是线性代数里面一块基础的内容(所以才叫线性基)。
建立一个独立的专题进行探讨我也是纠结了一会儿。
其概念在线性代数里很重要,而在我打算另写一套线性代数教程的情况下势必会有重复。
然而其在 OI 里面因为异或运算的线性性使得它有更加令人愉悦的用途。
故此我的打算是先完成如此教程,以后作线性代数教程时将另作指向。

本文将重点探讨异或运算与其线性性在线性代数视角的理论及运用,也可作为线性代数学习过程中的一个实例。

Basis: What We Concerned Here in Linear Algebra

线性代数是研究<s>搞</s>基的代数学。

线性空间(Linear Space)的基底(Basis)的概念,在高中数学学习向量初步的时候其实已经略有涉及。
我们已经知道,平面上任意两个不共线的向量的线性组合可以表示平面任意向量。Namely, 给定
基底向量 $ \mathbf v_0 ,\mathbf v_1 $,则对所有向量 $ \mathbf v = a \mathbf v_0 + b \mathbf v_1 $ 均存在 $ a,b \in \mathbb R $ 使其成立。

一般的

Field & Operation Axioms

Vector Space

Linear (In)dependent

Linear Combination

Span

Basis

Back to OI: Operation with XOR

XOR: The Definition and Properties

How to Get It: Gaussian Elimination

Problems in OI

SGU 275

给出一个集合,问最大异或和。
求出线性基后求得异或和即可。

HDU 3949

给出一个集合,问第k小异或和。
求出线性基后按二进制贡献分类。注意只有当矩阵满秩才会构成零。

References

[1]线性基学习笔记|Sengxian's Blog

太懒了所以留个坑督促自己赶紧来写点东西。

标签: none

添加新评论