在集合 {1, 2, …, n} 中选出尽可能多的子集，使得每个子集所含的元素个数都是奇数，但是任意两个子集的交集都含有偶数个元素。那么，我们最多能够选出多少个这样的子集来？

    容易看出，我们至少可以选出 n 个子集。例如，当 n = 4 时， {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗？简单地尝试后，你会觉得似乎不行。不过，这却并不是显然的，因为存在一些不那么平凡的方案，也能让子集的数量达到 n ，例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4} 这 4 个子集也是满足要求的。看来，证明最多只能选出 n 个子集，好像并不那么容易。

    不过，借助线性代数，我们有一个几乎是秒杀的证明方法。假如说我们可以从集合 {1, 2, …, n} 中选出 m 个满足要求的子集，并且用 m 个 n 维 01 向量 v₁, v₂, …, v_m 分别表示这 m 个子集。例如，当 n = 4 时，子集 {1, 2, 4} 就表示成向量 (1, 1, 0, 1) 。我们用 v^T 来表示矩阵的转置。注意到， v_i^T · v_j 正好等于这两个向量所对应的子集的交集的元素个数。根据要求，这些向量必须满足，对于任意一个 i ，v_i^T · v_i 都是奇数，而对于任意两个不同的 i 和 j ， v_i^T · v_j 都是偶数。下面，我们证明这 m 个向量在模 2 的有限域 F₂ 上是线性无关的，从而说明 m 一定小于等于 n 。

    只需要注意到，如果存在一组数 a₁, a₂, …, a_n 使得

      a₁ v₁ + a₂ v₂ + … + a_n v_n = 0

    那么对于任意一个 i ，都有

      0 = (a₁ v₁ + a₂ v₂ + … + a_i v_i + … + a_n v_n)^T v_i
        = a₁ v₁^T v_i + a₂ v₂^T v_i + … + a_i v_i^T v_i + … + a_n v_n^T v_i
        = a_i

    因此，这 m 个向量是线性无关的。

 
题目来源：http://mathoverflow.net/questions/33911/why-linear-algebra-is-funor
一个非常类似的问题：选取最多的子集使得任两子集恰有一个公共元素
更多线性代数的妙用：一个图论问题、一个不动点数量问题、盒子的三边和问题