Probabilistischer Test der Matrixmultiplikation mit einseitigem Fehler

7

Gegeben drei Matrizen wollen wir testen , ob AB \ neq C . Angenommen, die arithmetischen Operationen + und - benötigen eine konstante Zeit, wenn sie auf Zahlen aus \ mathbb {Z} angewendet werden .A,B,CZn×nABC+Z

Wie kann ich einen Algorithmus mit einseitigem Fehler angeben, der in O(n2) wird, und seine Richtigkeit beweisen?

Ich habe es jetzt mehrere Stunden lang versucht, aber ich kann es nicht richtig machen. Ich denke, ich muss die Tatsache nutzen, dass für jedes xZn höchstens die Hälfte der Vektoren s \ in S = \ left \ {1, 0 \ right \} ^ n x \ cdot ssS={1,0}n erfüllt xs=0 , wobei xs das Skalarprodukt i=1nxisi .

Warteschlange
quelle
1
Im letzten Absatz: Sie benötigen "für jedes x ungleich Null ", was offensichtlich, aber für eine Lösung entscheidend ist.
Tsuyoshi Ito

Antworten:

4

Wenn AB=C , dann ist A(Bx)=Cx für alle Vektoren x . Generieren Sie zufällig Vektoren und überprüfen Sie diese. Dies ist als Freivalds-Algorithmus bekannt . Wikipedia hat Details.

rgrig
quelle
Aber ich brauche einen einseitigen Fehleralgorithmus. Kann mir jemand helfen?
Warteschlange
2
Was lässt Sie denken, dass dies nicht einseitig ist? (Es ist.)
Rgrig