趣题:不动点与线性代数

    假设 X 、 Y 是两个有限集合,f:X→Y 和 g:Y→X 是两个函数。求证:复合函数 g∘f 和 f∘g 拥有相同数量的不动点(也就是说 g(f(x)) = x 和 f(g(y)) = y 的解的个数相同)。

    下面先提供一个“正常”的解法。观察函数 g∘f 的不动点,可以看出它有以下两个性质:首先,如果某个 x 是 g∘f 的不动点,即 x = g(f(x)) ,那么 f(x) = f(g(f(x))),这就说明 f(x) 是 f∘g 的一个不动点;另外,如果 x1 和 x2 是 X 中两个不同的不动点,则函数 f 不可能把它们映射到 Y 中的同一个元素,否则 g 没办法把它分别还原成 x1 和 x2 。结合上面两点可以看出, f∘g 中的不动点至少和 g∘f 的一样多。

    同理,考察 f∘g 的不动点,可知 g∘f 的不动点至少和 f∘g 的一样多。这就说明了 g∘f 和 f∘g 拥有相同数量的不动点。


    今天在 reddit 上学到了一招:利用线性代数的一些已知结论,我们可以得到一个更帅的证明方法。把集合 X 和 Y 的元素个数分别记作 |X| 和 |Y| ,再把函数 f 和 g 分别表示成 |X| × |Y| 的 01 矩阵 A 和 |Y| × |X| 的 01 矩阵 B 。我们可以用矩阵的乘积来表示复合函数, AB 和 BA 这两个矩阵就分别表示复合函数 g∘f 和 f∘g 。而 g∘f 和 f∘g 的不动点个数,也就是对应矩阵的迹。由于 tr(AB) = tr(BA) ,因此 g∘f 和 f∘g 拥有相同数量的不动点。

    如果你喜欢这样的证明,千万不要错过另外两个线性代数出奇制胜的例子:选取最多的子集使得任两子集恰有一个公共元素,以及完全图 Kn 最少可以拆成多少个完全二分图

26 条评论

发表评论