How can I quickly judge whether matrix A is the inverse matrix of B?

How can I quickly judge whether matrix A is the inverse matrix of B?

This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution may be related to randomized algorithms.

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random vectors. This method reduces the time complexity from $O(n^{2.3729}$) (regular matrix multiplication) to $O(n^2)$ with high probability. In your case, the matrices $A$ and $B$ would be the matrices you are given, and the matrix $C$ would be the identity matrix.

StackExchange Computer Science Q#140775, answer score: 24