高等代数的应用举例

高等代数的应用举例 2 目 录 目 录 矩阵密码问题 . 3 化学方程式的平衡问题 . 5 矩阵密码在保密通讯中的应用 . 6 交通流量问题 . 10 几何应用 . 12 宏观经济模型 . 13 情报检索模型 . 16 3 矩阵密码问题 矩阵密码问题 矩阵密码法是信息编码与解码的技巧， 其中的一种是基于利用可逆短阵的方 法先在 26 个英文字母与数字间建立起一一对应，例如可以是 262521 ZYBA 若要发出信息“SEND MONEY”，使用上述代码，则此信息的编码是 19，5， 14，4，13，l 5，14，5，25，其中 5 表示字母 E不幸的是，这种编码很容易 被别人破译在一个较长的信息编码中，人们会根据那个出现频率最高的数值而 猜出它代表的是哪个字母，比如上述编码中出现次数最多的数值是 5，人们自然 会想到它代表的是字母 E， 因为统计规律告诉我们， 字母 E 是英文单词中出现频 率最高的 我们可以利用矩阵乘法来对“明文”SEND MONEY 进行加密，让其变成“密 文”后再行传送，以增加非法用户破译的难度，而让合法用户轻松解密如果一 个矩阵A的元素均为整数，而且其行列式1A，那么由 * 1 1 AA A 即知， 1 A 的元素均为整数我们可以利用这样的矩阵A来对明文加密，使加密之后的密文 很难破译现在取 232 352 121 A 明文“SEND MONEY”对应的 9 个数值按 3 列被排成以下的矩阵 251514 5135 14419 B 矩阵乘积 4 937781 128118105 494543 251514 5135 14419 232 352 121 AB 对应着将发出去的密文编码： 43，105，81，45，118，77，49，128，93 合法用户用 1 A去左乘上述矩阵即可解密得到明文 251514 5135 14419 937781 128118105 494543 114 102 111 937781 128118105 494543 1 A 为了构造“密钥”矩阵A，我们可以从单位阵I开始，有限次地使用第三类初 等行变换，而且只用某行的整数倍加到另一行，当然，第一类初等行变换也能使 用这样得到的矩阵A，其元素均为整数，而且由于1A可知， 1 A的元素必 然均为整数 5 化学方程式的平衡问题 化学方程式的平衡问题 在光合作用过程中，植物能利用太阳光照射将二氧化碳( 2 CO)和水(OH2)转 化成葡萄糖( 6126 OHC)和氧( 2 O)该反应的化学反应式具有下列形式 61264232221 OHCxOxOHxCOx 为了使反应式平衡， 我们必须选择恰当的 321 ,xxx及 4 x才能使反应式两端的碳(C) 子,氢(H)原子及氧(O)原子数目对应相等由 2 CO含一个C原子，而 6126 OHC含 6 个C原子,故为维持平衡，必须有 41 6xx 类似地，为了平衡O原子，必须有 4321 622xxxx 最后，为了平衡H原子，必须有 42 122xx 如果将所有未知量移至等号左边，那么将得到一个齐次线性方程组 0122 0622 06 42 4321 21 xx xxxx xx 显然方程组有非零解，为了使化学反应式两端平衡，必须找到一个每个分量均 为正数的解 T xxxx 4321 ,按通常解法我们可以取 4 x作为自由未知量，且有 43 42 41 6 6 6 xx xx xx 特别地，取1 4 x时，则6 321 xxx此时化学反应式具有形式 6126222 666OHCOOHCO 6 矩阵密码在保密通讯中的应用 矩阵密码在保密通讯中的应用 保密通讯，就是通讯者要把消息发送给他指定的接收者，而又不让其他人， 特别是对手得到和了解消息的内容消息的发送方要保密，最好是根本不让除接 收者以外的任何人得到所发送的消息， 比如人们早期用派专门信使的方法直接将 密信送到接收者手中， 但这一方法的致命缺点是发送速度慢， 且安全性差 由此， 消息的发送者想出一个办法：不直接将原来的消息传送出去，而将它按一定的规 则加以改变和伪装后再传送出去 密码学中称原来的消息为明文，用人们日常生活中的语言写成，谁都看得 懂经过伪装的明文则变成了密文，别人看不懂由明文变成密文的过程称为加 密由密文变成明文的过程称为译密改变明文的方法称为密码，密码作为军事 和政治斗争的一种技术，已有上千年的历史随着科学技术的发展，信息传播越 来越频繁和便捷，保密通讯也日益扩展到民间的经济生活以及日常生活当中密 码中的关键信息称之为密钥，显然，密钥在保密通讯中占有极其重要的地位，通 常主要由通讯双方秘密商定当一个人知道了密码，就可以读懂密文，若不知道 密码，即使他得到了密文，也看不懂，这样就达到了保密的目的 人们对密文进行分析，企图找到译密的法则，这一过程称为破译保密通讯 就是在保密者和破译者之间的不断斗争中发展起来的 置换密码是一个最容易而且最为人们熟悉的密码， 他只要把每个字母由某个 其他字母来替换而形成密文 如指定从a到z的 26 个英文字母按顺序依次用从 0 到 25 这 26 个非负整数来表示，选定其中一个正整数X为密钥，就制作成一张 密码表加密的方法是将每个明文字母所代表的整数加上X，这里的“加法”是指 如果加法的结果达到或超过 26，还要将它诚去 26，这种加法称为模 26 加，即 若P表示明文字母所代表的整数，C为密文字母所代表的整数，则有记号 26modKPC 又称为模 26 的同余式这种密码又称为加法密码 例如，如果明文信息是： 7 MEETING IN MY OFFICE 取5K，由刚才的约定，得到的密文信息是： RJJYN SLNSR DTKKN HJ 这在外人眼里是一组毫无意义的字母 如果我们知道密码是由加法密码书写的，对于如下的秘密信息： FRPHK HUHLP PHGLD WHOB 我们如何进行解密呢? 一种可能浪费时间的解密方法是，把 1 到 25 的每一个整数代入关系式 26modKCP 中去试直到出现合适的K考虑密文中的第一块： FRPHK 试到3K时，对应明文 OOMEH 这个K似乎是合理的，因此取3K时对应明文是： COMEH EREIM MEDIA TELY(come here immediately) 另一种解密方法是利用每个字母在英文语言中出现的频率 上面的密文中出 现频率最大的字母是H， 而在英文中字母E的出现频率最大， 所以让密文中的H 与英文中字母E对应似乎是合理的，解方程26mod58K，得3K 置换密码中同一明文字母总是对应同一密文字母，人们可以利用字母出现 频率、重复方式及字母和字母的结合方式，应用到密码中来解方程由此可知， 用此种密码书写的密文是很容易破译的，保密性很差于是编码学家创造了一种 新的密码，叫做矩阵密码 矩阵密码是将一组n个明文字母指派给一组n个密文字母， 同一字母可以有 不同的对应，每一个字母用一个数代表：让 1 到 26 表示A到Z，27 表示空格， 28 表示?，29 表示! 为简便起见，取2n，加密过程是同时取两个明文字母 1 P和 2 P，用它们 的等价数字置换成具有如下形式的模 29 的同余式： 29mod 29mod 212 211 dPcPC bPaPC 8 这样就确定了明文字母 1 P和 2 P的等价密码 1 C和 2 C，如此一对一对进行 下去，直到全部信息都被加密使用矩阵乘法，令 dc ba M 加密过程可记作 29mod 2 1 2 1 P P M C C 称M为密码矩阵这种加密方法破坏了字母出现频率的不变性，加大了破译的 难度为使破译更加困难，我们可以使用更大的n，例如取3n,假设密码矩阵 632 741 320 M 要加密的明文是 UNITED NATIONS 明文字母的等价数字依次是：21，14，9，20，5，4，27，14，1，20，9，15， 14，19。因为3n，所以让每三个连续的字母成为一个列向量，进行矩阵运算： OLOUV RPCJX CEBVZ 29mod 1512152122 181631024 3522226 24715710279138 2791619068140 11963312255 2715149 19914514 1420272021 632 741 320 这个信息的密文是 ZXVVJUBCOEPLCRO 9 可见字母出现频率的不变性被打破了。假设密码矩阵不变，那么，如下的密文又 如何解密呢？ WUUF! NSOW VKLMH URLQH KWKI 求出密码矩阵M的逆矩阵 245 368 233 1 M 先对前 12 个字母进行译密，得到 29mod 951314 2714275 2515419 11152221 22192921 2314623 245 368 233 继续作下去，得到明文信息是： SEND MONEY IMMEDIATELY! 为了保证密码系统的保密性， 我们可以使用更大的 n 值。 但应注意使用密码 矩阵时， 应保证密码矩阵及其逆矩阵必须是整数矩阵， 即矩阵中的元是整数 这 里我们不再做更详细的介绍 这里我们应注意矩阵乘法、逆矩阵等的应用 10 交通流量问题 交通流量问题 设下图 3-1 所示的是某一地区的公路交通网络图，所有道路都是单行道，且道 上不能停车，通行方向用箭头标明，标示的数字为高峰期每小时进出网络的车 辆进入网络的车共有 800 辆等于离开网络的车辆总数，另外，进入每个交叉 点的车辆数等于离开该交叉点的车辆数，这两个交通流量平衡的条件都得到满 足 若引入每小时通过图示各交通干道的车辆数wvuts,和x (例如s就是每小时通 过干道 BA 的车辆数等)，则从交通流量平衡条件建立起的高等代数方程组，可 得到网络交通流量的一些结论。 解 对每一个道路交叉点都可以写出一个流量平衡方程，例如对A点，从图 上看，进入车辆数为s200 ,而离开车辆数为t，于是有 对 A 点： ts 200 对 B 点： vs 100200 对 C 点： uxv300 对 D 点： wtu300 对 E 点： xw200300 这样得到一个描述网络交通流量的高等代数方程组 11 100 300 300 300 200 xw wut xvu vs ts 由此可得 xw xvu vt vs 100 300 500 300 其中xv,是可取任意值的事实上，这就是方程组的解，当然也可将解写成 21 2 1 1 21 1 1 , 100 300 500 300 kk k k k kk k k 可以取任意实数。 方程有无限多个解。 可必须注意的是，方程组的解并非就是原问题的解，对于原问题。必须顾及 各变量的实际意义为行驶经过某路段的车辆数，故必须为非负整数，从而由 0 0100 0 0300 0300 2 2 1 21 1 kx kw kv kku ks 可知 1 k是不超过 300 的非负整数， 2 k是不小于 100 的正整数， 而且 21 kk 不 小于 300所以方程组的无限多个解中只有一部分是问题的解 从上述讨论可知，如若每小时通过 EC 段的车辆太少，不超过 100 辆；或者 每小时通过 BC 及 EC 的车辆总数不到 300 辆，则交通平衡将被破坏，在一些路 段可能会出现塞车等现象 12 几何应用 几何应用 设矩阵 333 222 111 cba cba cba 111 222 333 abc abc abc 满秩，试判断两直线 21 3 21 3 21 3 1: cc cz bb by aa ax L 与 32 1 32 1 32 1 2 : cc cz bb by aa ax L 的关系。 解 将 iiii cba,视为空间中三点3 , 2 , 1iMi对应的向量，由空间解析几何中 关于三向量混合积的几何意义知， 直线 1 L与 2 L共面的充要条件是 21 , 32 13 三向量共面（线性相关） 。很明显， 0 133221 ，故 1 L与 2 L共面。 而令0 322211 kk， 由题设矩阵满秩， 即 321 ,线 性无关知，0 21 kk， 即 21 与 32 线性无关， 亦即两向量 21 , 32 不平行，因此 1 L与 2 L相交。 13 宏观经济模型 宏观经济模型 假定一个国家的经济可以分解为n个部门，这些部门都有生产产品或服务的 独立功能。 设单列n元向量X是这些n个部门的产出， 组成在 n R 空间的产出向量。 考虑它有外部的需求，要向外提供产品。设d为外部需求向量，它也是 n R 空间 的单列向量，表示这n个部门以外的非经济部门对该国经济各部门的需求，比如 政府消费、出口和战略储备等等。在各经济部门进行满足外部需求的生产时，它 们也必须增加内部的相互需求，这种各部门的内部交叉需求非常复杂。Leontiff 提出的问题是， 为了满足外部的最终需求向量d， 各生产部门的实际产出X应该 是多少，这对于经济计划的制订当然很有价值。因为X=内部需求+外部需求 dLeontiff的输入输出模型中的一个基本假定是：对于每个部门，存在着一个在 n R 空间单位消耗列向量 i v ，它表示第i个部门每产出一个单位（比如100万美金） 产品，需要消耗其他部门产出的数量。把这n个 i v ，并列起来，它可以构成一个 nn 的系数矩阵，可称为内部需求矩阵V。由于要向外部提供产品，故内部需求 矩阵各列向量元素的和必然小于1（上例中要求它等于1） 。 举一个最简单的例子，假如国民经济由三个部门组成，它们是制造业、农业 和服务业。它们的单位消耗列向量如下表。 每单位输出的输入消耗 向下列部 门购买 制造业 农业 服务业 制造业 0.5 0.4 0.2 农业 0.2 0.35 0.15 服务业 0.15 0.1 0.3 如果制造业产出了100个单位的产品，有50个单位会被自己消耗，20个单位被农 业消耗，而被服务业消耗的是15个单位，用算式表示为 14 15 20 50 15. 0 2 . 0 5 . 0 100100 1 v 这就是内部消耗的计算方法，把几个部门都算上，可以写出 内部需求= XV x x x vvvvxvxvx 3 2 1 321332211 其中 3 . 01 . 015. 0 15. 035. 02 . 0 2 . 04 . 05 . 0 V 于是总的需求方程可以写成为： dXVI dVXX 从而可用MATLAB语句写出其解的表示式 dVIinvX 用一个数字来试算一下，设外部需求为 30 20 10 d 用以下程序 ea710 解出X V=0.5,0.4,0.2;0.2,0.35,0.15;0.15,0.1,0.3 d =30 20 10 X=inv(eye(3)-V)*d 程序运行结果为 160.4563 94.4867 62.1673 x 15 这个结果是合理的，因为实际产出应该比外部需求大得多，以应付内部的消耗。 我们常常说，某某外部需求可以拉动国民经济增长多少个百分点，就是从这样的 模型中得出的。内部需求矩阵 V 要满足一些基本要求，一般各列的列向元素总 和必须小于 1，否则这个部门就将入不敷出而亏损，但我们仍可能求出上述方程 的解。 当所有的列向量都出现列向元素总和大于 1 的情况时， 解 x 中会出现负值， 因而是庸解. 16 情报检索模型 情报检索模型 假如数据库中包括了n个文件，而搜索所用的关键词有m个。如果关键词按字 母顺序排列，我们就可以把数据库表示为 nm 的矩阵A。 每个文件用矩阵的列表示。A的第 j 列的第一个元素是一个数，它表示第一个 关键词出现的相对频率， 第二个元素表示第二个关键词出现的相对频率， 依 此类推。 用于搜索的关键词清单用 n R 空间的向量X表示。 如果关键词清单中第i 个关键词在搜索行中出现，则X的第i个元素就赋值1，否则就赋值0。为了进行 搜索，只要把 T A 乘以X。 举例来说，假如我们的数据库包含有以下的书名：B1：应用 高等代数；B2： 初等高等代数；B3：初等高等代数及其应用；B