趣题：不动点与线性代数

    假设 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 条评论

发表评论




Enter Captcha Here :