東京大学 情報理工学系研究科 コンピュータ科学専攻 2015年8月実施 専門科目I 問題1

标签：

• Tokyo-University
• Matrix-Multiplication-Algorithms

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

向量、矩阵之间的等号均按元素模 $2$ 理解。随机 $0$-$1$ 向量是指各分量独立且等概率取 $0,1$ 的向量，零向量和零矩阵分别记为 $o,O$。回答下列问题。

（1）对随机向量 $x\in\{0,1\}^3$，求

$$\begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}x=o$$

成立的概率。

（2）设 $A$ 是不满足 $A=O$ 的 $n\times n$ 整数矩阵，$x\in\{0,1\}^n$ 为随机向量。证明 $Ax=o$ 的概率不超过 $1/2$。

（3）设 $A,B,C$ 是不满足 $AB=C$ 的 $n\times n$ 整数矩阵，$x\in\{0,1\}^n$ 为随机向量。证明 $ABx=Cx$ 的概率不超过 $1/2$。

（4）给出一个 $O(n^2)$ 随机算法：若 $AB=C$，总回答“成立”；若 $AB\ne C$，则以严格大于 $9/10$ 的概率回答“不成立”。

Kai

以下计算均在域 $\mathbb F_2$ 上进行。

(1)

三个方程分别给出 $x_2=x_3$、$x_1=x_3$、$x_1=x_2$，故只有 $x=(0,0,0)^\mathsf T,(1,1,1)^\mathsf T$ 两个解。因此

$$\Pr(Ax=o)=\frac{2}{2^3}=\boxed{\frac14}.$$

(2)

取 $A$ 的一个非零行，并在该行中取系数为 $1$ 的位置 $j$。固定除 $x_j$ 外的所有分量后，该行与 $x$ 的内积形如

$$x_j+c\pmod 2.$$

由于 $x_j$ 等概率取 $0,1$，该内积为 $0$ 的条件概率恰为 $1/2$。事件 $Ax=o$ 还要求其余各行也为 $0$，故

$$\boxed{\Pr(Ax=o)\le \frac12}.$$

(3)

令 $D=AB-C$。由 $AB\ne C$ 知 $D\ne O$，且

$$ABx=Cx\iff Dx=o.$$

由（2）立即得到所求概率不超过 $1/2$。

(4)

独立重复以下检验 $4$ 次：随机生成 $x\in\{0,1\}^n$，依次计算

$$y=Bx,\qquad z=Ay,\qquad t=Cx\pmod2.$$

若某次 $z\ne t$，回答“不成立”；四次均相等时回答“成立”。每次只做三次矩阵向量乘法，故总时间为 $O(n^2)$。

若 $AB=C$，算法必定回答“成立”。若 $AB\ne C$，由（3），四次均未检出错误的概率至多为 $2^{-4}=1/16$，所以回答“不成立”的概率至少为

$$1-\frac1{16}=\frac{15}{16}>\frac9{10}.$$