Checking Matrix Multiplication

The problem of Checking Matrix Multiplication is defined as follows: Given three matrices A $($m x n$),$ B

$($n x p$),$ and C $($m x p$),$ determine if C is the product of A and B $($i$.$e$.,$ C $=$ A $*$ B$).$ The traditional matrix

multiplication algorithms require multiplying all elements in the resulting matrix. However, there exists

a randomized algorithm called Freivald's Algorithm that can solve the problem with high probability

using fewer operations.

$($a$)$ Briefly describe the core idea behind Freivald's Algorithm and how it utilizes randomness to check

matrix multiplication.

$($b$)$ Specify and justify the type of the Freivald's Algorithm $($Las Vegas or Mont Carlo$)$

$($d$)$Discuss how the following aspects of Freivald's Algorithm are considered:

$$ Expected Running Time: Compared to the deterministic algorithm, what is the expected

running time $($average number of operations$)$ of Freivald's Algorithm?

$$ Trade$-$offs: Discuss the potential trade$-$offs between using a randomized algorithm like

Freivald's compared to a deterministic approach