矩阵及其应用

矩阵及其应用内容•线性方程组•矩阵运算•矩阵的初等变换•线性空间及线性变换•矩阵的特征值和特征向量•广义逆矩阵nmnmmmnnnnxaxaxayxaxaxayxaxaxay.....................................................22112222121212121111线性方程组矩阵•因为线性方程组的解只与系数有关，而与变量的名称无关，所以我们可以把无关的因素去掉，把全体系数排成一个长方形的表：mnmmnnaaaaaaaaa.....................212222111211矩阵•这种表被称为矩阵（对于上述方程组来说，被称为方程组的系数矩阵），通常用符号A={aij}来表示，为了运算时方便，通常用一个大写字母来表示。数aij被称为矩阵的元素。矩阵的几种比较重要的特殊情形有：由一列数组成的矩阵，叫做列向量；由一行数组成的矩阵，叫做行向量；行数和列数相等的矩阵，叫做方阵。矩阵运算•矩阵加法•矩阵乘法矩阵加法nmnmmnnnmnmmnnxbxbzxbxbxaxayxaxay.......................................z.......................................11111111111111设有如下两个方程组：和矩阵加法nmnmnmmmmnnnxbaxbazyxbaxbazy)(...)()(................................................................)(...)()(111111111111那么：矩阵加法•由新的方程组所得到的矩阵，自然可以看做原来两个方程组的矩阵的和。mnmnmnmnmnmnmmnnbbbbaaaababababa.............................................1111111111111111数乘矩阵mnmnmnmncacacacaaaaac..............................11111111类似地，矩阵与数c相乘定义为cy1,...,cym的系数所对应的矩阵：矩阵乘法nmnmmnnmkmkkmmxbxbyxbxbyyayazyayaz..............................................................................11111111111111设有如下两个方程组：和矩阵乘法•将第二个方程组带入到第一个方程组中，得到z1,...,zk的通过x1,...,xn表示的方程组。nknkknnxcxczxcxcz.....................................1111111矩阵乘法mnmnkmkmknknbbbbaaaacccc.............................................111111111111通常把z关于x的方程组的系数矩阵称为z关于y的方程组的系数矩阵与y关于x的系数矩阵的乘积：矩阵乘法的计算方法•两个矩阵乘积中第i行第j列的元素等于第一个因子的第i行诸元素与第二个因子的第j列诸对应元素乘积之和。•计算矩阵乘法的时间复杂度O(kmn)，方阵相乘的复杂度O(n3)。矩阵运算的条件•加法运算只对具有同样行数和同样列数的两个矩阵有意义。得到的也是一个具有相同行数和列数的矩阵。•乘法运算只对第一个矩阵的列数等于第二个矩阵的行数时有意义，得到的是一个行数与第一个矩阵相同，列数与第二个矩阵相同的矩阵。矩阵运算的基本性质•根据矩阵的运算规则可以得到矩阵的如下运算性质：–矩阵加法满足交换律和结合律。–矩阵加法与数乘运算满足分配律。–矩阵乘法满足结合律（一般不满足交换律）。–矩阵加法与数乘满足分配律。–矩阵加法与矩阵乘法满足分配率单位阵•线性方程组y1=x1+0x2+...+0xny2=0x1+x2+...+0xn......yn=0x1+0x2+...+xn•的系数矩阵被称为单位阵，通常用大写字母E来表示。单位阵•又矩阵乘法的定义可知，对于任意的方阵A，都满足：AE=EA=A。方阵的乘法逆元•给定n阶方阵A，如果存在一个n阶方阵B，满足：AB=BA=E，那么我们把矩阵B称为矩阵A的乘法逆元，简称为矩阵A的逆，记作：A-1。线性方程组•根据矩阵乘法的定义，第三页中的线性方程组可以表示成：•Ax=y•其中A是第五页中的系数矩阵，x是列向量[x1,x2,...,xn]，y是列向量[y1,y2,...,ym]。•当n=m时，A是n阶方阵，如果A可逆，那么：•x=A-1y方阵的幂•已知n阶方阵A和正整数m，计算Am。其中n不超过50，m不超过1000000。方阵的幂（二）•已知n阶方阵A和正整数m，计算A1+A2+...+Am。其中n不超过50，m不超过1000000。路径计数•给定一个有向图，问从A点恰好经过k步（允许多次经过同一条边）走到B点的方案总数。图中顶点数不超过50，边数不超过1000000。线性递推式）不超过，不超过的值。（，计算数整是常数。对于任给的正其中的值和线性递推关系已知100000050,...,,,,...,...,,21221121mnxmaaankxaxaxaxxxxmnnknkkkn细菌•N个培养皿排成一个圈，每个里面都有一些细菌。培养皿逆时针编号为0,1,2,...,N-1，第i个培养皿里有bi个细菌。细菌不停地活动着，他们可能会进行6种动作：•diei0：表示第i个培养皿里的细菌都死亡。•reproduceik：表示第i个培养皿里的每个细菌分裂成k个。•copyij：表示把第j个培养皿里的所有细菌复制到第i个培养皿。•teleportij：表示把第j个培养皿里的所有细菌转移到第i个培养皿。•swapij：表示交换第i个培养皿和第j个培养皿的细菌。•go-round00：表示每个培养皿的细菌都同时转移到它逆时针的下一个培养皿。细菌•一旦某个培养皿里有超过k个细菌，每k个细菌就会合在一起进化成一个高级组织而脱离培养皿，这些细菌重复着执行M（20）条指令，问在执行了T条指令之后，每个培养皿里各有多少个细菌？已知开始的时候每个培养皿恰好有一个细菌。蜂窝机•一个n,m蜂窝机是指由n个格子围成的圈，每个格子中有一个大于等于0且小于m的整数。一个格子的d-environment是指距离这个格子不超过d的所有格子组成的集合。一个d-step是指把每个格子中的数更改为它的d-environment中的所有数之和并对m模的结果。•给出一个n,m蜂窝机中每个格子的初始值，问经过k次d-step后蜂窝机的每个格子中的值是多少？蜂窝机下图中是一个经过1次1-step变换的5,3蜂窝机：矩阵的初等变换•矩阵的初等行变换：–交换矩阵的两行；–用非零常数c乘以矩阵的某一行；–用常数c乘以矩阵的某一行再加到另一行上。•矩阵的初等列变换：–交换矩阵的两行；–用非零常数c乘以矩阵的某一行；–用常数c乘以矩阵的某一行再加到另一行上。矩阵的初等变换•矩阵的初等变换是可逆的。•对矩阵进行若干次初等行变换等价于用一个初等矩阵去左乘这个矩阵。对矩阵进行若干次初等行变换等价于用一个初等矩阵去左乘这个矩阵。•如果矩阵A经过一系列初等变换变成矩阵B，那么存在可逆矩阵P,Q使得B=PAQ。矩阵的初等变换•计算矩阵的秩•计算方阵的逆矩阵•解线性方程组高斯消元nnnnnnnnnnnnnnnnnbaaabaaabaaabxaxaxabxaxaxabxaxaxa.............................................................................2122222111121122112222212111212111已知线性方程组：写出它的增广矩阵：高斯消元nnnnkkknkknbaabaabaaa.......................................111211第k次消元前：高斯消元•第k次消元：–找到最大的aik，其中k≤i≤n。交换矩阵的第i行与第k行。（为什么这样做？）–将矩阵第k行下面的每一行（假设是第j行）减去第k行的ajk/akk倍。高斯消元nnnnnbabaabaaa...............2222111211最后得到矩阵：回带即可得到方程组的解。高斯消元•方程组无解的情况：在消元过程中，某一行的系数全变为0，而常数项不为0。•方程组有无穷多组解的情况：在消元过程中，某一行的系数和常数项全变为0。开关游戏•有n×m盏灯排成一个矩形，如果要手动改变其中一盏灯的状态（开→关或关→开），那么这盏灯周围的四盏（如果在边上是三盏，角上是两盏）灯的状态也会同时被自动改变。现给出每盏灯的初始状态和目标状态，问需要手动改变那些灯的状态，才能达到目标。开关游戏线性空间•设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。线性空间的例子•例一：n维实向量是实数域R上的一个线性空间，加法运算用向量加法来定义，数乘运算用向量的数乘运算来定义。•例二：R[a,b]表示闭区间[a,b]上的实值连续函数的全体组成的集合，那么按照函数的加法与数乘定义其上的线性运算，构成一个实数域R上的线性空间。线性空间的子空间•设X是线性空间，Y是X的一个非空子集。若对于任意x,y∈Y，有x+y∈Y，ax∈Y则称Y为线性空间X的子空间。线性无关与线性相关•设X是线性空间，x1,...,xn∈X，若关系式a1x1+a2x2+...+anxn=0（其中ai∈K）仅当a1=a2=...=an=0时成立，则称集合{x1,...,xn}是线性无关的。否则，称为是线性相关的。线性空间的维数•设X是线性空间，若存在一个正整数n，满足：–1.X包含一个由n个元素组成的线性无关集，–2.任何多于n个元素组成的集合都是线性相关的。•则称此正整数n为线性空间X的维数，记为dimX=n。•当X={0}时，记dimX=0。若X的维数为正整数n或0时，则称X是有限维的。若X不是有限维的，则称X是无限维的，这时记为dimX=∞。线性空间的基•设X是线性空间，B是X的子集。若集合B是线性无关的，且对于任意x∈X，存在x1,...,xn∈B以及a1,...,an∈K，使得x=a1x1+...+anxn，则称B为X的一组基（或Hamel基）。线性算子与线性变换•设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为线性变换。•在一组给定的基下，线性变换可以用一个矩阵来表示。方阵的行列式•方阵的行列式的值是所有取自不同行不同列的元素的乘积之代数和，积的符号是正是负决定于要使各个乘数的列的指标顺序恢复到自然顺序所需的换位次数是偶数还是奇数。也可以这样解释：行列式是矩阵的所有不同行且