Apa struktur paling umum di mana verifikasi produk matriks dapat dilakukan dalam waktu

Pada tahun 1979, Freivalds menunjukkan bahwa memverifikasi produk matriks atas bidang apa pun dapat dilakukan dalam waktu secara acak . Lebih formal, diberikan tiga matriks A, B, dan C, dengan entri dari bidang F, masalah memeriksa apakah AB = C memiliki algoritma waktu O ( n 2 ) acak .$O(n^2)$$O(n^2)$

Ini menarik karena algoritma yang paling cepat diketahui untuk mengalikan matriks lebih lambat daripada ini, jadi memeriksa apakah AB = C lebih cepat daripada komputasi C.

Saya ingin tahu apa struktur aljabar paling umum di mana verifikasi produk matriks masih memiliki algoritma waktu (acak). Karena algoritme asli berfungsi di semua bidang, saya kira itu berfungsi di semua domain integral juga.$O(n^2)$

Jawaban terbaik yang dapat saya temukan untuk pertanyaan ini adalah dalam Subkubis Kesetaraan Antara Jalur, Matriks, dan Masalah Segitiga , di mana mereka mengatakan "verifikasi produk matriks atas cincin dapat dilakukan dalam waktu acak [BK95]." ([BK95]: M. Blum dan S. Kannan. Merancang program yang memeriksa pekerjaan mereka. J. ACM, 42 (1): 269–291, 1995.)$O(n^2)$

Pertama, apakah cincin merupakan struktur paling umum di mana masalah ini memiliki algoritma acak ? Kedua, saya tidak bisa melihat bagaimana hasil [BK95] menunjukkan algoritma waktu O ( n 2 ) di semua dering. Adakah yang bisa menjelaskan cara kerjanya?$O(n^2)$$O(n^2)$

Berikut ini argumen singkat mengapa ia bekerja di atas dering. Diberikan matriks , B , C , kami memverifikasi A B = C dengan memilih vektor bit acak v , lalu memeriksa apakah A B v = C v . Ini jelas melewati jika A B = C .$A$$B$$C$$A B = C$$v$$ABv = Cv$$AB = C$

Misalkan dan A B v = C v . Biarkan D = A B - C . D adalah matriks nol untuk yang D v = 0 . Berapa probabilitas hal ini terjadi? Biarkan D [ i ′ , j ′ ] menjadi entri yang bukan nol. Dengan asumsi, ∑ j D [ i ′ , j ] v [ j ] = $AB \neq C$$ABv = Cv$$D = AB - C$$D$$Dv = 0$$D[i',j']$$\sum_{j} D[i',j] v[j] = 0$. Dengan probabilitas , v [ j ' ] = 1 , jadi kita harus$1/2$$v[j'] = 1$

.$D[i',j'] + \sum_{j\neq j'} D[i',j] v[j] = 0$

Setiap cincin di bawah operasi Selain adalah kelompok aditif, sehingga ada terbalik unik , yaitu, - D [ i ' , j ' ] . Sekarang, probabilitas dari peristiwa buruk - D [ i ' , j ' ] = Σ j ≠ j ' D [ i ' , j ] v [ j ] adalah paling 1 /$D[i',j']$$-D[i',j']$$-D[i',j'] = \sum_{j\neq j'} D[i',j] v[j]$$1/2$. (Salah satu cara untuk melihat ini adalah "prinsip keputusan yang ditangguhkan": agar penjumlahannya sama , setidaknya satu D lainnya [ i ′ , j ] harus nol, jadi pertimbangkan v [ j ] sesuai dengan entri bukan nol lainnya ini. Bahkan jika kita mengatur semua v [ j ] ini kecuali untuk salah satu dari mereka secara optimal , masih ada probabilitas yang sama untuk yang terakhir adalah 0 atau $-D[i',j']$$D[i',j]$$v[j]$$v[j]$$0$$1$, Tapi masih hanya satu dari nilai-nilai ini bisa membuat jumlah akhir sama untuk .) Jadi dengan probabilitas setidaknya 1 / 4 , kami berhasil menemukan bahwa D v ≠ 0 , ketika D adalah nol. (Catatan v [ j ] dan v [ j ′ ] dipilih secara independen untuk j ≠ j ′ .)$-D[i',j']$$1/4$$Dv \neq 0$$D$$v[j]$$v[j']$$j \neq j'$

Seperti yang Anda lihat, argumen di atas tergantung pada pengurangan. Jadi itu tidak akan berfungsi (misalnya) pada semut komutatif yang sewenang-wenang. Mungkin Anda bisa mengendurkan sifat multiplikasi struktur aljabar, dan masih mendapatkan hasilnya?