离散数学学习体会

离散数学学习体会 离散数学学习心得 (1) -- 一类抽象代数题的解题思路 学习离散数学已经有一段时间了，书读了不少，题也做了一些。最近又常在群里和研友们讨论离散数学中的问题。所以对离散数学也有了一些心得和体会。在今后的一段时间里，我会不定期的写一些小的经验总结，以供后来人参考。 这次我们来讨论一类代数问题的解题思路。 问题:设R为含幺环，求证:对任意a,b?R，若1-ab可逆，则1-ba也可逆。 分析: 我们知道，证明问题的方法大致可以分为两类:构造性证明和存在性证明。前者要求给出一个切实的方法，找出符合命题要求的元素(在这道题中，就是找到1-ba的逆元)。后者则只证明这样的元素必然存在，但并不给出切实的寻找方法。反证法是存在性证明的基本方法。 无论打算采用是哪种证明方法，确认一下我们可以使用的前提条件总是必要的。 就这道题而言，我们可以使用这些前提: 1、R是含幺环。这就意味着R对加法构成Abel群(从而我们可以自由地使用加法交换律、加法消去律、加法逆元等)，R对乘法构成独异点(从而可以使用乘法单位元1)，当然还有乘法对加法的分配律。 2、1-ab是可逆的，这就是说，存在c?R，使得c(1-ab)=(1-ab)c=1。移项后得到:cab=abc=c-1。 需要注意的是: 1、在题设中没有假设R的可换性(事实上，如果R可换的话，整个问题就没有任何难度了)，也没有假设a、b是可逆的。所以，在解题时，不能使用乘法交换律，也不能随便使用a、b的逆元(除非已经证明了它们的存在性)。 2、如果没有1-ab可逆这个条件，肯定是推不出1-ba可逆的(我们在环中可以找到太多的反例)。所以，cab=abc=c-1将是解题的关键。观察这个式子，我们注意到，它提供了在c的参与下，移动和消去ab的方法。 我们的目的是，证明存在这样的一个元素d?R，满足(1-ba)d=d(1-ba)=1。 初看到这道题，我们并不知道使用构造性证明容易还是使用反证法容易。 不过推理一下我们可以发现，如果要使用反证法的话，我们需要反设1-ba不存在乘法逆元，然后由此推出1-ab也不可能有逆元(或者推出R不是含幺环)。 但反设1-ba不存在乘法逆元后，我们到底能推出哪些结论来呢,似乎很少。我们甚至连“对任意x?R，必有x(1-ba)?1”这样简单的情况都难以证明(因为我们只假设了1-ba没有“乘法逆元”，并不能由此推出1-ba没有“乘法左逆元”)。 另一方面，利用等式cab=abc=c-1直接构造出一个1-ba的逆元应该一个比较有希望的方法。 这时，我们可以“取巧”了。注意到: 1、如果我们相信题目给的命题没有错的话，我们只要找到1-ba的左逆元(或者右逆元)就基本完成任务了(虽然最终书写证明时，我们需要证明我们找到的元素既是左逆元又是右逆元)。因为如果一个元素的左右逆元都存在的话，它的左右逆元是唯一且相等的(所以，1-ba确实可逆，而我们又找到了它的一个左逆元x，那么这个x自然也是1-ba的右逆元)。 2、不要指望证明c本身也是1-ba的逆元。因为假如是这样的话，(1-ab)和(1-bc)就都是c的逆元，由逆元的唯一性可知，1-ab=1-ba，利用消去律，我们可以得到ab=ba。这就说，在这个环里，只要1-ab有逆元，a和b就是可换的。这个符合“含幺环R”的一般情况吗,显然不符合。比如，由所有实矩阵对矩阵加法和矩阵乘法组成的环，它是含幺环。但只要|a|?|b|?1，1-ab就可逆，但这样的矩阵都可换吗,显然不是的。这就说明，即使1-ab的逆元c存在，1-ba的逆元(如果存在的话)也未必是c。 3、我们前面看到，在这道题中，c的存在性是1-ba可逆的一个不可缺少的条件，但c本身并不一定就是1-ba的逆元(仅当ab=ba时，c是1-ba的逆元)。那么，1-ba的逆元应该是一个与c有某种关系的元素。 根据这些线索，我们来寻找1-ba的乘法逆元(不妨先寻找左逆元)。 前面已经提到，cab=abc=c-1应该是解题的一个关键。那么，如果要使用它，就得用一个式子(不妨记为X)与(1-ba)相乘，使得它们的乘积中出现包含cab或者abc的项。 因为 X(1-ba) = X - Xba。我们很容易看出，如果X中有以ca结尾的项(不妨记作Yca)，那么就可以得到 Ycaba 这样的项，而这个项可以换成 Yabca 或 Y(c-1)a。这些式子也许有助于我们消掉那些不需要的项。 这样，我们不妨设 X = (Yca + Z)，其中Y和Z分别是两个式子(注意到，这样的假设是具有一般性的，任何含有以ca结尾的项的式子都能写成Yca+Z的样子)。 看看这样乘出来的式子是什么样的: X(1-ba) = (Yca + Z)(1 - ba) = Yca + Z - Ycaba - Zba = Yca + Z - Y(c-1)a - Zba = Yca + Z - Yca + Ya - Zba = Z - Zba + Ya 好了，现在我们得到一个当 X = (Yca + Z) 时，乘积的一般形式，如果能给Y和Z适当的值，使得Z - Zba + Ya = 1，那么相应的X就是我们要找的逆元了。 我们发现，要想把Zba消掉，Ya就应该也以ba结尾。看到这里，结果已经很明显了，令Y=b，Z=1，则 Z - Zba + Ya = 1 - ba + ba = 1。 这就是说，我们已经发现，当 X = (bca + 1) 时，X(1-ba)=1。这样的X 就是1-ba的左逆元了。 证明X是右逆元的工作是简单的，和前面这段推导一样，只需利用等式abc = c-1就可以了。 写在答题纸上的证明只不过是后面那小小的一段: (bca+1)(1-ba) = bca+1-bcaba-ba = bca+1-b(c-1)a-ba = bca+1-bca+ba-ba = 1 (1-ba)(bca+1) = bca-babca+1-ba = bca-b(c-1)a+1-ba = bca-bca+ba+1-ba = 1 而寻找bca+1的过程才是解题的关键。 总结一下我们的思路: 1、我们得到一些已知条件，需要找到一个未知的、满足某种特定条件的元素d。 2、整理出我们可以使用的条件和不可以使用的条件(在抽象代数里要特别注意“不可以使用的条件”。因为抽象代数里常常使用以往算术运算中的符号，使人容易不自觉地使用一些在实数域上成立，但在其它代数系统上未必成立的性质和原理)。 3、找到一些重要的等式，把它们变形为容易利用的形式(通常一边是一个单项，这样才方便在等式中代换)。 4、写出待求元素的一般形式，考虑如何在其中利用我们在第3步找出的等式。 5、根据推导的结果，确定待求元素的具体形式。 6、证明结果的正确性。 抽象代数中许多构造性证明都可以按这一思路进行。 从这里也可以看出，虽然抽象代数中绝大多数题都是证明题，但在大多数情况下，观察、分析和试探仍然是解决问题的关键所在。