高等代数的应用举例

高等代数的应用举例—2—目录矩阵密码问题.....................................3化学方程式的平衡问题.............................5矩阵密码在保密通讯中的应用.......................6交通流量问题....................................10几何应用........................................12宏观经济模型....................................13情报检索模型....................................16—3—矩阵密码问题矩阵密码法是信息编码与解码的技巧，其中的一种是基于利用可逆短阵的方法．先在26个英文字母与数字间建立起一一对应，例如可以是262521ZYBA若要发出信息“SENDMONEY”，使用上述代码，则此信息的编码是19，5，14，4，13，l5，14，5，25，其中5表示字母E．不幸的是，这种编码很容易被别人破译．在一个较长的信息编码中，人们会根据那个出现频率最高的数值而猜出它代表的是哪个字母，比如上述编码中出现次数最多的数值是5，人们自然会想到它代表的是字母E，因为统计规律告诉我们，字母E是英文单词中出现频率最高的．我们可以利用矩阵乘法来对“明文”SENDMONEY进行加密，让其变成“密文”后再行传送，以增加非法用户破译的难度，而让合法用户轻松解密．如果一个矩阵A的元素均为整数，而且其行列式1A，那么由*11AAA即知，1A的元素均为整数．我们可以利用这样的矩阵A来对明文加密，使加密之后的密文很难破译．现在取232352121A明文“SENDMONEY”对应的9个数值按3列被排成以下的矩阵251514513514419B矩阵乘积—4—937781128118105494543251514513514419232352121AB对应着将发出去的密文编码：43，105，81，45，118，77，49，128，93合法用户用1A去左乘上述矩阵即可解密得到明文．2515145135144199377811281181054945431141021119377811281181054945431A为了构造“密钥”矩阵A，我们可以从单位阵I开始，有限次地使用第三类初等行变换，而且只用某行的整数倍加到另一行，当然，第一类初等行变换也能使用．这样得到的矩阵A，其元素均为整数，而且由于1A可知，1A的元素必然均为整数．—5—化学方程式的平衡问题在光合作用过程中，植物能利用太阳光照射将二氧化碳(2CO)和水(OH2)转化成葡萄糖(6126OHC)和氧(2O)．该反应的化学反应式具有下列形式61264232221OHCxOxOHxCOx为了使反应式平衡，我们必须选择恰当的321,,xxx及4x才能使反应式两端的碳(C)子,氢(H)原子及氧(O)原子数目对应相等．由2CO含一个C原子，而6126OHC含6个C原子,故为维持平衡，必须有416xx类似地，为了平衡O原子，必须有4321622xxxx最后，为了平衡H原子，必须有42122xx如果将所有未知量移至等号左边，那么将得到一个齐次线性方程组012206220642432121xxxxxxxx显然方程组有非零解，为了使化学反应式两端平衡，必须找到一个每个分量均为正数的解Txxxx4321,,,．按通常解法我们可以取4x作为自由未知量，且有434241666xxxxxx特别地，取14x时，则6321xxx．此时化学反应式具有形式6126222666OHCOOHCO—6—矩阵密码在保密通讯中的应用保密通讯，就是通讯者要把消息发送给他指定的接收者，而又不让其他人，特别是对手得到和了解消息的内容．消息的发送方要保密，最好是根本不让除接收者以外的任何人得到所发送的消息，比如人们早期用派专门信使的方法直接将密信送到接收者手中，但这一方法的致命缺点是发送速度慢，且安全性差．由此，消息的发送者想出一个办法：不直接将原来的消息传送出去，而将它按一定的规则加以改变和伪装后再传送出去．密码学中称原来的消息为明文，用人们日常生活中的语言写成，谁都看得懂．经过伪装的明文则变成了密文，别人看不懂．由明文变成密文的过程称为加密．由密文变成明文的过程称为译密．改变明文的方法称为密码，密码作为军事和政治斗争的一种技术，已有上千年的历史．随着科学技术的发展，信息传播越来越频繁和便捷，保密通讯也日益扩展到民间的经济生活以及日常生活当中．密码中的关键信息称之为密钥，显然，密钥在保密通讯中占有极其重要的地位，通常主要由通讯双方秘密商定．当一个人知道了密码，就可以读懂密文，若不知道密码，即使他得到了密文，也看不懂，这样就达到了保密的目的．人们对密文进行分析，企图找到译密的法则，这一过程称为破译．保密通讯就是在保密者和破译者之间的不断斗争中发展起来的．置换密码是一个最容易而且最为人们熟悉的密码，他只要把每个字母由某个其他字母来替换而形成密文．如指定从a到z的26个英文字母按顺序依次用从0到25这26个非负整数来表示，选定其中一个正整数X为密钥，就制作成一张密码表．加密的方法是将每个明文字母所代表的整数加上X，这里的“加法”是指如果加法的结果达到或超过26，还要将它诚去26，这种加法称为模26加，即若P表示明文字母所代表的整数，C为密文字母所代表的整数，则有记号26modKPC又称为模26的同余式．这种密码又称为加法密码．例如，如果明文信息是：—7—MEETINGINMYOFFICE取5K，由刚才的约定，得到的密文信息是：RJJYNSLNSRDTKKNHJ这在外人眼里是一组毫无意义的字母．如果我们知道密码是由加法密码书写的，对于如下的秘密信息：FRPHKHUHLPPHGLDWHOB我们如何进行解密呢?一种可能浪费时间的解密方法是，把1到25的每一个整数代入关系式26modKCP中去试直到出现合适的K．考虑密文中的第一块：FRPHK试到3K时，对应明文OOMEH这个K似乎是合理的，因此取3K时．对应明文是：COMEHEREIMMEDIATELY(comehereimmediately)另一种解密方法是利用每个字母在英文语言中出现的频率．上面的密文中出现频率最大的字母是H，而在英文中字母E的出现频率最大，所以让密文中的H与英文中字母E对应似乎是合理的，解方程26mod58K，得3K．置换密码中同一明文字母总是对应同一密文字母，人们可以利用字母出现频率、重复方式及字母和字母的结合方式，应用到密码中来解方程．由此可知，用此种密码书写的密文是很容易破译的，保密性很差．于是编码学家创造了一种新的密码，叫做矩阵密码．矩阵密码是将一组n个明文字母指派给一组n个密文字母，同一字母可以有不同的对应，每一个字母用一个数代表：让1到26表示A到Z，27表示空格，28表示?，29表示!．为简便起见，取2n，加密过程是同时取两个明文字母1P和2P，用它们的等价数字置换成具有如下形式的模29的同余式：29mod29mod212211dPcPCbPaPC—8—这样就确定了明文字母1P和2P的等价密码1C和2C，如此一对一对进行下去，直到全部信息都被加密．使用矩阵乘法，令dcbaM加密过程可记作29mod2121PPMCC称M为密码矩阵．这种加密方法破坏了字母出现频率的不变性，加大了破译的难度．为使破译更加困难，我们可以使用更大的n，例如取3n,假设密码矩阵632741320M要加密的明文是UNITEDNATIONS明文字母的等价数字依次是：21，14，9，20，5，4，27，14，1，20，9，15，14，19。因为3n，所以让每三个连续的字母成为一个列向量，进行矩阵运算：OLOUVRPCJXCEBVZ29mod15121521221816310243522226247157102791382791619068140119633122552715149199145141420272021632741320这个信息的密文是ZXVVJUBCOEPLCRO—9—可见字母出现频率的不变性被打破了。假设密码矩阵不变，那么，如下的密文又如何解密呢？WUUF!NSOWVKLMHURLQHKWKI求出密码矩阵M的逆矩阵2453682331M先对前12个字母进行译密，得到29mod9513142714275251541911152221221929212314623245368233继续作下去，得到明文信息是：SENDMONEYIMMEDIATELY!为了保证密码系统的保密性，我们可以使用更大的n值。但应注意使用密码矩阵时，应保证密码矩阵及其逆矩阵必须是整数矩阵，即矩阵中的元是整数．这里我们不再做更详细的介绍．这里我们应注意矩阵乘法、逆矩阵等的应用．—10—交通流量问题设下图3-1所示的是某一地区的公路交通网络图，所有道路都是单行道，且道上不能停车，通行方向用箭头标明，标示的数字为高峰期每小时进出网络的车辆．进入网络的车共有800辆等于离开网络的车辆总数，另外，进入每个交叉点的车辆数等于离开该交叉点的车辆数，这两个交通流量平衡的条件都得到满足．若引入每小时通过图示各交通干道的车辆数wvuts,,,,和x(例如s就是每小时通过干道BA的车辆数等)，则从交通流量平衡条件建立起的高等代数方程组，可得到网络交通流量的一些结论。解对每一个道路交叉点都可以写出一个流量平衡方程，例如对A点，从图上看，进入车辆数为s200,而离开车辆数为t，于是有对A点：ts200对B点：vs100200对C点：uxv300对D点：wtu300对E点：xw200300这样得到一个描述网络交通流量的高等代数方程组—11—100300300300200xwwutxvuvsts由此可得xwxvuvtvs100300500300其中xv,是可取任意值的．事实上，这就是方程组的解，当然也可将解写成212112111,,100300500300kkkkkkkkk可以取任意实数。方程有无限多个解。可必须注意的是，方程组的解并非就是原问题的解，对于原问题。必须顾及各变量的实际意义为行驶经过某路段的车辆数，故必须为非负整数，从而由00100003000300221211kxkwkvkkuks可知1k是不超过300的非负整数，2k是不小于100的正整数，而且21kk不小于300．所以方程组的无限多个解中只有一部分是问题的解．从上述讨论可知，如若每小时通过EC段的车辆太少，不超过100辆；或者每小时通过BC及EC的车辆总数不到300辆，则交通平衡将被破坏，在一些路段可能会出现塞车等现象．—12—几何应用设矩阵333222111cbacbacba111222333abcabcabc满秩，试判断两直线2132132131:ccczbbbyaaaxL与3213213212:ccczbbbyaaaxL