Hi! I've encountered a matrix problem when designing an algorithm, which I cannot seem to figure out. I have a (square) matrix with the following properties:

j<k → a_{ij}<a_{ik}, a_{ji}<a_{ki}

a_{ij}≠a_{kl} unless i=k, j=l

That is, elements are strictly increasing along rows and columns, and all elements are unique.

Now, I want to do a fast search for an element in this matrix. So I divide it into four square submatrixes of 1/4 the size (taking care of odd size if needed). My thinking is that the interval of elements in a given submatrix is bounded by the upper left and lower right elements.

$\left(\begin{array}{ccccc} a_{11} & a_{12} & | & a_{13} & a_{14} \\\\ a_{21} & a_{22} & | & a_{23} & a_{24} \\\\ -&-&+&-&- \\\\ a_{31} & a_{32} & | & a_{33} & a_{34} \\\\ a_{41} & a_{42} & | & a_{43} & a_{44} \\\\ \end{array}\right)$

So, in this example (I can't get the array environ to draw lines, so it looks kinda ugly), I'd check interval a11 to a22, then a13 to a24, a31 to a42 and a33 to a44, and then recursivly checking until the size of the submatrix is 1x1.

My intuition tells me I would at most have to check two submatrixes at any step (ie there are at most two intervals which could contain a given number). However, I can only seem to prove that there are at most three. Am I wrong, and this is the best possible?