|
浅谈结构体运算律的证明——从矩阵乘法讲起
yummy
2020-03-09 13:03:10
Personal
## 目录
0. 一些说明
1. 矩阵乘法的结合律
1. 交换律
1. 结合律
1. 分配律
1. 练习题答案
## 0. 一些说明
本文作者yummy是个菜鸡，并没有读过一些专业文献，也只是一个初中生，所以文中可能会有一些不妥当的地方，请轻喷。
本文不会去讨论加法和乘法的性质，会直接作为“公理”使用。一些应当严谨证明的地方，yummy可能会用“显然”“感性理解”等词语带过。
本文中所有运算都是二元运算，用 $X=$一个关于 $A,B$ 的式子表示。默认左边的东西是右边东西的运算结果，即 $X=a\#b$.
说句实在的，这篇文章第一节看完之后把练习做掉你就看完所有这篇文章里面不是很水的内容了。
## 1. 矩阵乘法的结合律
如果不知道什么是矩阵乘法，[左转洛谷日报108](https://www.luogu.com.cn/blog/shehuizhuyihao/post-zhen-sheng-fa)。那么接下来我们就默认您会矩阵乘法了。注意，本文中，默认矩阵都是 $n\times n$ 的。
矩阵乘法有一个非常重要的性质，那就是
$$A\cdot B\cdot C=A\cdot(B\cdot C)$$
那篇日报没有讲解为什么矩阵乘法满足这个性质，这里简单地提一下。
设 $X=A\cdot B\cdot C,Y=A\cdot(B\cdot C)$，那么根据矩阵乘法定义，有：
$$X_{ij}=\sum_{l=1}^{n}(\sum_{k=1}^{n}A_{ik}B_{kl})C_{lj}=\sum_{l=1}^{n}\sum_{k=1}^{n}A_{ik}B_{kl}C_{lj}$$
$$Y_{ij}=\sum_{k=1}^{n}A_{ik}(\sum_{l=1}^{n}B_{kl}C_{lj})=\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ik}(B_{kl}C_{lj})$$
由于实数满足乘法结合律，故矩阵乘法满足结合律。
如果你认为上一行是对的，你就进坑了。
两个式子的第一个等号是不需要任何运算律的，但是从第一个等号到第二个等号需要用到乘法左分配律和右分配律：
$$(\sum a_i)b=\sum a_ib$$
$$b\sum a_i=\sum ba_i$$
我们看见，证明上面的结论只用到了乘法分配律与乘法结合律，我们是否可以把其他满足结合律的运算也套进矩阵“乘法”呢？
答案是肯定的。[**NOI** Online入门组T3](https://www.luogu.com.cn/problem/P6190)就用到了这个性质。这里，我们用加法代替普通矩阵乘的乘法，用`min`函数代替普通矩阵乘的加法,`min(a,b)+c=min(a+c,b+c)`，所以这个特殊矩阵乘满足结合律，也即运算：
$$X_{ij}=\min_{k=1}^nA_{ik}+B_{kj}$$
做几道练习：
1. 矩阵乘法满足交换律和分配律吗？请说明理由。
2. 下面的“矩阵乘法”满足结合律吗？
$$X_{ij}=\oplus_{k=1}^nA_{ik}+B_{kj}$$
3. Alice想要给Bob发送一个数字 $x$。由于乘法满足交换律，他们决定加密发送这个数：
- Alice发送 $ax$ 给Bob，$a$ 是Alice想好的一个数。
- Bob把Alice的数乘以 $a$ 发回去，也就是发回去 $abx$
- Alice把 $abx$ 除以 $a$ 发给Bob，也就是 $bx$
- Bob把发回来的数除以 $b$，得到 $x$。
请问这个过程用了乘法的哪些运算定律？
## 2. 交换律
对于一个运算 $\#$,若 $a\#b=b\#a$,则称该运算满足交换律。
如何证明一个运算满足交换律？
由于我们不是专业的人，感性理解一下就是：
> 这个运算是**对称**的，或者说两个自变量**地位相同**。
但是，有的时候，有些式子看上去很对称，但是不满足交换律。比如说这个很常见的场景：
> 当Alice和Bob意见不同的时候，听Alice的，否则听Bob的。
用一种运算描述就是：
```cpp
idea operator + (idea a,idea b)
{
if(a!=b)
return a;
else
return b;
}
```
看上去很对称，但是仔细一看，会发现：这个函数(运算)本质是：
$$ f(a,b)=a$$
所以，我们需要证明 $f(a,b)=f(b,a)$ 对于任意的 $a,b$ 都成立。
举个栗子：证明对于所有自然数，异或满足交换律。
首先，我们根据定义，通过枚举法得知，$a,b\in \{0,1\}$时，异或满足交换律。
我们如果把整数 $a,b$ 看成了两个01串，那么我们就有：
$$x_i=a_i\oplus b_i=b_i\oplus a_i$$
由于 $a_i,b_i\in \{0,1\}$，所以后两坨相等，故对于任意整数异或都满足交换律。
交换律有什么应用？实际上，一个仅满足交换律的运算好像还真没有简便计算的方法。
但是，**如果 # 运算满足交换律和与 \$的左分配律，那么#满足与\$的右分配律。** 用符号语言就是：
若有
$$a\#b=b\#a\qquad a\#(b\$c)=a\#b\ \$\ a\#c$$
则有
$$(b\$c)\#a=b\#a\ \$\ c\#a$$
但是与下一节的结合律结合在一起，就有好van的事情发生。
做几道练习：
1. 你能找出一个满足交换律，不满足结合律的运算吗？
2. 若一个运算#满足交换律，那么 $a\#b\#c=a\#c\#b$吗？
## 3. 结合律
同样地，若 $f(f(a,b),c)=f(a,f(b,c))$，则称运算 $f$ 满足结合律。
结合律的证明和交换律差不多。结合律有个很广泛的应用就是快速幂/光速幂。
**注意：快速幂/光速幂不需要满足交换律**，不然矩阵快速幂哪来的？
光速幂是啥？自行右转P5110.
在洛谷日报108中讲到矩阵乘法能够通过预先dp减少乘法的计算次数，其实不光是矩阵乘法，任何满足结合律的运算都可以通过预先区间dp减少乘法计算次数。
如果一个运算同时满足交换律和结合律，那么2.2的式子就成立了。我们可以用很多trick。
举个栗子，假设你现在不会FFT，你计算多项式乘法是 $O(NM)$的暴力算法，现要求一些多项式的连乘积。由于多项式乘法满足交换律和结合律，所以你可以每次都选择项数最少的两个多项式计算。同样这个方法适用于多项式少而大的情况。
做几道练习：
1. 合并果子
## 4. 分配律
本文中分配律默认指左分配律。右分配律与左分配律大体相似。
分配律的证明也没啥好讲的，和
**如果运算 # 同时满足左右分配律，则 # 满足交换律。**
## 5. 练习题答案
1.1 不满足交换律，但是满足分配律。证明略。
1.2 不满足， $a\oplus(b+c)\neq(a\oplus b)+(a\oplus c)$
1.3 我们看到，这个过程之所以可以成功，就是基于一个事实：
$$x\times a\times b=x\times b\times a$$
证明这个式子成立需要用到交换律和结合律。
考虑如果他们使用了一个不满足交换律和结合律的运算...
> Alice发送 $a^x$ 给Bob，$a$ 是Alice想好的一个数。
> Bob把Alice发送的数计算 $b^{a^x}$ 后返回给Alice。
> Alice求 $\log_a$ 得到一个奇怪的东西。
> Bob求 $\log_b$ 得到一个更奇怪的东西。
2.1 答案不唯一，比如说 $a\#b=(a-b)^2$
2.2 不满足。这是一个容易出现的错误。不信可以用2.1的结果验证一下。
|