Question: There is an N x N matrix with the property that each entry in the matrix is the smallest non-negative number, which does not appear either above the entry or to its left. Write a method to find the entry in a particular row and column.

For example, for N=8, we might have the matrix:

0 1 2 3 4 5 6 71 0 3 2 5 4 7 62 3 0 1 6 7 4 53 2 1 0 7 6 5 44 5 6 7 0 1 2 35 4 7 6 1 0 3 26 7 4 5 2 3 0 17 6 5 4 3 2 1 0

Answer: From the question statement, it is clear that the top left corner starts things off with 0 and the top row and the leftmost column are each completed with the positive integers 1,2,3,..., in order.

Secondly, if every time we fill another cell, we use the smallest non-negative integers that have not so far appeared in the same column and the same row, then it is impossible to get a repeated integer in either the same column or the same row. Square matrix of order n, in which every symbol occurs exactly once in each row and column of the array, is called latin square. So we can say that above matrix is a latin square in different setting.

Lets see if we can find some pattern in the sequence. If we write the matrix in binary number system an 8*8 matrix will look like below matrix:

^{n}square matrix in 4 parts of size 2

^{n-1}and call them as M

_{tl}, M

_{tr}, M

_{br}, M

_{bl}(top-left, top-right, bottom-left, bottom-right respectively), each of these sub-matrixes is a latin square in itself.

If we took the highest power of 2 from these values, we can also write this matrix as

_{tl}, M

_{tr}, M

_{br}, M

_{bl}) equal in size to the square on the previous step. M

_{tl}is the square from the previous step. Copy it into three other squares, and lastly add 1 (2

^{o}) to every element of M

_{tr}and M

_{bl}.

Now at every step for generating a square matrix of size 2

^{n+1}, we can expand the matrix by assuming that a corner square of size 2

^{n}(M

_{tl) }has been filled. Copy it into adjacent squares M

_{tr}, M

_{br}and M

_{bl}and add 2

^{n}to every element of M

_{tr}and M

_{bl}. Final relationship will be like shown below:

**How can we prove that resultant matrix has the required property?**

Lets prove it my using mathematical induction. We have seen that M

Since we assumed that M

For M

Now we can calculate value at any row and column in O(logN) time as on every step we can reduce the matrix size by half.

Assume that rows and columns starting with 0 as in C/C++. Let M

_{0}adhere to the property. Now assume that M_{N-1}follow the property, lets show that M_{N}also follow the same:Since we assumed that M

_{N-1}(i.e. M_{tl}for M_{N}) follows theis rule and entries of M_{tr}are formed by adding 2^{N-1}to M_{tl}. So M_{tr}is a latin square in itself. Also since elements from 0 to (2^{N-1}- 1) have already been used in M_{tl}, candidates for M_{tr}are only values greater than or equal to 2^{N-1}. So we can say that M_{tr}adheres to the given rule. Similar argument can be given for M_{bl}.For M

_{br}, we see that value for 0..(2^{N-1}-1) are not used in these row and column yet, We can use them and we used M_{tl}as it is. Hence we prove that M_{N }the given conditions.Now we can calculate value at any row and column in O(logN) time as on every step we can reduce the matrix size by half.

**Can we do it in constant time?**Assume that rows and columns starting with 0 as in C/C++. Let M

_{(m,n)}denotes the number that appears in the (m, n) cell. Since we can denote any number with addition of power of 2, lets saym = 2^{a}+ 2^{b}+ 2^{c}+ ... where a > b > c...

n = 2^{x}+ 2^{y}+ 2^{z}+ ... where x > y > z...

**If a = x:**then (m, n) lies in the M

_{br}square of the smallest square M

_{N}that contains (m, n). By dropping 2

^{a}from m and 2

^{x}from n, the point is moved into M

_{N-1}. So we don’t bother about a

^{th}and x

^{th}bit from m and n respectively.

**If a < x:**then (m, n) lies in the M

_{tr}square of the smallest square M

_{N}that contains (m, n). As we saw earlier, we can move it into M

_{N-1}by dropping 2

^{a}from m and add 2

^{a}to result. So we don’t bother about a

^{th}bit if it diffres.

**If a > x:**then (m, n) lies in the M

_{bl}square of the smallest square M

_{N}that contains (m, n). As we saw earlier, we can move it into M

_{N-1}by dropping 2

^{x}from n and add 2

^{x}to result. So we don’t bother about x

^{th}bit if it differs.

The process will continue while either m or n are not zero. Every time one of them has a binary bit which is 0 in the other, this bit is removed from the number but added to result. So we see that whenever any bit of m and n differs, we need to add it to result and just drop it if it’s same. In Boolean mathematics, XOR operator does the same. At the end of the day, m = n = 0 whereas result contains (m XOR n) of the original m and n. So finally

M_{(m,n)}= m^n

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
## 0 Comments

Post a Comment