JZTXT

矩阵和线性空间

发布时间 2023-05-25 20:25:10作者: Bloodstalk

矩阵

定义

一个 \(n \times m\) 的矩阵可看作一个 \(n\times m\) 的二维数组。一般用方括号或圆括号表示矩阵。

\[\left( \begin{array}{ccc} a_{11} & a_{12} & \dots & a_{1m}\\ a_{21} & a_{22} & \dots & a_{2m}\\ \vdots \\ a_{n1} & a_{n2} & \dots & a_{nm} \end{array} \right) \]

一些定义

同型矩阵

同型矩阵指的是两个矩阵，如果它们的行数和列数对应相同，那么它们两个就被称为同型矩阵。

方阵

行数等于列数的阵称为方阵。一般所说的「\(n\) 阶矩阵」实际上是 \(n\) 阶方阵。

主对角线

对于方阵 \(A\) ，主对角线就是指 \(A_{i,i}\) 上的元素。

对称矩阵

如果方阵的元素关于主对角线对称，即对于任意的 \(i\) 和 \(j\) ， \(i\) 行 \(j\) 列的元素和 \(j\) 行 \(i\) 列的元素相等，则该矩阵被称为对称矩阵。

对角矩阵

主对角线之外的元素均为 \(0\) 的方阵称为对角矩阵，一般记作：

\[\text{diag}\{\lambda_1,\dots,\lambda_n \} \]

其中 \(\lambda_1,\dots,\lambda_n\) 是主对角线上的元素。

很显然，对角矩阵也是对称矩阵。

单位矩阵

如果对角矩阵的元素均为 \(1\) ，即主对角线上都是 \(1\) ，其余都是 \(0\) 的方阵，称为单位矩阵，记为 \(I\) 。只要能进行矩阵乘法， 任何矩阵乘单位矩阵都等于原矩阵。

三角矩阵

如果方阵主对角线左下方的元素均为 \(0\) ，称为上三角矩阵。如果方阵主对角线右上方的元素均为 \(0\) ，称为下三角矩阵。

运算

加法(减法)

两个矩阵进行加减法运算就是把两个矩阵对应位置上的数相加减，即 \(C = A \pm B \Leftrightarrow \forall i \in [1,n] , j \in [1,m] , C_{i,j} = A_{i,j} \pm B_{i,j}\)

引用子谦
大佬的几张图。

数乘

类似于向量， \(\lambda * A\) 就等效于 \(A\) 中的每个元素都乘以 \(\lambda\) 。

数乘运算中，类似于向量的，有以下运算律：

\((\lambda\mu)A = \lambda(\mu A)\)

\((\lambda+\mu)A = \lambda A + \mu A\)

\(\lambda(A+B) = \lambda A + \lambda B\)

转置

矩阵的转置，就是在矩阵的右上角写上转置 \(T\) 记号， 记为 \(A^T\) ， 表示将矩阵的行与列互换。

对称矩阵转置前后保持不变。

乘法：

重头戏来了

矩阵乘法只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

设 \(A\) 是 \(N \times M\) 的矩阵， \(B\) 为 \(M \times P\) 的矩阵，设 \(C = A \times B\) ，那么 \(C\) 矩阵是 \(N \times P\) 的。

其中 \(C\) 中的第 \(i\) 行第 \(j\) 列元素可以表示为

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

也就是说，在矩阵乘法中，结果 \(C\) 矩阵的第 \(i\) 行第 \(j\) 列的数，就是由矩阵 \(A\) 第 \(i\) 行 \(M\) 个数与矩阵 \(B\) 第 \(j\) 列 \(M\) 个数分别相乘再相加得到的。口诀为左行右列。

矩阵乘法满足以下运算律：

结合律：$A \times B \times C= A \times (B \times C) $

分配律：

\((A + B) \times C = AC + BC\)

\(C \times (A + B) = CA + CB\)

不满足交换律

但有一种特殊情况：\(A \times I = I \times A\) (\(I\) 为单位矩阵)

常数优化

image-20221006141637037

\(i,k,j\)的顺序最优。

因为 \(i,j\) 和 \(i,k\) 都在缓存里，不需要重复查找，所以最优，可以卡常。

用途

  • 在某些题中可以加速递推公式，把一个 \(O(n)\) 的柿子加速到 \(O(\log n)\) 。

    前提是你需要会矩阵快速幂。

  • 高斯消元

矩阵快速幂

矩阵快速幂，顾名思义，就是矩阵套个快速幂。
首先把 \(res\) 定为初始矩阵，那么就把它初始化成单位矩阵 \(I\) ，接着就是快速幂的操作了，然后重载一下乘号就行了。

matrix operator *(matrix &x,matrix &y)
{
	matrix t;
	for(re int i=1;i<=n;i++)
		for(re int k=1;k<=n;k++)
			for(re int j=1;j<=n;j++)
				t.c[i][j] = (t.c[i][j] + x.c[i][k]*y.c[k][j]) % mod;
	return t;
}

il void ksm(int b)
{
	while(b)
	{
		if(b&1) res = res*A;
		A = A*A;
		b >>= 1;
	}
	return ;
}

时间复杂度 \(O(n^3 \log k)\)

Ⅰ：矩阵加速

好东西啊好东西。

先来道例题：P1962。题意很简单，就是让你求斐波那契数列的第 \(n\) 项 \(\text{mod} \ 10^9 +7\) 的值，其中 \(1 \leq n < 2^{63}\)。

显然有暴力的 \(O(n)\) 递推做法，更显然的是，它会超时。

考虑优化。我们知道， \(Fib_n\) 的值只跟 \(Fib_{n-1}\) 和 \(Fib_{n-2}\) 有关，我们在递推时保存最近的两个斐波那契数，即可得到下一个斐波那契数。

设 \(F(n)\) 表示一个 \(1 \times 2\) 的矩阵，\(F(n) = [Fib_n,Fib_{n-1}]\) 。而我们想要通过 \(F(n-1) = [Fib_{n-1},Fib_{n-2}]\) 来推得 \(F(n)\) 。为此，我们就要把 \(F(n-1)\) 第一列上的数放在 \(F(n)\) 的第二列上，并把 \(F(n-1)\) 两列上的数求和放在 \(F(n)\) 的第一列上。因此，我们可以构造出一个矩阵 \(A\)，使得

\[A= \left( \begin{array}{ccc} 0 & 1 \\ 1 & 1 \end{array} \right) \]

那么就有

\[F(n) = F(n-1) \times A \Leftrightarrow [Fib_n \ \ Fib_{n-1}] = [Fib_{n-1} \ \ Fib{n-2}] \times \left( \begin{array}{ccc} 0 & 1 \\ 1 & 1 \end{array} \right) \]

至此，我们得到了一个矩阵乘法的递推式，我们初始化 \(F(0) = [0 \ \ 1]\)，目标为 \(F(n) = F(0) \times A^n\) 的第一项。因为矩阵乘法满足结合律，我们就可以使用矩阵快速幂来快速计算 \(F(0) \times A^n\)。时间复杂度就是 \(O(2^3\log n)\) ，其中 \(2^3\) 是矩阵乘法所消耗的时间。矩阵乘法的结合律和递推式使得递推速度大为加快，这也就是我们所说的矩阵加速递推。

适用情况

  1. 可以抽象出一个长度为 \(n\) 的一维向量，该向量在每个单位时间内发生一次变化。也就是说这个矩阵只有一行；

  2. 变化的形式是一个线性递推（只有若干“加法”，或者“乘一个系数”的运算）；

  3. 该递推式在每个时间可能作用与不同的数据上，但本身保持不变；

  4. 向量变化时间（即递推轮数）很长，但向量长度 \(n\) 并不大。

有了这几个特点，我们就可以考虑矩阵乘法优化了。我们把这个长度为 \(n\) 的一维向量称为状态矩阵，把用于递推状态矩阵的固定不变的这个 \(A\) 矩阵称为 转移矩阵。若状态矩阵的第 \(x\) 个数对下一单位时间的状态矩阵中的第 \(y\) 个数产生影响，则把转移矩阵的第 \(x\) 行第 \(y\) 列赋值为适当的系数。

矩阵乘法加速递推的难点就在与构造，构造出一个合适的状态矩阵，再构造出一个合适的转移矩阵，之后就没有难度了，直接套矩阵快速幂即可。时间复杂度是 \(O(n^3\log T)\) ，\(T\) 是递推总轮数。

Ⅱ：高斯消元

介绍

高斯消元是一种求解线性方程组的方法。所谓线性方程组，是由 \(M\) 个 \(N\) 元一次方程共同构成的。线性方程组的所有系数可以写成一个 \(M\) 行 \(N\) 列的“系数矩阵”，再加上每个方程等号右侧的常数，可以写成一个 \(M\) 行 \(N+1\) 列增广矩阵，例如。

\[\begin{cases} x_1 + 2x_2 - x_3 = -6 \\ 2x_1 + x_2 - 3x_3 = -9 \\ -x_1 - x_2 + 2x_3 = 7 \end{cases} \Rightarrow \left( \begin{array}{ccc} 1 & 2 & -1 & -6 \\ 2 & 1 & -3 & -9 \\ -1 & -1 & 2 & 7 \end{array} \right) \]

高斯消元就是利用该矩阵进行一些操作来进行的。

初等行变换

上述操作可以分为三种。

  1. 交换两行；
  2. 把某一行乘一个非 \(0\) 的数；
  3. 把某行的若干倍加到零一行上去。

进行上述操作之后，我们可以知道，方程组的解并不会发生变化。上述三类操作就被称为矩阵的初等行变换。

思路

高斯消元法

高斯消元法的基本思路是利用矩阵的初等行变换将系数矩阵（除最后一列外的地方）消成上三角矩阵，再下到上回代求解。

  1. 枚举主元（主对角线上的元素），找到主元下面系数不是 \(0\) 的一行；

  2. 用变换 \(1\) ，把这一行和主元行交换；

  3. 用变换 \(2\) ，把主元系数变成 \(1\) ；

  4. 用变换 \(3\) ，把主元下面的系数变成 \(0\)。

引用董晓老师的图片

解可以有三种情况：

  1. 唯一解：\(i\) 可以枚举完 \(n\) 行，也就是说主元有 \(n\) 个。

  2. 无解：存在 \(a[i][i]\) 为 \(0\) ，常数不为 \(0\) 的行。也就是出现 \(0\times x = b(b \not=0)\) 的情况。

  3. 无穷多解：存在 \(a[i][i]\) 为 \(0\) ，常数为 \(0\) 的行。也就是出现 \(0 \times x = 0\) 的情况。

il bool Gauss()
{
	for(re int i=1;i<=n;i++)//行查找
	{
		int r = i;
		for(re int k=i;k<=n;k++)
			if(fabs(a[k][i]) > eps) { r = k; break; }
		if(r != i) swap(a[r],a[i]);//变换1
		if(fabs(a[i][i]) < eps) return false;//无解或无穷解
		for(re int j=n+1;j>=i;j--) a[i][j] /= a[i][i];//变换2
		for(re int k=i+1;k<=n;k++)
			for(re int j=n+1;j>=i;j--)//a[k][i]相当于从第i行到第k行变化的系数，而a[i][j]就是变哪个数的系数倍
				a[k][j] -= a[k][i]*a[i][j];
	}
	for(re int i=n-1;i>=1;i--)//回代
		for(re int j=i+1;j<=n;j++)
			a[i][n+1] -= a[i][j] * a[j][n+1];
	return true;
}

高斯-约旦消元法

与高斯消元法不同的是，高斯-约旦消元法把系数矩阵消成主对角矩阵，这样每一行 \(x_i\) 和常数都是一一对应的。令常数除以主元即为答案。

每轮循环，主元所在行不变，主元所在列消成 \(0\) 。

il bool Gauss_Jordan()
{
	for(re int i=1;i<=n;i++)//行查找
	{
		int r = i;
		for(re int k=i;k<=n;k++)
			if(fabs(a[k][i]) > eps) { r = k; break; }
		if(r != i) swap(a[r],a[i]);//变换1
		if(fabs(a[i][i]) < eps) return false;//无解或无穷解
		for(re int k=1;k<=n;k++)//每一列都消去0
		{
			if(k == i) continue;
			double t = a[k][i] / a[i][i];
			for(re int j=i;j<=n+1;j++)//a[i][1~j-1]都是0，再怎么乘还是0，所以不用管
				a[k][j] -= t*a[i][j];
		}
	}
	for(re int i=1;i<=n;i++) a[i][n+1] /= a[i][i];
	return true;
}

线性空间

引用一句话：“矩阵的加法和数乘运算所具有的不少性质，是一般线性空间同样具有的，事实上线性空间的定义本身就是从矩阵（以及其它一些数学对象）所具有的运算性质中抽象出来的。”

定义

线性空间

线性空间是一个关于以下两个运算封闭的向量集合。

  1. 向量加法 \(a+b\) ,其中 \(a,b\) 均为向量。

    而加法要满足这么几个性质：

    (1) \(\alpha + \beta = \beta + \alpha\)

    (2) \(\alpha + \beta + \gamma = \alpha + (\beta + \gamma)\)

    (3) 线性空间中有这么一个 \(0\) 元素，满足 \(\alpha + 0 = \alpha\)

    (4) 对于向量 \(\alpha\) ，都有一个 \(-\alpha\) 与之对应

  2. 标量乘法 \(k \times a\) ，也称数乘运算，其中 \(a\) 是向量，\(k\) 是标量。

    而数乘需要满足这么几个性质：

    (1) \(1 * \alpha = \alpha\)

    (2) $k(l\alpha) = (kl)\alpha \ \ \ $ (\(k,l\)为标量)

    (3) \((k+l)\alpha = k\alpha + l\alpha\)

    (4) \(k(\alpha + \beta) = k\alpha + k\beta\)

满足这两个大条件，就说这是一个线性空间。我们由此可以知道，这里的加法和乘法是广义的加法和乘法，也就是只要满足这几个条件，就能把它称之为加法和乘法，类似于 C++ 里面的运算符重载。

生成子集

给定若干个向量 \(a_1,a_2,\dots,a_k\) , 若向量 \(b\) 能由 \(a_1,a_2,\dots,a_k\) 经过加法和数乘得出，则称向量 \(b\) 能被向量 \(a_1,a_2,\dots,a_k\) 表出。那么，\(a_1,a_2,\dots,a_k\) 能表出的所有向量构成一个线性空间，\(a_1,a_2,\dots , a_k\) 被称为这个线性空间的生成子集。

线性相关和线性无关

任意选出线性空间内的若干个向量，如果其中存在一个向量能被其他向量表出，则称这些向量线性相关，否则称这些向量线性无关。

基和维数

线性无关的生成子集被称为线性空间的基底，简称基。基的另一种定义是线性空间的极大线性无关子集。一个线性空间内的所有基包含的向量个数一定都相等，这个个数被称为线性空间的维数。

以平面直角坐标系为例。平面直角坐标系中的所有向量构成一个二维线性空间，它的一个基就是单位向量集合\(\{(0,1),(1,0)\}\) 。实际上，任意两个不共线的向量都是这个线性空间的一个基底，而不共线就满足了它们是线性无关的。平面直角坐标系的 \(x\) 轴上的所有向量构成一个一维线性空间，它的一个基就是 \(\{(1,0)\}\)。

矩阵的秩

对于一个 \(n\) 行 \(m\) 列的矩阵，我们可以把它的每一行当作一个长度为 \(m\) 的向量，称为行向量。矩阵的 \(n\) 个行向量能够表出的所有向量构成一个线性空间，这个线性空间的维数被称为矩阵的行秩。类似地，我们可以定义列向量和列秩。事实上，矩阵的列秩一定等于行秩，他们都被称为矩阵的秩。

把这个 \(n\times m\) 的矩阵看作系数矩阵进行高斯消元（增广矩阵的最后一列全看作 \(0\)），得到一个对角矩阵。显然，对角矩阵的所有非零 行向量线性无关。事实上，矩阵的初等行变化就是行向量之间进行的加法和数乘，所以高斯消元不会改变矩阵的行向量表出的线性空间。由此可知，对角矩阵的所有非零行向量矩阵该线性空间的一个基，非零行向量的个数就是矩阵的秩。

为零的行向量因为可以由其它非零行向量 \(\times 0\) 的出，把它加上就线性有关了，因此要去掉，保证是线性无关的生成子集。

线性空间的异或推广-线性基