Graphs for an adjacency matrix in Z_2

[Merciadri Luca]

Hi,

Let us consider the matrix $S$ of a Sudoku, $S$ being $n\times n$,
with $n$ being a square (i.e. 9, 16, 25, etc.).
Let's say that $S_{i,j}:=S_{i,j}\pmod{2}$, i.e. we now consider $S$
with all its elements being taken in $1/\mathbb Z_2$ (i.e. the 2-adic
numbers), for $1\leq i\leq n$, $1\leq j\leq n$.

We now consider $S$ as the adjacency matrix of a graph $G$.

I know have the two following questions (we consider that $S$ is the
previous $S$ taken in $1/\mathbb Z_2$, as explained before):

1. The graph done from $S$ is often not simple, as it contains at
least one loop ($S$ has not often all its diagonal elements equalling
$0$). But what can we say about ``often?:'' are there correct (and
evidently completed) Sudoku matrices leading to, for their
representation in $1/\mathbb Z_2$, a diagonal full of zeros (and thus
a trace equalling $0$)?

2. Is it possible for $S$ to be symmetric, the previous $S$ being a
correct (and evidently completed) Sudoku matrix? If it is so, G is non-
oriented.

It is difficult to answer correctly to these questions without any
numerical (i.e. computing) help.

Is there somebody here having propositions about these two problems?

Thanks.

[Merciadri Luca]

Note that:

* This is not $1/\mathbb Z$, but $\mathbb Z/2\mathbb Z$,
* By "2-adic numbers," I was speaking (erroneously) about the integers
modulo 2. Evidently, the $S_{i,j}$ are taken modulo 2.

Thanks to Arturo Magidin for this correction.

[Ask me about System Design]

Consider the case of n=4. It is easy to construct a
sudoku using digits 1,2,3, and 4 such that, modulo 2,
the derived adjacency matrix is that of a 4-cycle. So
for n=2 the answer is yes to both questions.

For odd n, using the labelling starting from 1 to n,
there will be an odd number of 1's in the resulting 0-1
matrix, so if there is a sudoku that has a symmetric
derived 0-1 matrix, that matrix will have a non-zero
trace. This difficulty disappears if the labels range
from 0 to n-1.

One can use various constructions for matrices to build
larger matrices, such as Hadamard product. Given two
p by p matrices (or non-square) A and B, A prod B has
something like a_ij*b_kl for the entry in the i*p+k row
and j*p +l column. The matrix above can be used in a
similar fashion to create a larger matrix if you replace
a_ij*b_kl with (a_ij,b_kl), a base p representation for
the number from 1 to p^2. Details need to be worked out
to encode the desired result correctly. With such a
construction, I believe that the answer to both your
questions is yes for n a power of 4.

Note that any such (directed) graph above will be a
regular graph on n vertices with degree ceil(n/2), or
floor(n/2), depending on the symbol set. The literature
on such adjacency matrices and graphs is extensive; you
might look at existing constructions and see which have
or preserve the sudoku relation, which is having the
right number and position of 1's in certain submatrices.

Gerhard "Ask Me About System Design" Paseman, 2009.10.31