1
$\begingroup$

Suppose you have a square matrix of arbitrary width $m$ like: $$ \begin{matrix} 0.51 & 0.76 & 0.71 & 0.01 \\ 0.00 & 0.42 & \cdots & 1.00 \\ \vdots & \vdots & \ddots \\ 0.34 & 0.84 & \ & 0.33 \\ \end{matrix} $$ Where each entry is some real number in the range $[0,1]$. Let's say this matrix has a property called sharpness, defined as follows:

For each entry in the matrix, sum up the absolute values of the differences between its value and the value of its direct neighbors. For example, in the matrix above, for the 2nd row, 2nd column entry, the value of which is 0.42, this sum $S_{22}$ would look like: $$S_{22}=|0.42-0.51|+|0.42-0.76|+|0.42-0.71|+|0.42-0.00|\ ...=\text{Sum for 2nd row, 2nd column}$$ Now take the sum of all these sums for each entry: $$\text{Sharpness}=\sum_{i,\ j}^m{S_{ij}}$$ And that sum is the sharpness.

What matrix has the greatest possible sharpness?

Note: this is a question I've thought of while working on images sharpness, (acutance, more precisely), hence the use of the word sharpness here. If you imagine each entry in this matrix as representing the brightness of a pixel, the definition of sharpness makes intuitive sense, as "sharper" images would have greater differences in brightness between many neighboring pixels.

$\endgroup$
1
  • $\begingroup$ Hmm...my immediate guess would be that this would be the matrix alternating 0's and 1's in a checkerboard fashion, but I would imagine that this would be nontrivial to prove. Of course, if we don't consider diagonal neighbors in the formula for sharpness, this would be obvious... $\endgroup$
    – boink
    Jun 12, 2020 at 17:30

1 Answer 1

4
$\begingroup$

First of all, we note that for a set of numbers $x_1, x_2, \ldots, x_n$, the value $K$ that minimises the quantity $$|x_1 - K| + |x_2 - K| + \ldots + |x_n - K| + |K - x_1| + |K - x_2| + \ldots + |K - x_n|$$ is the median of the set of numbers, and that this quantity increases the further that $K$ is from the median. (I'll leave this to you to prove.) As a result, we note that if $K$ is restricted to the range $[a, b]$, the value above will be maximised when $K = a$ or $K = b$.

Now consider any $m \times m$ matrix, and suppose that it has the maximum sharpness possible. Suppose that any element of the matrix is in the range $(0, 1)$; that is, it is neither $0$ nor $1$. Then, using the fact above, the sharpness of the matrix will either remain the same or increase if we change this element to $0$ or $1$ (that is, one of these possible choices will increase the sharpness). If we repeat this for every element of the matrix, we now know that there exists a matrix with maximal sharpness which contains only $0$s and $1$s. (There might be more than one matrix with largest possible sharpness, so we'll focus on just finding one for now.)

Now consider any $2\times 2$ sub-matrix $$\begin{bmatrix} a & b \\ c & d \end{bmatrix}.$$ We note that at least two of $a-b$, $a-c$, $a-d$, $b-c$, $b-d$, $c-d$ are $0$. The overall sharpness is equal to twice the total number of pairs of adjacent values in the matrix, minus twice the total number of "edges" removed in each $2\times 2$ sub-matrix (counting duplicate edges only once, and diagonals count as edges). Thus, each $2\times 2$ sub-matrix contributes a total of 2 removed edges, but this is effectively reduced to lower if it shares a removed edge with an adjacent matrix. With some reasoning it can be seen that the overall number of edges removed between all such sub-matrices, counting duplicates only once, is at least $m(m-1)$ (I'll leave as an exercise to prove rigorously). Thus the maximum possible sharpness is $$2(3m-2)(m-1),$$ and this is attainable e.g. via the following configuration: $$\begin{bmatrix}0 & 0 & \cdots & 0 \\ 1 & 1 & \cdots & 1 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ \end{bmatrix}.$$

(Note that a checkerboard matrix does not in fact maximise sharpness, for any $m > 2$.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .