矩阵基础
定义：
数学意义上有更加严谨的矩阵定义，这里不过多展开，如有需要还请自行查询。
由\(n\times m\)个数排成\(n\)行\(m\)列，第\(i\)行\(j\)列的数记为\(a_{i,j}\)。我们称这\(n \times m\)个数为矩阵\(A\)的元素，记作：
\[A=\begin{bmatrix} &a_{1,1} &a_{1,2} &... &a_{1,m} &\\ &a_{2,1} &... &... &a_{2,m} \\ &... &... &... &... \\ &... &... &... &... \\ &a_{n,1} &... &... &a_{n,m} \end{bmatrix} \]两个或者两个以上的矩阵的行数和列数都相同，那么我们就说这两个或两个以上的矩阵是同型矩阵。
当且仅当矩阵\(A\)和矩阵B为同型矩阵，且满足任意\(a_{i,j}=b_{i,j}\)时，我们称矩阵\(A\)等于矩阵\(B\),记作\(A=B\)
基本运算
加法
只有两个同型矩阵才能相加。
若\(A\)和\(B\)为同型矩阵，\(A=a_{1,1},...,a_{n,m}\),\(B=b_{1,1},...,b_{n,m}\)
则\(A+B=a_{1,1}+b_{1,1},...a_{i,j}+b_{i,j},...a_{n,m}+b_{n,m}\)
例如：
\[\begin{bmatrix} &1 &2 &5 & \\ &3 &4 &6 \\ &9 &11 &13 \\ \end{bmatrix}+ \begin{bmatrix} &0 &14 &15 & \\ &13 &17 &16 \\ &19 &12 &18 \\ \end{bmatrix}= \begin{bmatrix} &1+0 &2+14 &5+15 & \\ &3+13 &4+17 &6+16 \\ &9+19 &11+12 &13+18 \\ \end{bmatrix}= \begin{bmatrix} &2 &16 &20 & \\ &16 &21 &22 \\ &28 &23 &31 \\ \end{bmatrix} \]减法与加法同理。
乘法
矩阵与实数相乘：
定义矩阵\(A\)以及一个任意实数\(k\),则\(A\)与\(k\)的乘积为：
\[\begin{bmatrix} &a_{1,1} &... &a_{1,m} & \\ &... &... &... \\ &a_{n,1} &... &a_{n,m} \\ \end{bmatrix}\times k= \begin{bmatrix} &a_{1,1}\times k &... &a_{1,m}\times k & \\ &... &... &... \\ &a_{n,1}\times k &... &a_{n,m}\times k \\ \end{bmatrix} \]再来看看矩阵之间的乘法
设矩阵\(A\)有\(n_A\)行，\(m_A\)列，矩阵\(B\)有\(n_B\)行，\(m_B\)列。
只有当\(m_A=n_B\)时，\(A\)和\(B\)才能相乘。
矩阵之间的乘积依然是矩阵,我们\(A\)和\(B\)的乘积为矩阵\(C\)。则矩阵\(C\)有\(n_A\)行,\(m_B\)列。
\[C_{i,j}=a_{i,1}\times b_{1,j}+a_{i,2}\times b_{2,j}+...+a_{i,n_A}\times b_{n_{A},\ j} =\sum_{r=1}^{n_A}a_{i,r}\times b_{r,j} \]例如:
\[\begin{bmatrix} &1 &2 &3 & \\ &4 &5 &6 \\ \end{bmatrix}\times \begin{bmatrix} &7 &8 & \\ &9 &10 \\ &11 &12 \\ \end{bmatrix}= \begin{bmatrix} &1\times 7 +2\times9+3\times11 &1\times 8+2\times10+3\times12 &\\ &4\times7+5\times9+6\times11 &4\times8+5\times10+6\times12 &\\ \end{bmatrix} \]矩阵也同样存在幂运算，一个矩阵的\(k\)次幂表示\(k\)个该矩阵相乘。
单位矩阵
在实数的运算中，我们规定\(1\)为实数的单位，\(1\)乘的任何实数的结果都为这个实数本身。
矩阵运算中，我们也有一个单位矩阵,单位矩阵乘任意矩阵的结果等于这个矩阵本身。
单位矩阵的主对角线值为\(1\),其余位置都为\(0\)。
一个\(3\times 3\)的单位矩阵：
\[\begin{bmatrix} &1 &0 &0 & \\ &0 &1 &0\\ &0 &0 &1\\ \end{bmatrix} \]例：
\[\begin{bmatrix} &1 &0 &0 & \\ &0 &1 &0\\ &0 &0 &1\\ \end{bmatrix}\times \begin{bmatrix} &x_1 & \\ &x_2 &\\ &x_3 &\\ \end{bmatrix}= \begin{bmatrix} &1\times x_1+0\times x_2+0\times x_3 & \\ &0\times x_1+1\times x_2+0\times x_3&\\ &0\times x_1+0\times x_2+1\times x_3 &\\ \end{bmatrix}= \begin{bmatrix} &x_1 & \\ &x_2 &\\ &x_3 &\\ \end{bmatrix} \]零矩阵
一个矩阵中的所有元素都为\(0\)则称这个矩阵为零矩阵。
零矩阵与任意矩阵相加都等于这个矩阵本身，与任意矩阵相乘都等于零矩阵。(前提是这两个矩阵能够相加或相乘)
矩阵的性质
一、加法:
定义\(A\)和\(B\)为同型矩阵。
加法交换律：\(A+B=B+A\)
加法结合律：\((A+B)+C=A+(B+C)\)
\(A+O=A\) (\(O\)为零矩阵)
二、乘法
乘法结合律 :\((AB)C=A(BC)\)
左分配律:\(A\times(B+C)=A\times B+A\times C\)
右分配律:\(C\times(A+B)=C\times A+C\times B\)
由于矩阵乘法需要满足前者的列数等于后者行数这一性质，相乘顺序对于矩阵乘法非常重要。
矩阵乘法不一定满足交换律。
实际应用
矩阵快速幂
与整数运算一样，矩阵也存在同样的幂运算，也同样可以使用快速幂，时间复杂度同样为\(O\)(\(log\) \(n\))。不过由于矩阵运算的特殊性，矩阵的行数和列数越大，常数也会有所增大。
矩阵与DP
矩阵快速幂优化递推式
拿最简单的斐波那契数列为例，递推式为:
\(f[i-1]+f[i]=f[i+1]\)
假设我们现在要求斐波那契数列的第n位，用正常递推方法做的话时间复杂度为\(O(n)\),当\(n\)较大时会超时。
假设这个递推式不是加法，而是乘法，最好是幂运算的形式，我们就可以使用快速幂实现\(O\)(\(log\) \(n\))的快速求解。
可惜这是一个加法递推式，但矩阵可以解决这个问题。
我们考虑把递推式左边写成一个矩阵的形式：
\[\begin{bmatrix} &f[i-1] &f[i]& \\ \end{bmatrix} \]再试着把递推式右边也写成矩阵
\[\begin{bmatrix} &f[i] &f[i+1]& \\ \end{bmatrix} \]我们利用矩阵乘法，使得上述矩阵乘以一个矩阵后得到递推式右边。我们设乘上的这个矩阵为转移矩阵，记作\(C\)
那么:
\[\begin{bmatrix} &f[i-1] &f[i]& \\ \end{bmatrix}\times C= \begin{bmatrix} &f[i] &f[i+1]& \\ \end{bmatrix} \]我们反过来想，看看右边这个矩阵是怎么乘过来的。
\[\begin{bmatrix} &f[i] &f[i+1]& \\ \end{bmatrix}= \begin{bmatrix} &f[i-1]\times 0+f[i]\times 1 &f[i-1]\times1+f[i]\times 1& \\ \end{bmatrix} \]根据矩阵乘法的定义，我们可以得到转移矩阵
\[C=\begin{bmatrix} &0 &1& \\ &1 &1& \\ \end{bmatrix} \]即：
\[\begin{bmatrix} &f[i-1] &f[i]& \\ \end{bmatrix}\times \begin{bmatrix} &0 &1& \\ &1 &1& \\ \end{bmatrix} =\begin{bmatrix} &f[i] &f[i+1]& \\ \end{bmatrix} \]同样的，我们也可以用\(f[i]\)和\(f[i+1]\)的矩阵乘上\(C\)得到包含\(f[i+1]\)和\(f[i+2]\)的矩阵。
换句话说，我们用\(f[i-1]\)和\(f[i]\)的矩阵乘上矩阵\(C\)的二次方后得到了包含\(f[i+1]\)和\(f[i+2]\)的矩阵。
那么，只要我们用\(f[i-1]\)和\(f[i]\)的矩阵乘乘上矩阵\(C\)的\(n\)次方，就能得到包含\(f[i+n-1]\)和\(f[i+n]\)的矩阵。
由于我们知道斐波那契数列的前两位（也就是\(f[1]\)和\(f[2]\)）,那么我们可以将其作为初始矩阵。
再用矩阵快速幂算出转移矩阵\(C\)的\(n-2\)次方，用初始矩阵乘上转移矩阵的\(n-2\)次方，就能得到一个包含\(f[n-1]\)和\(f[n]\)的矩阵，也就求出了斐波那契数列的第n位。时间复杂度接近快速幂。
同样的，对于别的递推式，我们可以将已知的数作为初始矩阵，再根据递推式推导出转移矩阵，通过快速幂加快递推过程。
大部分DP都可以写成递推的形式，我们可以用矩阵加速递推式("矩阵能加速所有递推式"---Gym学长)
矩阵与动态DP
当一个DP问题需要支持修改操作的时候，一切都变得麻烦起来了。因为没一个修改对DP的影响我们都有可能需要从头再DP一遍，时间复杂度难以接受。
矩阵结合律以及不满足交换律这一特点给了它参与进动态DP的可能。
为什么呢？
首先矩阵是可以结合的，这使得我们我们可以直接维护矩阵，利用矩阵进行DP。
满足结合律，所以可以用快速幂加速。
不满足交换律，\(A\times B\) 不一定等于\(B\times A\),这可以更好的满足DP需要的无后效性，方便转移。
广义矩阵乘法
为了更好的适应DP的需求，我们需要一个功能更强的矩阵乘法
我们规定\(⊕\)和\(⊗\)表示两个满足如下规律的运算：
\(1.\) \(⊗\)满足交换律: \(a⊗b=b⊗a\)
\(2.\) \(⊗\)满足结合律: \((a⊗b)⊗c=a⊗(b⊗c)\)
\(3.\) \(⊗\)对\(⊕\)满足分配率: \(a⊗(b⊕c)=a⊗b+a⊗c\)
如果这两个运算满足这些规律，那么：
\[ A\times B=\bigoplus_{1}^{n}A_{i,k}\otimes B_{k,j} \]平时用的比较多的情况就是:
\(1.\) \(⊕\)是"\(+\)",\(⊗\)是"\(\times\)" (普通矩阵乘法)
\(2.\) \(⊕\)是\(max\)或\(min\),\(⊗\)是"\(+\)"
第一种情况前文讲过了，我们再来看看第二种情况。
\[C_{i,j}=\max_{k=1}^{n}A_{i,k}+B_{k,j} \]实例：
给出一个序列\(a_i\),规定一个区间的权值和为\(a_i\)的和，要求你找到一个权值和最大的区间。
这是个很简单的问题，但是，你先别急。我们用广义矩阵做一下这个题
标签：begin,end,矩阵,笔记,times,bmatrix,&... From： https://www.cnblogs.com/int-Hello-world/p/17462222.html