# Prove that search in matrix takes mor than n comparisons

Let us call matrix $A$ ascending if $A_{kl}\ge A_{ij}, i \le k, j \le l$ for every $k$ and $l$. Given a number $x$ prove that determining whether $x$ is in an ascending matrix or not takes more than $n$ comparisons.

I understand that finding number in sorted array takes at least $\log(n)$ comparisons, but I don't know where to start with the matrix.

It takes at least $n$ comparisons to check whether a given number $x$ is contained in an unsorted list $L = (x_1, x_2, \ldots, x_n)$ with $n$ elements. Create a matrix $A$ by writing the elements from $L$ on the diagonal $(A_{n1}, A_{(n-1)2}, \ldots, A_{2(n-1)},A_{1n})$. Fill the upper left triangle of the matrix with a small number $a$ which is smaller than all elements of $L$, and the lower right triangle with a large number $b$ which is larger than all elements of $L$. You obtain the following ascending matrix $$A = \begin{pmatrix} a & \cdots & \cdots & a & x_n \\ \vdots & & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & x_{n-1} & b \\ \vdots & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & \vdots \\ a & x_2 & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & & \vdots \\ x_1 & b & \cdots & \cdots & b \end{pmatrix}$$ If you could check whether $A$ contains $x$ with less than $n$ comparisons, then you could also perfrom this check on $L$. This is not possible.