Checking Matrix Multiplication three n xn matrices A,B,C: A X B 名 C Freivald's Algorithm: pick a uniform random r∈{0，l}n; check whether A(Br)=Cr; time:O(n2) if AB C:always correct ifAB≠C:• three n × n matrices A, B,C: Checking Matrix Multiplication A × B = C ? Freivald’s Algorithm: pick a uniform random ; check whether ; r ∈ {0,1}n A(Br) = Cr time: O(n if AB = C: always correct 2 ) if AB ≠ C: