内积代数

在这篇文章中，我们提供了一些对于内积的有用代数技巧，这些技巧将在后面推导范围证明（以及将电路编码为内积）时非常有用。每条规则将附带一个简单的证明。

记号

加粗变量，如 $\mathbf{a}$，表示一个向量。未加粗的变量，如 $v$，表示一个标量。操作符 $\circ$ 是两个向量的 Hadamard 乘积（逐元素相乘），即 $[a_1, \dots, a_n]\circ[b_1, \dots, b_n] = [a_1b_1, \dots, a_nb_n]$。我们使用简写“lhs”和“rhs”分别表示一个方程的“左侧”和“右侧”。“加数”是加法中的一个元素，例如如果 $a + b = c$，那么 $a$ 和 $b$ 被称为加数。$\mathbf{1}$ 向量是一个全为 1 的向量，即 $[1, 1, \dots, 1]$。除非另有说明，所有向量隐含为相同的长度 $n$。

规则 1：一个向量是向量之和的内积可以展开

假设我们正在计算一个内积，其中一个向量是两个向量的和——例如 $\langle\mathbf{a} + \mathbf{b}, \mathbf{c}\rangle$。我们可以将其拆分为两个内积的和：$\langle \mathbf{a} + \mathbf{b}, \mathbf{c} \rangle = \langle \mathbf{a}, \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{c} \rangle$

证明：lhs 可以写成 $$ \sum_{i=1}^n(a_i+b_i)c_i $$

rhs 可以写成

$$ \begin{align} \sum_{i=1}^na_ici+\sum{i=1}^nc_ibi &=\sum{i=1}^n(a_ic_i+c_ibi) \\ &=\sum{i=1}^n(a_i+b_i)c_i \end{align} $$

规则 2：具有共同项的内积可以合并

下面 lhs 的两个内积有一个共同向量 $\mathbf{c}$。因此，它们可以合并： $$ \langle \mathbf{a}, \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{c} \rangle = \langle \mathbf{a} + \mathbf{b}, \mathbf{c} \rangle $$

这实际上是规则 1，仅左右两侧互换。

证明与规则 1 相同。

规则 3：将向量移到内积的另一侧

内积可以重写为 $\mathbf{1}$ 向量与原始向量的 Hadamard 乘积： $$ \langle \mathbf{a}, \mathbf{b} \rangle= \langle \mathbf{1}, \mathbf{a\circ b} \rangle $$

证明：

$$ \begin{align} \langle \mathbf{a}, \mathbf{b} \rangle&=\sum_{i=1}^na_ibi \\ \langle \mathbf{1}, \mathbf{a\circ b} \rangle&=\sum{i=1}^n1(a_ibi)\\ \sum{i=1}^na_ibi &= \sum{i=1}^n1(a_ib_i)\\ \end{align} $$

规则 4：我们可以向内积的一个项添加向量，以迫使两个内积具有共同项

假设我们在添加内积 $\langle\mathbf{x}, \mathbf{b}+\mathbf{c}\rangle$ 和内积 $\langle\mathbf{y}, \mathbf{b}\rangle$，并且内积的和为 $v$。注意它们有不同的分量，因此我们不能用规则 2 将它们相加。然而，以下等式

$$ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle = v $$

可以写为

$$ \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle $$

在上面的场景中，我们可以向两侧添加 $\langle\mathbf{y},\mathbf{c}\rangle$。

$$ \begin{align} \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle + \boxed{\langle\mathbf{y},\mathbf{c}\rangle}&= v + \boxed{\langle\mathbf{y},\mathbf{c}\rangle}\\ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle + \langle\mathbf{y},\mathbf{c}\rangle&= v + \langle\mathbf{y},\mathbf{c}\rangle \end{align} $$

现在我们有了共同的 $\mathbf{y}$ 项，我们可以使用规则 2 合并：

$$ \begin{align*} \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{\fbox{y}}, \mathbf{b}\rangle + \langle\mathbf{\fbox{y}},\mathbf{c}\rangle&= v + \langle\mathbf{y},\ma...