Qual é a estrutura mais geral na qual a verificação do produto da matriz pode ser feita no tempo

Em 1979, Freivalds mostrou que a verificação de produtos matriciais em qualquer campo pode ser feita em tempo aleatório $O(n^2)$. Mais formalmente, dadas três matrizes A, B e C, com entradas de um campo F, o problema de verificar se AB = C possui um algoritmo de tempo aleatório .$O(n^2)$

Isso é interessante porque o algoritmo mais rápido conhecido para multiplicar matrizes é mais lento que isso, portanto, verificar se AB = C é mais rápido que calcular C.

Quero saber qual é a estrutura algébrica mais geral sobre a qual a verificação de produtos matriciais ainda possui um algoritmo de tempo (randomizado). Como o algoritmo original funciona em todos os campos, acho que também funciona em todos os domínios integrais.$O(n^2)$

A melhor resposta que pude encontrar para essa pergunta foi em Equivalências subcúbicas entre problemas de caminho, matriz e triângulo , onde eles dizem que "a verificação do produto da matriz por anéis pode ser feita no tempo aleatório [BK95]". ([BK95]: M. Blum e S. Kannan. Criando programas que verificam seu trabalho. J. ACM, 42 (1): 269–291, 1995.)$O(n^2)$

Primeiro, os anéis são a estrutura mais geral na qual esse problema possui um algoritmo randomizado? Segundo, eu não conseguia ver como os resultados de [BK95] mostram um algoritmo de tempo em todos os anéis. Alguém pode explicar como isso funciona?$O(n^2)$$O(n^2)$

Aqui está um argumento rápido sobre por que funciona sobre anéis. Dadas as matrizes , B , C , verificamos A B = C escolhendo um vetor de bits aleatório v e verificando se A B v = C v . Isso passa claramente se A B = $A$$B$$C$$A B = C$$v$$ABv = Cv$$AB = C$ .

Suponha que e A B v = C v . Vamos D = A B - C . D é uma matriz diferente de zero para a qual D v = 0 . Qual é a probabilidade de que isso ocorra? Seja D [ i ' , j ' ] uma entrada diferente de zero. Por suposição, ∑ j D [ i ′ , j ] v [ j ] = . Com probabilidade$AB \neq C$$ABv = Cv$$D = AB - C$$D$$Dv = 0$$D[i',j']$$\sum_{j} D[i',j] v[j] = 0$ , v [ j ' ] = $1/2$$v[j'] = 1$ , então temos

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

Qualquer anel em sua operação de adição é um grupo aditivo, portanto, existe um inverso único de , ou seja, - D [ i ' , j ' ] . Agora, a probabilidade do mau evento - D [ i ' , j ' ] = Σ j ≠ j ' D [ i ' , j ] v [ j ] é no máximo 1 $D[i',j']$$-D[i',j']$$-D[i',j'] = \sum_{j\neq j'} D[i',j] v[j]$$1/2$. (Uma maneira de ver isso é o "princípio das decisões diferidas": para que a soma seja igual a , pelo menos um outro D [ i ' , j ] deve ser diferente de zero. Portanto, considere o v [ j ] corresponde a essas outras entradas diferentes de zero. Mesmo se definirmos todos esses v [ j ] , exceto um deles de maneira ideal , ainda há probabilidade igual para o último ser 0 ou$-D[i',j']$$D[i',j]$$v[j]$$v[j]$$0$$1$, Mas ainda apenas um desses valores poderia fazer a soma final igual .) Assim, com probabilidade de pelo menos 1 / 4 , encontramos com sucesso que D v ≠ 0 , quando D é diferente de zero. (Nota v [ j ] e v [ j ′ ] são escolhidos independentemente para j ≠ j $-D[i',j']$$1/4$$Dv \neq 0$$D$$v[j]$$v[j']$$j \neq j'$ .)

Como você vê, o argumento acima depende da subtração. Portanto, não funcionará (por exemplo) em semirrutas comutativas arbitrárias. Talvez você possa relaxar as propriedades multiplicativas da estrutura algébrica e ainda obter o resultado?