Menu
Three N*N matrices A,B,C are given. C is the same as the product of A and B except that exactly one element is wrong. The naive algorithm to find it out requires N^3 time. Can we do faster than that?
366
The product of two matrices can be computed by multiplying elements of the first row of the first matrix with the first column of the second matrix then, add all the product of elements. Continue this process until each row of the first matrix is multiplied with each column of the second matrix.
For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.
You can only multiply two matrices if their dimensions are compatible , which means the number of columns in the first matrix is the same as the number of rows in the second matrix. If A=[aij] is an m×n matrix and B=[bij] is an n×p matrix, the product AB is an m×p matrix.
Take a vector v = (1 1 1 1 ... 1)T, and calculate: u = Cv - A(Bv).
u is equal to (C-AB)v, and therefore it will have zeroes in all elements except one. The index of this element corresponds to the row index where C is different from AB. The value of the element (a) is the value of the nonzero element in C-AB.
To find the column index, you can repeat this with the vector v2 = (1 2 3 4 ... n)T. Now the value of the nonzero element is ac, where a is the value we calculated before and c is the column index.
Since we only do a few matrix*vector multiplications, the running time is O(n^2).
64
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
