数学基础-线性代数

阅读量：5103 次

发布时间：2019-06-13

本文共 6804 字，大约阅读时间需要 22 分钟。

矩阵

基本概念

一个 $ n \times m $ 的矩阵是 $ n $ 行 $ m $ 列的举行整列,一般由数组成,下面是一个 $ 2 \times 3 $ 的矩阵. \[ \begin{pmatrix}1&2&3\\4&5&6 \end{pmatrix} \]

单位矩阵 \[ I = \begin{pmatrix} 1 & \cdots & 0\\ \vdots & \ddots &\vdots\\ 0 & \cdots &1\end{pmatrix} \] ,也就是对角线上为1,其他都为0的矩阵.

基本运算

矩阵加法

每行每列各个数各自相加

矩阵乘法

设 $ A $ 是 $ n \times m $ 的矩阵, $ B $ 是 $ m \times p $ 的矩阵,他们的乘积 $ C $ 是一个 $ n \times m $ 的矩阵, 其中

\[ C_{i,j} = \sum_{k=1}^{m}A_{i,k} \times B_{k,j} \]

矩阵的幂

\[ A^0=I \]

\[ A^n=A^{n-1} \times A(n > 0) \]

矩阵的转置

$ n \times m $ 的矩阵 $ A $ 的转置 $ A^T $ 是个 $ m \times n $ 的矩阵, 可以通过 $ A $ 交换行列得到.

矩阵的逆

只有 $ n \times n $ 的可能存在逆, 矩阵 $ A $ 的逆 $ B $ 满足

\[ A \times B = B \times A = I \]

如果 $ B $ 存在,则 $ B $ 是唯一的,一般记做 $ A^{-1} $

性质

矩阵惩罚满足分配率,结合律,不一定满足交换律

矩阵假发满足交换律和结合率

算法

矩阵满足结合律,所以在求矩阵的幂的时候可以使用快速幂加速

行列式

基本概念

行列式是一个定义域为 $ n \times n $ 的矩阵, 值域为一个标量的函数, 通常记为 $ det(A) $

行列式也可以表示为 $ n $ 维广义欧几里得空间中的有向体积.

一个 $ n \times n $ 的行列式定义为 \[ det(A) = \sum_{\sigma \in S_n}(-1)^{n(\sigma)}\prod_{i=1}^na_{i,\sigma(i)} \]

其中 $ S_n $ 表示集合 $ {1,2,3 \cdots, n} $ 上置换的全体, $ n(\sigma) $ 是对一个置换中逆序对的个数,逆序对的定义为满足 $ 1 \le i < j \le n $ 且 $ \sigma(i) > \sigma(j) $ 的 $ (i,j) $

性质

若矩阵中一行或者一列为0,那么该行列式的值为0

若矩阵中有一行有公因子k, 那么可以提出k, 使得 $ D=kD_1 $

若矩阵中有一行可以拆分成两个数之和,那么该行列式可以拆分成两个行列式相加(剩余的行和列不发生改变)

交换矩阵的两行,行列式取反

将一行的 $ k $ 倍加到另一行上,行列式不变

转置,行列式不变

有上述性质可以得到,如果该矩阵是上三角或者下三角矩阵时,行列式的值等于对角线的乘积

解线性方程组

基本概念

解线性方程组即求解方程组

\[ \begin{cases} a_{1,1}x_1 + a_{1,2}x_2 + \cdots + a_{1,n}x_n = b_1 \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ a_{m,1}x_1 + a_{m,2}x_2 + \cdots + a_{m,n}x_n = b_m\end{cases} \]

也可以表示为 $ Ax = B $ , 其中 $ A $ 是 $ m \times n $ 的矩阵, $ x $ 是 $ n $ 维列向量, $ b $ 是 $ m $ 维列向量, 即

\[ \begin{pmatrix} a_{1,1} &\cdots &a_{1,n} \\ \vdots& \ddots &\vdots \\ a_{m,1} &\cdots &a_{m,n} \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix}b1 \\ \vdots \\ b_m \end{pmatrix} \]

算法

高斯消元(Gaussian elimination)

矩阵的初等变换:

互换矩阵两行(列),用非零常熟乘某一行(列),某行(列)的 $ k $ 倍加到矩阵的另一行(列)(避免精度损失)

则上述方程组可以用一个增光矩阵表示.

\[ \begin{pmatrix} a_{1,1} & \cdots & a_{1,n} & b_1 \\ \vdots & \ddots & \vdots & \vdots \\ a_{m,1} & \cdots & a_{m,n} & b_m \\ \end{pmatrix} \]

于是我们只要进行初等变换使得上述矩阵称为上三角矩阵就行了.

克莱姆法则(Cramer rule)

当 $ A $ 为 $ n \times n $ 的矩阵时,可用Cramer rule进行求解, 方程的解为:

\[ x_i = \frac{D_i}{D} \]

其中 $ D $ 是 $ A $ 的行列式, $ D_i $ 是将 $ A $ 中第 $ i $ 列替换成 $ b $ 后得到的矩阵的行列式.

例如上述列子中,求解 $ x_2 $ , 已知: \[ D = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 2 \\ 1 & 2 & 3 \end{pmatrix} = -1, D\begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 2 \\ 1 & 6 & 3 \end{pmatrix} = -3 \]

立刻就可以得到: \[ x_2 = \frac{D_2}{D} = 3 \]

用途

求解可逆矩阵的逆矩阵:

对于一个 $ n \times n $ 的非奇异矩阵, 在矩阵右侧补上一个 $ n \times n $ 的单位矩阵, 对于这个 $ n \times (2n) $ 的矩阵进行高斯消元, 使得这个矩阵左侧变成一个 $ n \times n $ 的单位矩阵.这是右侧的 $ n \times n $ 的矩阵就是原矩阵的逆矩阵

同模方程组也可使用高斯消元, 在除法时用乘逆元代替. 偶遇只有在模素数时, 非零数的逆元才唯一, 所以, 素数模才能保证有唯一解

求解行列式的值.消成上三角矩阵就OK.

Expand

由于在消元过程中需要用到除法, 所以会有浮点运算精度问题, 不同的消元顺序可能会导致较大的差异, 推荐使用绝对值较大的主元进行消元, 能达到比较好的效果

可以使用辗转相除法进行消元,这样做可以保证稀疏为整数.

多项式

基本概念

给定一个数域 $ R $ , 变量 $ x $ , 一元多项式的形式是:

\[ f(x) = \sum_{i=0}^na_ix^i \]

其中 $ a_i \in R $ , 并且 $ a_n \not= 0 $

多项式中次数最高的项称为首项,首项的系数等于1的多项式称作首一多项式

多项式加法: 对应次数系数做加法.例如:

\[ f(x) + g(x) = \sum_{i=0}^n(a_i + b_i)x^i \]

多项式乘法: 两个多项式的每一项都相乘, 例如:

\[ f(x) \bullet g(x) = \sum_{i=0}^n\sum_{j=0}^na_ib_jx^{i+j} \]

性质

$ (1 + x)^n = \sum_{i=0}^n \binom{n}{i}x^i $

$ n $ 个点可以唯一确定一个 $ n $ 次多项式

一个 $ n $ 次多项式有 $ n $ 个负数根

算法

用牛顿迭代法求解方程的根

选择一个靠近多项式 $ f(x) $ 零点的点 $ x_0 $ 作为迭代初值, 计算 $ f(x_0) $ 和 $ \mathop{

{f}'}(x_0) $ , 解方程:

\[ x \cdot \mathop{

{f}'}(x_0) + f(x_0) - x_0 \cdot \mathop{

{f}'}(x_0) = 0 \] 得到解 $ x_1 $ 如此反复迭代,就可以求出多项式的一个根.

复数

基本概念

复数是由实部和虚部组成的数,通常有两种表示方法, $ z=a+bi $ , $ a $ 和 $ b $ 都是实数, $ i $ 是虚单位根,满足 $ i^2=-1 $ , $ |z|=sqrt(x^2+y^2) $ 表示复数的模长.复数也可以表示为 $ z = Re^{i\varphi}=R(cos(\varphi)+isin(\varphi)) $ , 其中 $ R=|z| $ , $ e^{i\varphi}=cos(\varphi)+isin(\varphi) $

复数的运算满足结合律,分配率和交换率

复数可以表示为实数平面上的一个向量, 复数的乘法可以理解为两个向量的角度相加,模长相乘, 因此用复数的乘法处理向量的旋转非常的方便.具体来说,如果一个向量 $ (x,y) $ 旋转 $ \varphi $ , 可以视为两个复数, $ x+yi $ 乘以 $ cos(\varphi) + sin(\varphi)i $ ,等于 $ xcos(\varphi) + ysin(\varphi) + (ycos(\varphi) + xsin(\varphi))i $

群

基本概念

群

在数学中,群是一种代数结构, 由一个集合 $ S $ 与一个二元运算 $ \cdot $ 组成, 要成为群, 还要满足一些条件, 这些条件被称为"群公理", 即封闭性,结合律,单位元和逆元

封闭性即 $ \forall a,b \in S, a \cdot b \in S $

结合律即 $ \forall a,b,c \in S, (a \cdot b) \cdot c = a \cdot (b \cdot c) $

单位元即有一个元素 $ e $ , $ \forall a \in S, e \cdot a = a \cdot e = a $ (在群 $ G $ 中,常用1表示单位元)

逆元即 $ \forall a \in S, \exists b \in S, a \cdot b = b \cdot a = e $ , 记 $ b = a^{-1} $

值得注意的是, 二元运算符 $ \cdot $ 仅表示抽象的运算符号, 在不同的群中解释不同. 在不引起歧义的地方常将其省略.

例如: 整数加法群 $ (Z,+,0) $ , 是由整数 $ Z $ 和整数加法运算+组成的.其单元元是 $ 0 $ , 封闭性: $ \forall a, b \in Z, a + b \in Z $ ; 结合律: $ \forall a,b,c \in Z, (a + b) + c = a + (b + c) $ , 逆元: $ \forall a \in Z, a^{-1} = -a $

子群

设 $ G $ 是群, $ \oslash \not= H \subseteqq G $ , 若 $ H $ 具有封闭性,单位元,逆元,则 $ H $ 是 $ G $ 的一个子群. 作为群公理之一的结合律, 因为 $ H $ 继承了 $ G $ 的运算,所以自然成立,因此,子群也是群.(例如 $ (bZ,+,0) $ 就是 $ (Z,+,0) $ 的子群)

元素的价

在群 $ G $ 中,定义元素 $ g $ 的价 $ o(g) $ , 为使 $ g^n=1_G $ 成立的最小自然数 $ n $ ; 如果此自然数不存在, 则记做 $ o(g) = \infty $ .

循环群

设 $ g $ 是群 $ G $ 中一个取定的元素, 若群 $ G $ 的任意一个元素 $ a $ 可以写成 $ a = g^n, n \in Z $ 的形式, 则称 $ G $ 循环群,称 $ g $ 为群 $ G $ 的一个生成元, 可写成 $ G = < g > $

交换群

具有交换性的群称为交换群. 交换性: $ \forall a, b \in G, ab = ba $

整数加法群是交换群,因为整数加法满足交换律, 一般线性群 $ GL(n) $ 由所有 $ n \times n $ 的可逆矩阵和矩阵乘法组成, 它不是交换群, 因为矩阵乘法不满足交换律.

置换群

设 $ A $ 是一个非空集合, $ A^A $ 是 $ A $ 到 $ A $ 上的所有的置换的集合, 在 $ A^A $ 上的所有的置换的集合,在 $ A^A $ 上定义二元运算符为映射的复合, 因为映射的符合满足结合律, 记 $ S $ 为 $ A $ 上所有可逆映射的集合, 则 $ S $ 关于映射的复合构成群.

当 $ A $ 是有限集合时, 可设 $ A = {1,2, \cdots, n} $ , 则 $ A $ 上的可逆变换可表示为 \[ f = \begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\i_1 & i_2 & \cdots & i_{n-1} & i_n \end{pmatrix} \]

其中 $ i_1,i_2,\cdots $ 是一个 $ n $ -的排列, $ i_j $ 表示将 $ j $ 位置上的元素换到了 $ i_j $ 位置.这样一个变换称作 $ n $ 次置换, 形成的群称作 $ n $ 次置换群. 所有的 $ n $ 次置换形成的群记做 $ S_n $ ,例如 $ S_3=\left{ \begin{pmatrix} 1&2&3 \1 &2 &3 \end{pmatrix}\begin{pmatrix} 1&2&3 \1 &3 &2 \end{pmatrix}\begin{pmatrix} 1&2&3 \2 &1 &3 \end{pmatrix}\begin{pmatrix} 1&2&3 \2 &3 &1 \end{pmatrix}\begin{pmatrix} 1&2&3 \3 &1 &2 \end{pmatrix}\begin{pmatrix} 1&2&3 \3 &2 &1 \end{pmatrix} \right} $

还有一种表示置换的方法,若 $ (i_1,i_2,\cdots,i_k) $ 满足 $ f(i_j)=i_{j+1} $ , 则称 $ (i_1,i_2,\cdots,i_k) $ 为一个循环节, 显然, 一个置换可以拆成若干个循环节,所以可以将置换用循环节表示.

例如 $ S_3 $ 在这种情况下可以表示为 $ S_3={(1)(2)(3),(1)(2,3),(1,2)(3),(1,2,3),(1,3,2),(1,3)(2)} $