Algorithm on n-bit matrix

Question

Two function P1, P2 are given that take input n-bit x, and calculate y1=A1*x, y2=A2*x. A1 and A2 is n*n bit matrix. these two functions return n-bit array y1,y2. we doesn't know any information about these matrices but know A1 and A2 is the same except one slot (i,j). (i and j are unknown for us). we can call P1 and P2 for different value of x and then compare the output of these two function. I want to find that with how many calls we can find i, j?

In Short answer our book wrote: Log n calls. any hint or idea? thanks to all.

Edit: someone says, at first x be a column matrix of "1's". and calculate y1 and y2 and find the row that different. then x be a matrix that n/2 up elements be "1's" and n/2 bottom element be "0's". if y1 and y2 be equal difference is in n/2+1 to n else be 1 to n/2...

Answer 1

You can do it in two calls if you could transpose A1 and A2:

You can determine i by doing one call an mainly check which entry in y1 and y2 differs. That will give you i.

Transpose A1 and A2, do same thing, the entry which differs is the index of j.

Without transpose: you still do one multiplication to determine i. Now, just do a "binary search" where your searching area will be identified by 1 in the entry of your x vector.

First step: fill half of x vector with 1, the other with 0, do the multiplication, check if the entry at index i is different, if it isn't, then your j is somewhere in the 2nd half, if it is different, then it is in your first half (the one you felt with 1)

Second step: split one of the selected parts from previous step in two, have one half with 1 and the other with 0, repeat same logic until you are left with exactly one entry. That one is the index of your j

Since you are splitting always in 2, you will have exactly log(n) calls.

Determine `i` entry by doing one call. (trivial)
length = n/2
start = 0
while(not found)
    var x[start..start+length) = 1 (0 all otter entries)
    do function calls
    if result1[i] == result2[i]
        start = 0
        length = length/2
    else
        start = length+1
        length = length/2
    if length == 1
        found.
        start is your index j