Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 → aij<aik, aji<aki
aij≠akl 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?

share|improve this question

closed as no longer relevant by Scott Morrison Nov 22 '09 at 18:41

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
you should change that --> in the first line of maths to "if", as I'm pretty sure you don't mean "implies". –  Scott Morrison Nov 20 '09 at 6:41
    
Carlpett seems to have withdrawn his question (see his answer below), so I'm closing. –  Scott Morrison Nov 22 '09 at 18:42
add comment

2 Answers 2

Note that even if you could eliminate two of the submatrices at each step, you would be left with a Θ(N1/2) algorithm (where N=n*n is the total number of entries in the matrix). Fortunately, there's a simple Θ(N1/2) algorithm anyway:


def search(item):
    (i, j) = (0, n-1);
    while i < n and j >= 0:
        if a[i,j] == item:
            return (i,j)
        else if a[i,j] > item:
            j = j-1
        else 
            i = i+1
    return Not_Found;

I'm not sure it's the fastest possible, but it's probably at least as good as whatever you were trying.

share|improve this answer
add comment

Nevermind, came up with a counterexample. (Trivial too, disheartenly enough :( ) One cannot assume that there will be at most two submatrixes with the sought interval. It can be seen by assigning a large value for a_22, and smallest possible values for the first row and column. Then, there will be numbers such that it lies in the intervals of all submatrixes but the lower right one.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.