1

How can I prove that at least one value of a square matrix is equal or more than its neighbors in the matrix?

I know that in the case where all the values are the same, then all of the values fullfill the condition.

To give some context, I'm analyzing 4 algorithms that find one value of a square matrix which is equal or more than its neighbors (The value above, the value below, the value at the left, and the value at the right) by recursion, and after a lot of attempts, I haven't got a matrix where I couldn't find a "peak" (trying with random values or by putting the worst-case scenario for each algorithm).

Is there a theorem that explains this or anything I can use to prove that there is at least one value in a square matrix that is equal or more than its neighbors?

To give an example of what I'm trying to say: $$ \begin{bmatrix} 1 & 5 & 9\\ 4 & 1 & 0 \\ 1 & 8 & 4 \end{bmatrix} $$ In this case, both 9, 8 and the first 4 are the "peaks", since none of their neighbors are more than them.

Programmer Failure
  • 35
  • 11
    I mean, one entry of the matrix will be the largest. –  Jun 10 '20 at 00:56
  • @Gae.S. Look at the example matrix. Both 4 and 8 are values that satisfy the condition that none of their neighbors are more than them – Programmer Failure Jun 10 '20 at 01:03
  • I think what @Gae S. is trying to say is that if you look at all the numbers in the matrix, and take the largest of those, then the matrix entry containing that number will be larger than all its neighbors (because it is larger than every element of the matrix). – Bolton Bailey Jun 10 '20 at 01:06
  • 3
    Are you trying to find all entries in the matrix that satisfy your condition, or prove that at least one does? The latter (which is what you put in the title, and repeated throughout the body of your question) is trivial, as pointed out by the comment of Gae.S. – YiFan Tey Jun 10 '20 at 01:07

0 Answers0