Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find the single wrong element in matrix product?

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?

like image 366
user2249675 Avatar asked Aug 26 '14 11:08

user2249675


People also ask

How do you find the product of a matrix?

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.

What is the product of 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.

What is the general rule of matrix multiplication?

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.


1 Answers

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).

like image 64
interjay Avatar answered Oct 12 '22 22:10

interjay