矩阵及其应用

关于矩阵及其应用内容线性方程组矩阵运算矩阵的初等变换线性空间及线性变换矩阵的特征值和特征向量广义逆矩阵第2页,共57页，2024年2月25日，星期天线性方程组第3页,共57页，2024年2月25日，星期天矩阵因为线性方程组的解只与系数有关，而与变量的名称无关，所以我们可以把无关的因素去掉，把全体系数排成一个长方形的表：第4页,共57页，2024年2月25日，星期天矩阵这种表被称为矩阵（对于上述方程组来说，被称为方程组的系数矩阵），通常用符号A={aij}来表示，为了运算时方便，通常用一个大写字母来表示。数aij被称为矩阵的元素。矩阵的几种比较重要的特殊情形有：由一列数组成的矩阵，叫做列向量；由一行数组成的矩阵，叫做行向量；行数和列数相等的矩阵，叫做方阵。第5页,共57页，2024年2月25日，星期天矩阵运算矩阵加法矩阵乘法第6页,共57页，2024年2月25日，星期天矩阵加法设有如下两个方程组：和第7页,共57页，2024年2月25日，星期天矩阵加法第8页,共57页，2024年2月25日，星期天矩阵加法由新的方程组所得到的矩阵，自然可以看做原来两个方程组的矩阵的和。第9页,共57页，2024年2月25日，星期天数乘矩阵类似地，矩阵与数c相乘定义为cy1,...,cym的系数所对应的矩阵：第10页,共57页，2024年2月25日，星期天矩阵乘法设有如下两个方程组：和第11页,共57页，2024年2月25日，星期天矩阵乘法将第二个方程组带入到第一个方程组中，得到z1,...,zk的通过x1,...,xn表示的方程组。第12页,共57页，2024年2月25日，星期天矩阵乘法通常把z关于x的方程组的系数矩阵称为z关于y的方程组的系数矩阵与y关于x的系数矩阵的乘积：第13页,共57页，2024年2月25日，星期天矩阵乘法的计算方法两个矩阵乘积中第i行第j列的元素等于第一个因子的第i行诸元素与第二个因子的第j列诸对应元素乘积之和。计算矩阵乘法的时间复杂度O(kmn)，方阵相乘的复杂度O(n3)。第14页,共57页，2024年2月25日，星期天矩阵运算的条件加法运算只对具有同样行数和同样列数的两个矩阵有意义。得到的也是一个具有相同行数和列数的矩阵。乘法运算只对第一个矩阵的列数等于第二个矩阵的行数时有意义，得到的是一个行数与第一个矩阵相同，列数与第二个矩阵相同的矩阵。第15页,共57页，2024年2月25日，星期天矩阵运算的基本性质根据矩阵的运算规则可以得到矩阵的如下运算性质：矩阵加法满足交换律和结合律。矩阵加法与数乘运算满足分配律。矩阵乘法满足结合律（一般不满足交换律）。矩阵加法与数乘满足分配律。矩阵加法与矩阵乘法满足分配率第16页,共57页，2024年2月25日，星期天单位阵线性方程组

y1=x1+0x2+...+0xny2

=0x1+x2+...+0xn......yn=0x1+0x2+...+xn的系数矩阵被称为单位阵，通常用大写字母E来表示。第17页,共57页，2024年2月25日，星期天单位阵又矩阵乘法的定义可知，对于任意的方阵A，都满足：AE=EA=A。第18页,共57页，2024年2月25日，星期天方阵的乘法逆元给定n阶方阵A，如果存在一个n阶方阵B，满足：AB=BA=E，那么我们把矩阵B称为矩阵A的乘法逆元，简称为矩阵A的逆，记作：A-1。第19页,共57页，2024年2月25日，星期天线性方程组根据矩阵乘法的定义，第三页中的线性方程组可以表示成：Ax=y其中A是第五页中的系数矩阵，x是列向量[x1,x2,...,xn]，y是列向量[y1,y2,...,ym]。当n=m时，A是n阶方阵，如果A可逆，那么：x=A-1y第20页,共57页，2024年2月25日，星期天方阵的幂已知n阶方阵A和正整数m，计算Am。其中n不超过50，m不超过1000000。第21页,共57页，2024年2月25日，星期天方阵的幂（二）已知n阶方阵A和正整数m，计算A1+A2+...+Am。其中n不超过50，m不超过1000000。第22页,共57页，2024年2月25日，星期天路径计数给定一个有向图，问从A点恰好经过k步（允许多次经过同一条边）走到B点的方案总数。图中顶点数不超过50，边数不超过1000000。第23页,共57页，2024年2月25日，星期天线性递推式第24页,共57页，2024年2月25日，星期天细菌N个培养皿排成一个圈，每个里面都有一些细菌。培养皿逆时针编号为0,1,2,...,N-1，第i个培养皿里有bi个细菌。细菌不停地活动着，他们可能会进行6种动作：diei0：表示第i个培养皿里的细菌都死亡。reproduceik：表示第i个培养皿里的每个细菌分裂成k个。copyij：表示把第j个培养皿里的所有细菌复制到第i个培养皿。teleportij：表示把第j个培养皿里的所有细菌转移到第i个培养皿。swapij：表示交换第i个培养皿和第j个培养皿的细菌。go-round

00：表示每个培养皿的细菌都同时转移到它逆时针的下一个培养皿。第25页,共57页，2024年2月25日，星期天细菌一旦某个培养皿里有超过k个细菌，每k个细菌就会合在一起进化成一个高级组织而脱离培养皿，这些细菌重复着执行M（<20）条指令，问在执行了T条指令之后，每个培养皿里各有多少个细菌？已知开始的时候每个培养皿恰好有一个细菌。第26页,共57页，2024年2月25日，星期天蜂窝机一个n,m蜂窝机是指由n个格子围成的圈，每个格子中有一个大于等于0且小于m的整数。一个格子的d-environment是指距离这个格子不超过d的所有格子组成的集合。一个d-step是指把每个格子中的数更改为它的d-environment中的所有数之和并对m模的结果。给出一个n,m蜂窝机中每个格子的初始值，问经过k次d-step后蜂窝机的每个格子中的值是多少？第27页,共57页，2024年2月25日，星期天蜂窝机下图中是一个经过1次1-step变换的5,3蜂窝机：第28页,共57页，2024年2月25日，星期天矩阵的初等变换矩阵的初等行变换：交换矩阵的两行；用非零常数c乘以矩阵的某一行；用常数c乘以矩阵的某一行再加到另一行上。矩阵的初等列变换：交换矩阵的两行；用非零常数c乘以矩阵的某一行；用常数c乘以矩阵的某一行再加到另一行上。第29页,共57页，2024年2月25日，星期天矩阵的初等变换矩阵的初等变换是可逆的。对矩阵进行若干次初等行变换等价于用一个初等矩阵去左乘这个矩阵。对矩阵进行若干次初等行变换等价于用一个初等矩阵去左乘这个矩阵。如果矩阵A经过一系列初等变换变成矩阵B，那么存在可逆矩阵P,Q使得B=PAQ。第30页,共57页，2024年2月25日，星期天矩阵的初等变换计算矩阵的秩计算方阵的逆矩阵解线性方程组第31页,共57页，2024年2月25日，星期天高斯消元已知线性方程组：写出它的增广矩阵：第32页,共57页，2024年2月25日，星期天高斯消元第k次消元前：第33页,共57页，2024年2月25日，星期天高斯消元第k次消元：找到最大的aik，其中k

≤i≤n。交换矩阵的第i行与第k行。（为什么这样做？）将矩阵第k行下面的每一行（假设是第j行）减去第k行的ajk/akk倍。第34页,共57页，2024年2月25日，星期天高斯消元最后得到矩阵：回带即可得到方程组的解。第35页,共57页，2024年2月25日，星期天高斯消元方程组无解的情况：在消元过程中，某一行的系数全变为0，而常数项不为0。方程组有无穷多组解的情况：在消元过程中，某一行的系数和常数项全变为0。第36页,共57页，2024年2月25日，星期天开关游戏有n×m盏灯排成一个矩形，如果要手动改变其中一盏灯的状态（开→关或关→开），那么这盏灯周围的四盏（如果在边上是三盏，角上是两盏）灯的状态也会同时被自动改变。现给出每盏灯的初始状态和目标状态，问需要手动改变那些灯的状态，才能达到目标。第37页,共57页，2024年2月25日，星期天开关游戏第38页,共57页，2024年2月25日，星期天线性空间设X是一个非空集合，K是数域。若存在一个X上的二元映射（称为加法运算，记为“+”），使得对任意的x,y∈X，都有x+y∈X，且满足性质：交换律：x+y=y+x；结合律：(x+y)+z=x+(y+z)；零元存在：0+x=x；负元存在：x+(-x)=0；结合律：a∙(b∙x)=(a∙b)∙x；单位元：1∙x=x；数乘对加法的分配率：a∙(x+y)=a∙x+a∙y；分配率：(a+b)∙x=a∙x+b∙x。第39页,共57页，2024年2月25日，星期天线性空间的例子例一：n维实向量是实数域R上的一个线性空间，加法运算用向量加法来定义，数乘运算用向量的数乘运算来定义。例二：R[a,b]表示闭区间[a,b]上的实值连续函数的全体组成的集合，那么按照函数的加法与数乘定义其上的线性运算，构成一个实数域R上的线性空间。第40页,共57页，2024年2月25日，星期天线性空间的子空间设X是线性空间，Y是X的一个非空子集。若对于任意x,y∈Y，有x+y∈Y，ax∈Y则称Y为线性空间X的子空间。第41页,共57页，2024年2月25日，星期天线性无关与线性相关设X是线性空间，x1,...,xn∈X，若关系式a1x1+a2x2+...+anxn=0（其中ai∈K）仅当a1=a2=...=an=0时成立，则称集合{x1,...,xn}是线性无关的。否则，称为是线性相关的。第42页,共57页，2024年2月25日，星期天线性空间的维数设X是线性空间，若存在一个正整数n，满足：1.X包含一个由n个元素组成的线性无关集，2.任何多于n个元素组成的集合都是线性相关的。则称此正整数n为线性空间X的维数，记为dimX=n。当X={0}时，记dimX=0。若X的维数为正整数n或0时，则称X是有限维的。若X不是有限维的，则称X是无限维的，这时记为dimX=∞。第43页,共57页，2024年2月25日，星期天线性空间的基设X是线性空间，B是X的子集。若集合B是线性无关的，且对于任意x∈X，存在x1,...,xn∈B以及a1,...,an∈K，使得x=a1x1+...+anxn，则称B为X的一组基（或Hamel基）。第44页,共57页，2024年2月25日，星期天线性算子与线性变换设X和Y是同一数域K上的两个线性空间，T是X到Y的映射。若对于任意x,y∈X和a∈K，有T(x+y)=Tx+Ty，T(ax)=aTx，则称T为线性空间X到线性空间Y的线性算子。当X与Y是同一个线性空间时，也可以称T为线性变换。在一组给定的基下，线性变换可以用一个矩阵来表示。第45页,共57页，2024年2月25日，星期天方阵的行列式方阵的行列式的值是所有取自不同行不同列的元素的乘积之代数和，积的符号是正是负决定于要使各个乘数的列的指标顺序恢复到自然顺序所需的换位次数是偶数还是奇数。也可以这样解释：行列式是矩阵的所有不同行且不同列的元素之积的代数和，和式中每一项的符号由积的各元素的行指标与列指标的逆序数之和决定：若逆序数之和为偶数，则该项为正；若逆序数之和为奇数，则该项为负。第46页,共57页，2024年2月25日，星期天逆序数在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。第47页,共57页，2024年2月25日，星期天行列式的基本性质某一行（列）元素全为0，则此行列式的值为0。某一行（列）有公因子k，则可以提出k。某一行（列）的每个元素是两数之和，则此行列式可拆分为两个相加的行列式。行列式中的两行（列）互换，改变行列式正负符号。将一行（列）的k倍加进另一行（列）里，行列式的值不变。在行列式中，有两行（列）对应成比例或相同，则此行列式的值为0。将行列式的行列互换，行列式的值不变。第48页,共57页，2024年2月25日，星期天克莱姆法则设n个未知数n个方程组成的方程组：a11x1+a12x2+...+a1nxn=b1a21x1+a22x2+...+a2nxn=b2...an1x1+an2x2+...+annxn=bn当它的系数行列式D不为0时，方程组的解为xi=Di/D，其中Di是把D中的第i列用