向量
定义
线性代数上，对于一个 n n n 维向量就是一个长度为 n n n 的数组 a a a，其中 a i ∈ F a_i\in F ai∈F， F F F 一般为 R \R R 或 KaTeX parse error: Undefined control sequence: \C at position 1: \̲C̲。
运算
数乘
对于向量 α = ( a 1 , a 2 , ⋯ , a n ) \alpha=(a_1,a_2,\cdots,a_n) α=(a1,a2,⋯,an) 和 k ∈ F k\in F k∈F，定义 k α = ( k a 1 , k a 2 , ⋯ , k a n ) k\alpha=(ka_1,ka_2,\cdots,ka_n) kα=(ka1,ka2,⋯,kan)，相当于对 α \alpha α 中每一项乘 k k k。运算结果为一个向量。
求和
对于向量 α = ( a 1 , ⋯ , a n ) , β = ( b 1 , ⋯ , b n ) \alpha=(a_1,\cdots,a_n),\beta=(b_1,\cdots,b_n) α=(a1,⋯,an),β=(b1,⋯,bn)，定义 α + β = ( a 1 + b 1 , ⋯ , a n + b n ) \alpha+\beta=(a_1+b_1,\cdots,a_n+b_n) α+β=(a1+b1,⋯,an+bn)，即对应项分别相加。运算结果同上。
内积
对于向量 α , β \alpha,\beta α,β，要求内积运算 ( α , β ) (\alpha,\beta) (α,β) 的结果为 F F F 中的一个数，且满足：
- 对称性： ( α , β ) = ( β , α ) (\alpha,\beta)=(\beta,\alpha) (α,β)=(β,α)；
- 两个线性性：
- ( α + γ , β ) = ( α , β ) + ( γ , β ) (\alpha+\gamma,\beta)=(\alpha,\beta)+(\gamma,\beta) (α+γ,β)=(α,β)+(γ,β)；
- 对于 c ∈ F c\in F c∈F， ( c α , β ) = c ( α , β ) (c\alpha,\beta)=c(\alpha,\beta) (cα,β)=c(α,β)；
- 正定性： ( α , α ) ≥ 0 (\alpha,\alpha)\ge 0 (α,α)≥0，当且仅当 α \alpha α 为零向量时取等号。
当 F F F 为 R \R R 时，我们一般定义内积运算 ( α , β ) = a 1 b 1 + a 2 b 2 + ⋯ + a n b n (\alpha,\beta)=a_1b_1+a_2b_2+\cdots +a_nb_n (α,β)=a1b1+a2b2+⋯+anbn，即对应项相乘后求和；对于二维向量 α , β \alpha,\beta α,β， ( α , β ) (\alpha,\beta) (α,β) 即为点积运算 α ⋅ β \alpha\cdot\beta α⋅β。内积的运算结果为一个属于 F F F 的数。
矩阵
概念
由 m × n m\times n m×n 个数排列成的 m m m 行 n n n 列矩形数表，称为一个 m × n m\times n m×n 矩阵。矩阵实际上表示的是向量和向量的关系，而一个 n n n 维向量即为一个 n × 1 n\times 1 n×1 的矩阵。
[ a 11 ⋯ a 1 n ⋮ ⋱ ⋮ a m 1 ⋯ a m n ] \begin{bmatrix} a_{11}& \cdots& a_{1n}\\ \vdots& \ddots&\vdots \\ a_{m1}& \cdots& a_{mn} \end{bmatrix} a11⋮am1⋯⋱⋯a1n⋮amn
运算
数乘、加法
数乘、加法运算与向量类似。
乘法
对于矩阵 A = ( a i j ) m × r , B = ( b i j ) r × n A=(a_{ij})_{m\times r},B=(b_{ij})_{r\times n} A=(aij)m×r,B=(bij)r×n，则令 A B = C = ( c i j ) m × n AB=C=(c_{ij})_{m\times n} AB=C=(cij)m×n，定义
c i j = ∑ k = 1 r a i k × b k j c_{ij}=\sum_{k=1}^r a_{ik}\times b_{kj} cij=k=1∑raik×bkj
c i j c_{ij} cij 其实就是 a a a 的第 i i i 行与 b b b 的第 j j j 列分别组成的向量求内积。矩阵乘法符合结合律但是不符合交换律。
计算
[ x 1 0 0 x 1 0 0 x ] n \begin{bmatrix}x&1&0\\0&x&1\\0&0&x\end{bmatrix}^n x001x001x n
我们令单位矩阵 I I I 为从左上到右下对角线为 1 1 1 其余为 0 0 0 的矩阵，这里 I = [ 1 0 0 0 1 0 0 0 1 ] I=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix} I= 100010001 ，单位矩阵满足任何矩阵乘或乘以 I I I 得到的都是这个矩阵。那么
[ x 1 0 0 x 1 0 0 x ] n = ( I x + [ 0 1 0 0 0 1 0 0 0 ] ) n \begin{aligned}\begin{bmatrix}x&1&0\\0&x&1\\0&0&x\end{bmatrix}^n&=\left(Ix+\begin{bmatrix}0&1&0\\0&0&1\\0&0&0\end{bmatrix}\right)^n\end{aligned} x001x001x n= Ix+ 000100010 n
可以发现后面的矩阵在求立方后就变为全 0 0 0 了，因为 I x Ix Ix 是单位矩阵，满足“交换律”，于是我们考虑二项式展开，只保留前三项即可。过程略。
已知 A 1 = 2 , A 2 = 3 , A n = 4 A n − 2 + 3 A n − 1 A_1=2,A_2=3,A_n=4A_{n-2}+3A_{n-1} A1=2,A2=3,An=4An−2+3An−1，求 A n A_n An。
我们不妨构造矩阵 [ A n − 1 A n ] \begin{bmatrix}A_{n-1}\\A_{n}\end{bmatrix} [An−1An]，考虑由 [ A n − 2 A n − 1 ] \begin{bmatrix}A_{n-2}\\A_{n-1}\end{bmatrix} [An−2An−1] 进行矩阵乘法转移。我们构造转移矩阵 [ 0 1 4 3 ] \begin{bmatrix}0&1\\4&3\end{bmatrix} [0413]，转移即为
[ A n − 1 A n ] = [ 0 1 4 3 ] × [ A n − 2 A n − 1 ] \begin{bmatrix}A_{n-1}\\A_n\end{bmatrix}=\begin{bmatrix}0&1\\4&3\end{bmatrix}\times \begin{bmatrix}A_{n-2}\\A_{n-1}\end{bmatrix} [An−1An]=[0413]×[An−2An−1]
转移矩阵即可快速幂进行优化。构造过程就考虑矩阵乘法的本质——行向量与列向量的内积。
![[网络协议篇] UDP协议](https://img-blog.csdnimg.cn/img_convert/9c2a494bc6e3d740c9208f49746e31e2.png)
