动机
设有人给出三个方阵,并声称前两个的乘积等于第三个。用初等方法计算整个乘积需要立方时间。如果我们愿意接受一个可控的概率,即可能漏掉一个错误的断言,那么验证的代价可以更低。
关键在于用一个随机向量来检验所声称的等式。矩阵与向量的乘法只需二次数量的算术运算,因此少数几次独立检验可以比完整的初等乘积便宜得多。我们将精确证明:错误概率的含义是什么,为什么正确的断言绝不会被拒绝,以及分析需要哪些关于固定输入和算术的假设。
定义
定义 6.4.1
(矩阵乘积的随机向量检验)
设 为一个域,设 ,并设 。 中的算术是精确的。需要验证的断言是 。抽样 ,其各坐标相互独立,且每个坐标都从两个不同的域元素 和 中均匀选取。计算 ,再计算 ,并独立地计算 。若 则接受该次试验,否则拒绝。
一次检验使用三次矩阵与向量的乘法和一次向量比较。实现时不需要计算 ,也不需要构造差矩阵 。对于稠密矩阵,一次试验需要 次域运算,并且除输入矩阵之外只需要 个额外的域元素。在同一次试验的三个乘积中,必须使用同一个向量。
定理
定理 6.4.2
(单侧验证错误)
若 ,则每次试验都接受。若 ,且这些矩阵在随机向量被抽样之前已经固定,则一次试验接受的概率至多为 。
定理 6.4.3
(独立重复)
对于整数 ,用相互独立的全新向量进行 次试验,并且仅当所有试验都接受时才接受。正确的乘积总是被接受;不正确的固定乘积被接受的概率至多为 。稠密运算的代价为 次域运算。
这里的概率是针对一个固定的矩阵三元组,就验证者的随机选择而言的。该定理并不是说,对某个特定向量而言,至多有一半的错误矩阵能够蒙混过关。
证明
一个非零行就足够了
证明
(一个非零行限制接受概率)
记 。试验接受当且仅当 。若 ,则该等式对每个向量都成立,这就证明了完美完备性。现设 。则 的某一行在第 列含有非零系数 。固定 中除 之外所有坐标的任意取值。在该行中,方程 变为
因为 是域且 ,这个方程关于 至多有一个解。在两个可能的取值 和 中,至多有一个能满足它。在对其余坐标取条件之后,剩下的那个坐标仍然是独立的公平选择,因此该行为零的条件概率至多为 。对其余坐标取平均,可得无条件下同样的上界。事件 包含于这一行为零的事件之中,因此它的概率同样至多为 。
该证明在每个域中都成立,包括特征为二的域: 与 仍然不同,并且乘以非零元素仍然是单射。证明不要求 的各项相互独立或随机。它也不要求我们知道哪一行是非零的;这一行只在分析中使用。
证明透视
固定其余所有坐标,只留一个
关键一步把矩阵恒等式化为一条标量方程: 迫使 的每一行在 处为零,所以只需界定某个单一非零行为零的概率。固定除 之外的所有坐标(其中 ),该行方程化为 ,而 只依赖其余坐标。由于 是域, 可逆,方程至多有一个解,所以 两个值中至多一个可行。这里用到两个假设,且只在这里用到: 中 ,使抽样集合有两个元素;以及 可逆。各坐标相互独立,使得在条件于其余坐标之后, 仍是公平的选择。选取哪一行、哪一个坐标只属于分析,验证者无须知道它们是什么。
证明
(独立重复)
对于重复试验,输入三元组以及 都不变,而随机向量相互独立。对于不正确的固定三元组,每次试验的接受概率至多为 ,所以 次试验全部接受的概率至多为 。若某次试验拒绝,立即停止既保持正确性,又可以节省运算。该上界所计的是所有试验都被执行的最坏情形。
更大的抽样集合
同样的论证适用于由 个不同元素组成的有限集合 。每个坐标独立且均匀地从 中抽样。在固定所有其他坐标之后, 个取值中至多有一个满足所选取的非零行方程。因此一次试验漏掉不正确乘积的概率至多为 ,而 次独立试验漏掉它的概率至多为 。
对于有限域 ,从整个域中均匀抽样即可得到这一上界。更一般地,该子集不必对加法或乘法封闭:只有其元素互不相同以及均匀独立抽样才是要紧的。由公平比特构造精确的均匀样本可能有单独的代价,特别是当 不是 的幂时。上述域运算次数的计数把抽样视为可得的,并把算术运算单独计费。
失败概率的上界可以事先选定。对于二元向量,当 时,取 可使接受一个固定的不正确乘积的机会至多为 。若验证者检验 个固定的断言,并希望任何不正确接受的概率至多为 ,则可以给每个断言分配失败概率 ,并应用并集界。最后这个并集界并不要求不同断言之间相互独立,但每个断言各自的重复试验必须满足其个别误差估计所用的独立性假设。
当域为有限域时:秩的作用
若 ,且整个向量在 上均匀分布,则一次试验的实际错误概率有一个有用的精确描述。设 。由秩–零度定理,核的维数为 ,所以在等可能的 个向量中,核含有 个。因此
非零的差矩阵的秩至少为一,从而得到前面的 上界。秩为一的差矩阵可以达到该上界,而满秩的差矩阵仅在零向量上被漏掉,其错误概率为 。验证者不需要计算秩:这样做会增加工作量,而对每个非零差矩阵都适用的一致最坏情形保证已经足够。
这一精确的秩公式依赖于从整个有限域中均匀抽样。对于较大域中的二元向量,它不能自动适用,因为这些向量只在子集 上均匀分布。单坐标论证对该子集仍然有效,并且仍然给出 的上界。区分精确概率与最坏情形上界,可以避免对试验预算作出无根据的削减。
概念视角组合
数立方体上被接受的顶点
二元向量就是 维立方体的 个顶点,同一个上界也可以通过计数得到。取 中一行,其第 个系数 ,把每个 的顶点 与只在第 个坐标上不同的顶点 配成一对。此时 ,而 在所选那一行的分量是 。因此该行不可能在一对顶点上同时为零,每一对至多有一个顶点被接受,所以 个顶点中至多有 个被接受。
高概率的结论还取决于实例是何时选定的。对于维数至少为二的任何已知非零测试向量 ,存在一个与它正交的非零行向量,而以该行为一行的非零矩阵可以使 化为零。如果允许恶意的证明者在得知验证者的向量之后再选择差矩阵,则不能照原样援引固定输入的定理。在所述的实验中,矩阵先被固定,然后验证者再抽样私有的全新随机数。
证书的含义
若某次试验拒绝,则 。向量 是所声称等式为假的一个简短证书:另一个人可以重新计算两边并加以比较。相反,一个被接受的向量并不证明等式成立;非零的差矩阵可以使某些向量化为零。重复被接受的试验按已证明的上界提高信心,但并不会把接受变成确定性的证明。
单侧一词指出了哪一种结果可能出错。在精确的域算术下,拒绝总是可靠的。对于不相等的乘积,接受则可能是错的。当必须以高概率发现错误、而又不能容忍对正确计算的误报时,这种保证很有用。应用时应当根据漏掉错误的后果来选择试验次数,而不应把有限次被接受的检验说成绝对的确定性。
反例模式
固定的向量可能漏掉错误
设 ,。则 非零,但向量 被该差矩阵变为零。检验这个特定的向量会接受一个不正确的乘积。随机抽样限制了固定输入下这一事件发生的机会,但并不使每个单独的向量都成为证书。
例题详解
例题 6.4.4
(一个被漏掉的错误与一个被发现的错误)
对于 和 ,试验接受恰好当 的第二个坐标为零。在四个等可能的二元向量中, 和 接受,而 和 拒绝。错误概率恰为 ,这说明一般的二元上界可以是紧的。
例题 6.4.5
(正确的乘积总能通过)
在实数上,取 ,。它们的乘积为 。对于 ,计算得 ,。这个等式并非该向量所特有:由结合律,对每个向量都有 。
例题 6.4.6
(三元素抽样)
在 上,取 和 。若每个坐标在 中均匀取值,则差矩阵使 化为零恰好当其第二个坐标为零。一次试验漏掉该错误的概率为 ;四次独立试验漏掉它的概率为 。
例题 6.4.7
(选择试验预算)
若要用独立的二元向量把错误概率限制在 以内,选择 ,因为 。对于一千个固定的断言(无论其正确与否),取 的并集界给出任何不正确接受的概率至多为 。这个并集界不需要假设各个断言相互独立。
常见错误
常见错误
(对每次重复都沿用同一个向量)
只抽样一个向量并在每次重复中都使用它,并不会使错误概率相乘。在第一个例子中,若第二个坐标为零,则同一个坏向量会通过每一次重复检验。全新的独立向量才是指数下降的机制。每次试验的全新向量还必须与命题中固定的矩阵相互独立。
常见错误
(未经论证就取素数模)
把整数矩阵对某个素数取模会改变问题,除非这一约化有正当理由。若一个整数差矩阵的所有元素都是该素数的倍数,则它在模该素数下成为零矩阵,并通过该域中的每一次检验。例如,一个等于 的整数差矩阵元素在模 下为零。域上的定理验证的是在所选域中的相等;要推出整数上的相等,还需要另外的论证。
常见错误
(把浮点运算当作精确运算)
最后,浮点舍入并不是精确的域算术。舍入可能使正确的乘积看起来不相等,也可能掩盖微小的误差,所以单侧保证不能自动推广到普通的浮点计算。数值验证器需要一个适合其算术模型的误差分析。
总结
随机向量把矩阵乘积恒等式化为三次二次时间的矩阵与向量乘法。对于一个固定的不正确乘积,一个非零行把二元坐标情形下未被发现错误的概率限制在二分之一。独立重复使该概率指数下降,而在精确的域算术下正确的乘积总能通过。该结果依赖于抽样、固定输入和域这几方面的假设。
练习
快速检查
(设 ,。列出被接受的二元向量及其概率。)
解答 · 答案
差矩阵为 ,所以试验接受恰好当第一个坐标为零。被接受的向量为 和 ,概率为 。
快速检查
(在 上,每个坐标从整个域中均匀抽样。给出三次独立试验都接受一个固定的错误乘积的概率上界。)
解答 · 答案
一次试验的错误概率至多为 ,由独立性,三次都接受的概率至多为 。某些特定的错误矩阵可能有更小的概率。
快速检查
(解释为什么对十次重复试验使用同一个二元向量,未必能给出 的错误概率。)
解答 · 答案
对于 和 ,检验接受恰好当所抽样的第二个坐标为零。把同一个向量重复使用十次,接受的概率仍为 ,而不是 。
快速检查
(给出整数 矩阵,使其乘积不等于所声称的整数值,但在模 下与之相等。解释 上的验证者看到了什么。)
解答 · 答案
取 ,。整数值 与 不同,但两者模七后都化为 。 上的验证者看到的是一个正确的域恒等式,并接受每一个向量;这并不是其域层面保证的错误。