矩阵理论引言

中国石油大学（华东）理学院（刘新海）,矩阵理论,MatrixTheory,一、简介,矩阵理论是一门重要的数学理论，除了在数值分析、最优化方法、微分方程稳定性理论、数学模型等数学分支上有极其重要的应用，还在计算机科学、无线电技术、系统工程、自动控制及卫星通讯等尖端科学领域中有重要用途。,矩阵理论是描述、分析、解决线性系统的有力工具，“有力”主要表现在这种工具的普适性和简便性。,二、主要内容,1、线性空间与线性变换,2、内积空间,3、矩阵的标准型与若干分解形式,4、矩阵函数及其应用,5、特征值的估计与广义逆矩阵,三、学习方法,学习基础知识专业课程中进一步认知科学研究中应用,例1层析成像系统的原理与模型,四、引例,系统背景：医学上绘制计算机断面图的基本问题：如何利用由位于同一截面，但方向不同的大量射线所搜集的信息，恢复该截面人体组织的图像，并将其显示在终端屏幕上。层析成像系统的英文名称是Computer-Aided-Tomograpgy-Scanner，缩写为CAT-Scanner，就是口语中的CT-扫描一词的来源。世界上第一个这样的医用商业系统1971年由一家英国公司制造，其发明者豪斯菲尔德与科马克于1979年被授予诺贝尔奖。,系统简介（系统原理）：通常的胸部X-透视，是将平行的X-射线束垂直穿过人体再投影到屏幕上，由于人体各部分对射线吸收能力不同，屏幕上便显示出黑白亮度不同的图形，但这一图形只反映垂直于射线方向上无穷多个平行截面之人体组织的叠加或平均，它不能给出人体组织的空间分布。,X-射线断面图与透视不同，它依据位于探测截面上的数万以至数十万条极细的不同射线，绘制出截面的人体组织结构，它所利用的是射线穿过被测物体后强度的变化，所有射线的初始强度已知，每条射线穿过被测物体后其强度再次被测量，并将结果送入计算机。,X-射线扫描被探测截面的方式有两种，一种为平行方式，一种为扇形方式。在平行模式中，一个X-射线源和一个强度探测器在视域中等间距同步平移，在不同的位置对彼此平行的射线进行多次测量和记录，然后源与探测装置共同旋转一个小的角度，再次进行多次平行测量。最早的系统即采用这一工作方式，源与探测器每次平移测量160条平行射线，然后以1度为间隔，旋转一新的位置，共转180度，从而知此种方式所测量的射线总数为160*180=28800，需时5.5分。以后出现的通用电气公司的CT/T系统使用扇形扫描，所测量的射线总数为184320=1024*180，需时4.6秒。,系统模型（原理与模型）：下面说明计算机绘制断面图的基本原理与数学模型。人体不同组织与器官对X-射线的吸收是能力不同的，即对同样面积或体积的不同组织与器官而言，当入射的X-射线有相同的强度时，穿透后离开的射线则有不同的强度。入射前与穿透后射线强度的比值刻画了不同组织和器官的不同性质，这个比值可称为生物组织或器官的X-射线密度。为确定扫描截面内各个局部的X-射线密度，如下图所示，把视域划分为正方形网格，每个格子称为一个象点。世界上第一台这样的装置有80*80=6400个象点；而通用电气公司的CT/T系统则有320*320=102400个象点。每个象点大约1mm*1mm。,由于每个象点的面积非常小，可以假设在一个象点范围内，组织或器官的性质是均匀的，可以由同一的X-射线密度来刻画。因此，如果能够从所有测量数据中，求得,每个象点的X-射线密度值，然后在显示屏幕相应位置，正比于这一密度，决定图像的辉度水平，那么就可以清楚地显示出生物组织或器官的结构，这就是CT成像的基本原理。,模型建立：,下面首先以一种极为直观的简单方式，依据上述原理，建立数学模型。把所有象点依据某种规则编号，对任意象点j定义其X-射线密度，考虑如下图示的单一象点与多个象点垂直入射情况。,对于单一象点，令,对于多个象点，则,上式右端的量显然是可以测量的：其分子可由同样装置在无受检物体情况下测得，分母则在临床应用时测得。若假设每一条射线均按以上方式给出一个方程，合起来将得到一个以象点射线密度为未知数的非线性方程组，因而求解是非常困难的。,为了克服这一点，将任意象点j的X-射线密度定义为,因为lny是单调函数，不同的yj对应不同的xj，因而以正比于xj的辉度，屏幕上仍然可以显示出不同组织或器官的清晰图像。,令,若假设第i条射线正入射通过编号为i1,i2,in的n个象点，则由上述方法可得方程：,出现在上式左端的量是未知数，右端由扫描测得。如果把视域中所有N个象点的N个未知数都包括进上式，则有下列一般形式的方程组：,由前述CT扫描的工作方式知，并非所有射线都是正入射穿过一系列象点的，此时同一射线在不同象点格子中穿过的长度不同，因而被吸收的强度不同于正入射。此时为使方程更精确，应对方程系数aij加以修正，,以反映每个象点格子中的射线长度对射线强度衰减的影响。确定aij的方式常用的有三种：,（a）象点中心法,（b）中心线长度法,（c）面积法（认为射线有宽度）,不管哪种处理方法，最终导致一个大型代数方程组：,其中M与N分别为总射线束与总格子数，这个方程组的特点是方程个数远远超过未知数个数，且系数矩阵是稀疏的，即其中包含大量零元素（代数重构技术）。,例2希尔密码系统,背景简介：希尔密码是以矩阵变换的方法建立的字母间的对应关系，由LesterS.Hill于1929年提出。密码学（Cryptography：研究秘密信息的编码和译码的学科）的一个重要方面是试图给出一种方法，改变信息的原有形式，使得除了某些特定人员外，其他人难以读懂这一信息的内容。密码学中的信息代码称为密码，尚未转换成密码的文字信息称为明文，由密码表示的信息称为密文，从明文到密文的转换过程称为加密，相反的过程称为解密。显然，加密过程必须遵循某种规则。最早使用密码的是古罗马皇帝朱利叶斯.凯撒，他以字母A对应D,，B对应E等，即以右边第三个字母取代原字母的简单方式作为转换规则。至今仍把保持字母自然顺序的对应规则称为凯撒换字表或凯撒密码。,一般说来，一个密码系统可以抽象地表示如下的五元组：X，Y，E，D，k，其中字母X表示信息明文，Y表示密文，E表示一族加密变换，D表示一族解密变换，而任何特定的一个加密或解密变换由指标k给定，k称为密钥。如凯撒密码中的间隔多少个字母数就是密钥k。,一个密码系统称之为是不可破译的，其含义是说，不存在一种密码分析技术，使得在不知解密规则的情况下，可以该系统的密文解释出明文。对于那些按确定性规则编制且反复使用的密码，原则上来说最终均可破译；然而当破译所需工作量极大，所花费的时间实际上不可能实现，或者大大超过所需要的保密期限时，密码系统就是可以使用的。下面介绍在密码史上有重要地位，由希尔所发明的密码-希尔密码。,希尔密码系统加密原理,前面提到的凯撒密码有一个致命的弱点，即明文中的每一个字母与密文中对应字母有相同的使用频率，因,而当被截获的密文累积到一定数量时，利用所出现符号的统计频率，再利用拼音字母所固有的字母连接特点，就可以进行破译。克服此弱点的一种方法是，将明文中的每n个字母划为一组，然后依照某种规则，按组与n个字母组成的密文相对应。由于变换由字母组决定，因此，明文中出现在不同组合中的同一个字母，在明文中对应的密码是不同的。希尔密码以矩阵变换的方法建立字母间的对应关系，它使得密码学进入以数学方法处理问题的阶段。,在下面的讨论中，无论明文或密文，均假定每一字母对应一个非负整数。一种最自然的对应方式，是令这,一整数为任一字母在字母表中的位置；但有一个例外，即字母z对应数字0而不是26，原因下文自明。ABCDEFGHIJKLMN234567891011121314OPQRSTUVWXYZ15161718192021222324250,为便于叙述，仅考虑希尔密码最简单的形式，即考虑明文字母按先后顺序每两个分为一组的情况。如电文字母总数为奇数，则在最后位置任意补缀一个。为了将每组字母转换为密码，采用如下步骤：,步骤任意选定一2阶方阵，每个矩阵的元素均为整数，设为要求A的行列式det(A)是奇数且不能被13整除，原因后面说明。,步骤将明文中的每个字母对，按照上表列出的对应关系，转换成一个二维向量,步骤根据每个字母对形成的二维整数向量计算一新的二维向量,步骤对的每个分量计算同余：再依据前表，将转化为字母，得到所要的明文。,上述步骤中所涉及的同余概念为：设a是任意一个整数，m是一个正整数，令r是商为整数时a的绝对值除以m的余数，则a对数m的同余定义为,下面举例说明：,设所要转化的英文是：amutiny,info.（有人叛变，速查）。,首先按字母在明文中的顺序，将它们分为二个字母一组：amutinyinfoo，最后一个字母是分组要求添加的。,选定一整数元素矩阵：,明文字母分组序列对应的二维向量集合按顺序是,将以上向量左乘矩阵A：,将以上向量的每个分量对模26取同余：,转换回字母，所得到的密文是：,amihkpqazrss,希尔密码系统解密原理,由上节加密过程不难看出，只要知道了加密时所用矩阵A在mod26意义下的逆，则从密文字母所对应的二维向量q，即可得到明文字母所对应的向量p。因为,现在的问题：是否任意一个矩阵A，在mod26意义下都是可逆的？,为了弄清在mod26意义下A的逆矩阵存在的条件，首先考察最简单的1阶矩阵情况，即是否集合G=0,1,2,25中的每个数都在mod26意义下存在倒数，或者说存在乘法逆元素。确切地说，是否有,事实上，在mod26意义下，对G中的元素a求逆，就是求一个整数x（属于G），使得存在另一整数k（属于G），满足,上式意味着与26有公因子的元素，不存在乘法逆元素。,下面表中是集合G中有乘法逆的元素及其倒数（逆）：,对于任意一个二阶矩阵A，如果不考虑mod26的要求，在实数域内，二阶矩阵A的逆存在的条件是：,由上式知，当矩阵元素为整数时，矩阵的逆（mod26意义下）是否由集合G中的元素来表示，关键在于矩阵的行列式在G中是否存在倒数。从而得到结论：选择矩阵时，要求矩阵的行列式不是偶数，且不含因子13。,将前面的例子解密：,amihkpq