Learning a term position by it's value in a matrix

Question

Suppose we have a matrix with $n$ columns and $m$ rows ($n,m$ can be arbitrary). The following could be an example of the matrix:

$$\begin{bmatrix} 0&1&2&p \\ 3&4&p&5 \\ 6&p&7&8 \\ p&9&10&11 \\ 12&13&14&p \\ \ldots&\ldots &\ldots&\ldots\end{bmatrix}$$

I think you can notice the pattern by now. What I'm trying to figure out is: Given a value (number, not $p$) in the matrix (which is obviously, unique) I want to return the position, $(i,j)$ of the term.

For example, $\text{Pos}(5) = (1, 3)$. Basically, I'm trying to look for a simple formula to do that.

I'd be glad for help,

Thanks in advance.

Answer 1

NOTE: By the Division Theorem, for any natural numbers $a$ and $b$, we have unique integers $q$ and $0 \leq r < b$ such that $a=qa+r$. $a \ \% \ b$ represents $r$. For example, $5 \ \% \ 3=2$ and $7 \ \% \ 4=3$.

Let's say you took all of the $p$s out so that you had a $m \times (n-1)$ matrix. Clearly, the answer to $\text{Pos}(N, n)$ is now the following:

$$\text{Pos}(N, n)=\left(\left\lfloor \frac N {n-1} \right\rfloor, N \ \% \ (n-1)\right)$$

This might take a while to understand, but try plugging in some $N$s and $n$s so you can see why this is true.

Now, we need to insert the $p$s. However, notice how the $p$s are inserted in row $r$:

• $r \ \% \ n=1$ implies $p$ is in column $n-1$
• $r \ \% \ n=2$ implies $p$ is in column $n-2$
• $r \ \% \ n=3$ implies $p$ is in column $n-3$
• $r \ \% \ n=s$ implies $p$ is in column $n-s$
• • UNLESS $r \ \% \ n=0$, in which case $p$ is in column $0$

Thus, let $\text{Pcolumn}(r, n)=n-(r \ \% \ n)$ is $r \ \% \ n \neq 0$ and $\text{Pcolumn}(r, n)=0$ otherwise. Therefore, we have a function $\text{Pcolumn}$ that tells us where the $p$ is.

Thus, once we insert the $p$, none of the elements row changes, but if the element's column is greater than or equal to $\text{Pcolumn}(r, n)$ where $r$ is the row that the element is in, then we need to increase the column by $1$ in order to account for the $p$.

We already figured out that given $N$ and $n$, $r=\left\lfloor \frac N {n-1} \right\rfloor$ and that the column $N$ was originally in was $N \ \% \ (n-1)$. Therefore, the following Boolean expression tells us if the original column is greater than or equal to the column p will be inserted in:

$$(N \ \% \ (n-1)) \geq \text{Pcolumn}\left(\left\lfloor \frac N {n-1} \right\rfloor, n\right)$$

Let $\text{IncreaseByOne}(N, n)$ be a function that returns $1$ if the above is true and $0$ otherwise. This way, we can add this to the column in order to account for the inserted $p$. Thus, here is our new $\text{Pos}(N, n)$ formula:

$$\text{Pos}(N, n)=\left(\left\lfloor \frac N {n-1} \right\rfloor, (N \ \% \ (n-1))+\text{IncreaseByOne}(N, n)\right)$$

It's a bit complicated and takes two functions ($\text{Pcolumn}(r, n)$ and $\text{IncreaseByOne}(N, n)$) in order to define the whole thing, but it is a formula none the less.