Smallest Non-negative number in a matrix

Question

There is a question I encountered which said to fill an $N \times N$ matrix such that each entry in the matrix is the smallest non-negative number which does not appear either above the entry or to its left. That is for $N = 6$ the matrix looks like this:

$$\begin{array}{} 0&1&2&3&4&5\\ 1&0&3&2&5&4\\ 2&3&0&1&6&7\\ 3&2&1&0&7&6\\ 4&5&6&7&0&1\\ 5&4&7&6&1&0 \end{array}$$

I was asked to find a function such that given row and column I can calculate the value at that point i.e

$$f(\text{row}, \text{column}) = \text{Matrix}[\text{row}][\text{column}]$$

I was looking at Nimbers and found the matrix in it exactly similar to it. There was also given a formula to calculate to calculate Matrix[row][column] which was row XOR column (XOR is bitwise exor).

However I was able to get the answer I am still unable as to how to arrive at the solution i.e. the proof that each entry in the matrix is the smallest non-negative number which does not appear either above the entry or to its left is equal to row XOR column.

Answer 1

Denote by $a(m,n)$ the entry in row $m$, column $n$ of the matrix. By definition

$$a(m,n)=\operatorname{mex}\big(\{a(k,n):k<m\}\cup\{a(m,k):k<n\}\big)\;,\tag{1}$$

where $\operatorname{mex}(A)$ is the smallest non-negative integer not in $A$. The problem is to show that when all of the numbers involved are expressed in binary, $a(m,n)=m\oplus n$, the bitwise exclusive OR of $m$ and $n$. We’ll do this by induction on $m+n$. It’s certainly true when $m+n=0$: $a(0,0)=0=0\oplus 0$. Now assume let $m,n\in\mathbb{N}$, and assume that it’s true for all $m',n'\in\mathbb{N}$ with $m'+n'<m+n$; we’ll show that it’s true for $m$ and $n$.

Let $s=m\oplus n$. To show that $s=a(m,n)$ as defined by $(1)$, I need to show two things:

1. if $0\le t<s$, $t\in\{a(k,n):k<m\}\cup\{a(m,k):k<n\}$; and
2. $s\notin\{a(k,n):k<m\}\cup\{a(m,k):k<n\}$.

To show (1), suppose that $0\le t<s$, let $d=t\oplus s$, and let $k$ be the number of bits in $d$, so that $2^{k-1}\le d<2^k$. That is, $d$ has a $1$ in the $k$-th position counting from the right. Since $t<s$, this implies that $t$ has a $0$ in the $k$-th position, and $s$ has a $1$ there. Since $s=m\oplus n$, exactly one of $m$ and $n$ must have a $1$ in the $k$-th position; without loss of generality assume that $m$ has a $1$ in the $k$-th position. Then $d\oplus m$ has a $0$ in the $k$-th position and is identical to $m$ in positions to the left of the $k$-th position, so $d\oplus m<m$. Let $k=d\oplus m$; then $$k\oplus n=d\oplus m\oplus n=d\oplus s=t\oplus s\oplus s=t\;.$$ Moreover, $k<m$, so $k+n<m+n$, and therefore $t=k\oplus n=a(k,n)$ by the induction hypothesis. This completes the proof of (1).

To show (2), suppose, on the contrary, that $s\in\{a(k,n):k<m\}\cup\{a(m,k):k<n\}$. Without loss of generality we may assume that $s\in\{a(k,n):k<m\}$. Let $k<n$ be such that $s=a(k,n)$. Clearly $k+n<m+n$, so by the induction hypothesis we have $$k\oplus n=a(k,n)=s=m\oplus n\;,$$ and therefore $$k=k\oplus n\oplus n=m\oplus n\oplus n=m\;,$$ contradicting the choice of $k$. Thus, (2) also holds, and $m\oplus n=a(m,n)$.

Answer 2

Lets say you selected a row (say $A$ represented using n-bits). Now, for all the $2^n$ columns (say $B$) you select, you will get different bit strings, hence different numbers.

For a particular $A$, $A\oplus B$ is distinct for distinct values of $B$. Thats why you get different numbers and that too within the range of n-bit. The same is not true for AND or OR operators.

A  B  A xor B    A and B   A or B
0  0     0          0         0
0  1     1          0         1
1  0     1          0         1
1  1     0          1         1

Here you notice that if you take bitwise AND, then for a particular row you can get same values for different columns. For example, for $5^{th}$ row ie $(101)_2$ will have a value 5 $(101)_2$ at $5^{th}(101)_2$ as well as $7^{th}(111)_2$ column.

So, A[5][5] = A[5][7] = 5 which is not required. This problem comes because of 0 in the bitstring.

Similarly for OR, this repetition will come because of 1 in the bitstring.

A[5][5] = A[5][4] = A[5][1] = A[5][0] = 5

So, you can now see why bitwise XOR is used.

But its not using the smallest possible value. In your array, you can see that 4 and 5 are missing in $3^{rd}$ and $4^{th}$ rows; and 2 and 3 in $5^{th}$ and $6^{th}$ rows. This is because you have 6 rows and columns for which you need 3 bits which can accommodate 8 values.

\begin{array}{} 0&1&2&3&4&5\\ 5&0&1&2&3&4\\ 4&5&0&1&2&3\\ 3&4&5&0&1&2\\ 2&3&4&5&0&1\\1&2&3&4&5&0 \end{array}

To get the minimum values, you can just shift the values while stepping onto the next row.

Answer 3

I really like this question. I saw it on a website a year or so ago, closed the page so that I wouldn't see the answer, and then never found it again. I solved it by proving by induction that $$ f(4i+r, 4j+s) = f(r,s)+4f(i,j)$$ --- this relation is apparent if you draw enough of the matrix. Let me know if you would like the details. Once you have this relation, you can apply it repeatedly to get

$$f(\sum a_i 4^i, \sum b_i 4^i) = \sum h(a_i,b_i) 4^i$$

where $h$ is a the function determined by the first 4x4 block of the matrix. This explains why it is possible to think of f as a "bitwise" operation.

Answer 4

It's the XOR function, and you can prove it by induction on the bit length. For $0\leq x,y<2^n$ with binary expansions $$ x=\sum_{i=0}^{n-1} x_i 2^i, \quad y=\sum_{i=0}^{n-1} y_i 2^i \quad \text{for} \quad x_i, y_i \in \{0,1\}, \quad \text{and} \quad x,y \in I_n=\{0,1,\dots,2^n-1\}, $$ we start by assuming inductively that $$ f(x,y) = XOR(x,y) \equiv \sum_{i=0}^{n-1} x_i y_i 2^i $$ and observe (also as part of our inductive hypothesis) that each row and column (where one of $x$ or $y$ is fixed, but the other varies freely over $I_n$) contains precisely the values $I_n$ (once each).

Now for the inductive step, we let $x_n,y_n\in\{0,1\}$ be arbitrary, and note first that the base block $(x_i,y_i)=(0,0)$ is our inductive hypothesis. Next, note that for $(x_i,y_i)=(0,1)$ and $(x_i,y_i)=(1,0)$, all of the values in $I_n$ are already taken and so the minimality rule will assign values to $f$ starting with $2^n$ rather than $0$, filling these blocks with the values $I_{n+1} \setminus I_n = \{2^n,2^n+1,\dots,2^{n+1}-1\}$. Furthermore, these values will be assigned within each block in the same order as they were in the base block. Finally, the block $(x_i,y_i)=(1,1)$ will match the base block, since its predecessors (the two non-base, inductive blocks already considered) used the values from $I_{n+1} \setminus I_n$ but left those from $I_n$ vacant. Thus, the minimality criterion is additive: $$ f(2^i x_i + x, 2^i y_i + y) = 2^i XOR(x_i,y_i) + f(x,y) = 2^i x_i y_i + f(x,y) $$ which proves the inductive step.

The key insight that makes this proof work is that the blocks of $(x,y)$ for $0 \leq x,y < N$ are "full" (containing each value from $0$ to $N-1$ in each row and column) iff $N=2^n$ is a power of two.

Answer 5

All these proofs rely on the observation that this question is related to the bitwise XOR operator (after a few examples, this is very easy to see). However, I still cannot see the intuitive connection between the original problem and the Nimbers. Does anyone have a clear insight on this?