Rank of Sudoku matrices

[Merciadri Luca]

Hi,

I am currently wondering if the rank $\rho$ of a Sudoku matrix ($n
\times n$) $S$ can verify
$\rho < n-1$.

It is clear that $\rho < n$ is possible: it suffices to take $\rho =
n-1$, which is achieved iff $\det(S)=0$, but $\rho <= n-2\equiv \rho <
n-1$ (as we work in $\mathbb Z$) is already more difficult to say.

Any idea? Currently, my strongest (i.e. the most exigent, thus leading
to the `smallest' [on the cardinality point of view] set of matrices
verifying the property) affirmation is that, for some Sudoku matrices,
$1 <= \rho <= n-1$. But can one give examples about matrices whose
rank would restrict this equality (i.e. giving a subset $\mathcal P$
of [1, n-1] such that $\mathcal P\neq [1, n-1]$)?

Thanks.

[Chip Eastham]

Post by Merciadri Luca
Hi,
I am currently wondering if the rank $\rho$ of a Sudoku matrix ($n
\times n$) $S$ can verify
$\rho < n-1$.
It is clear that $\rho < n$ is possible: it suffices to take $\rho =
n-1$, which is achieved iff $\det(S)=0$, but $\rho <= n-2\equiv \rho <
n-1$ (as we work in $\mathbb Z$) is already more difficult to say.
Any idea? Currently, my strongest (i.e. the most exigent, thus leading
to the `smallest' [on the cardinality point of view] set of matrices
verifying the property) affirmation is that, for some Sudoku matrices,
$1 <= \rho <= n-1$. But can one give examples about matrices whose
rank would restrict this equality (i.e. giving a subset $\mathcal P$
of [1, n-1] such that $\mathcal P\neq [1, n-1]$)?
Thanks.

For general (positive integer) n it is unclear
what you might mean by "Sudoku matrix" (which
conventionally requires n = 9).

A Sudoku matrix is a special case of a latin
square. I believe it is known that "cyclic"
latin squares of order n can have rank as low
as:

1 + SUM phi((p_i)^{j_i})

where n = PROD (p_i)^{j_i} is the (unique)
prime factorization and phi is the Euler phi
function. So for n = 3^2, phi(n) = 6 and
the above minimum rank is 7.

[On the rank of cyclic latin squares (1995)]
(W. C. Shiu and K. T. Fang)
http://www.informaworld.com/index/779107967.pdf

However this doesn't answer your question about
the minimum rank of Sudoku matrices, even for
n = 9.

regards, chip

[Chip Eastham]

Post by Chip Eastham

Post by Merciadri Luca
Hi,
I am currently wondering if the rank $\rho$ of a Sudoku matrix ($n
\times n$) $S$ can verify
$\rho < n-1$.
It is clear that $\rho < n$ is possible: it suffices to take $\rho =
n-1$, which is achieved iff $\det(S)=0$, but $\rho <= n-2\equiv \rho <
n-1$ (as we work in $\mathbb Z$) is already more difficult to say.
Any idea? Currently, my strongest (i.e. the most exigent, thus leading
to the `smallest' [on the cardinality point of view] set of matrices
verifying the property) affirmation is that, for some Sudoku matrices,
$1 <= \rho <= n-1$. But can one give examples about matrices whose
rank would restrict this equality (i.e. giving a subset $\mathcal P$
of [1, n-1] such that $\mathcal P\neq [1, n-1]$)?
Thanks.

For general (positive integer) n it is unclear
what you might mean by "Sudoku matrix" (which
conventionally requires n = 9).
A Sudoku matrix is a special case of a latin
square.  I believe it is known that "cyclic"
latin squares of order n can have rank as low
1 + SUM phi((p_i)^{j_i})
where n = PROD (p_i)^{j_i} is the (unique)
prime factorization and phi is the Euler phi
function.  So for n = 3^2, phi(n) = 6 and
the above minimum rank is 7.
[On the rank of cyclic latin squares (1995)]
(W. C. Shiu and K. T. Fang)http://www.informaworld.com/index/779107967.pdf
However this doesn't answer your question about
the minimum rank of Sudoku matrices, even for
n = 9.
regards, chip

The above paper has a third author, S. L. Ma,
whose name for some reason appears only in the
metadata on the informaworld.com page linked
above (although the academic affiliation shows).

regards, chip

[Chip Eastham]

Post by Chip Eastham

Post by Merciadri Luca
Hi,
I am currently wondering if the rank $\rho$ of a Sudoku matrix ($n
\times n$) $S$ can verify
$\rho < n-1$.
It is clear that $\rho < n$ is possible: it suffices to take $\rho =
n-1$, which is achieved iff $\det(S)=0$, but $\rho <= n-2\equiv \rho <
n-1$ (as we work in $\mathbb Z$) is already more difficult to say.
Any idea? Currently, my strongest (i.e. the most exigent, thus leading
to the `smallest' [on the cardinality point of view] set of matrices
verifying the property) affirmation is that, for some Sudoku matrices,
$1 <= \rho <= n-1$. But can one give examples about matrices whose
rank would restrict this equality (i.e. giving a subset $\mathcal P$
of [1, n-1] such that $\mathcal P\neq [1, n-1]$)?
Thanks.

For general (positive integer) n it is unclear
what you might mean by "Sudoku matrix" (which
conventionally requires n = 9).
A Sudoku matrix is a special case of a latin
square.  I believe it is known that "cyclic"
latin squares of order n can have rank as low
1 + SUM phi((p_i)^{j_i})
where n = PROD (p_i)^{j_i} is the (unique)
prime factorization and phi is the Euler phi
function.  So for n = 3^2, phi(n) = 6 and
the above minimum rank is 7.
[On the rank of cyclic latin squares (1995)]
(W. C. Shiu and K. T. Fang)http://www.informaworld.com/index/779107967.pdf
However this doesn't answer your question about
the minimum rank of Sudoku matrices, even for
n = 9.
regards, chip

Success! The construction in Lemma 3.8 of the
paper by Shiu, Ma, and Fang (linked above) gives
a cyclic latin square (circulant matrix) that is
not immediately a sudoku matrix for n = 9.

However with a suitable permutation of rows it
becomes a sudoku matrix of rank 7:

1 2 3 5 6 4 9 7 8
5 6 4 9 7 8 1 2 3
9 7 8 1 2 3 5 6 4
2 3 5 6 4 9 7 8 1
6 4 9 7 8 1 2 3 5
7 8 1 2 3 5 6 4 9
3 5 6 4 9 7 8 1 2
4 9 7 8 1 2 3 5 6
8 1 2 3 5 6 4 9 7

I used the Online Matrix Calculator here:

[Online Matrix Calculator -- bluebit]
http://www.bluebit.gr/matrix-calculator/

to verify the matrix rank (bluebit's demo
of their .NET matrix library).

A similar construction using Lemma 3.7 gives
the 6x6 generalized sudoku matrix of rank 4:

1 6 2 | 4 3 5
4 3 5 | 1 6 2
---------------------
6 2 4 | 3 5 1
3 5 1 | 6 2 4
---------------------
2 4 3 | 5 1 6
5 1 6 | 2 4 3

which again is rank two less than the order.

regards, chip

[Chip Eastham]

Post by Chip Eastham

Post by Merciadri Luca
Hi,
I am currently wondering if the rank $\rho$ of a Sudoku matrix ($n
\times n$) $S$ can verify
$\rho < n-1$.
It is clear that $\rho < n$ is possible: it suffices to take $\rho =
n-1$, which is achieved iff $\det(S)=0$, but $\rho <= n-2\equiv \rho <
n-1$ (as we work in $\mathbb Z$) is already more difficult to say.
Any idea? Currently, my strongest (i.e. the most exigent, thus leading
to the `smallest' [on the cardinality point of view] set of matrices
verifying the property) affirmation is that, for some Sudoku matrices,
$1 <= \rho <= n-1$. But can one give examples about matrices whose
rank would restrict this equality (i.e. giving a subset $\mathcal P$
of [1, n-1] such that $\mathcal P\neq [1, n-1]$)?
Thanks.

For general (positive integer) n it is unclear
what you might mean by "Sudoku matrix" (which
conventionally requires n = 9).
A Sudoku matrix is a special case of a latin
square.  I believe it is known that "cyclic"
latin squares of order n can have rank as low
1 + SUM phi((p_i)^{j_i})
where n = PROD (p_i)^{j_i} is the (unique)
prime factorization and phi is the Euler phi
function.  So for n = 3^2, phi(n) = 6 and
the above minimum rank is 7.
[On the rank of cyclic latin squares (1995)]
(W. C. Shiu and K. T. Fang)http://www.informaworld.com/index/779107967.pdf
However this doesn't answer your question about
the minimum rank of Sudoku matrices, even for
n = 9.
regards, chip

Success!  The construction in Lemma 3.8 of the
paper by Shiu, Ma, and Fang (linked above) gives
a cyclic latin square (circulant matrix) that is
not immediately a sudoku matrix for n = 9.
However with a suitable permutation of rows it
1 2 3 5 6 4 9 7 8
5 6 4 9 7 8 1 2 3
9 7 8 1 2 3 5 6 4
2 3 5 6 4 9 7 8 1
6 4 9 7 8 1 2 3 5
7 8 1 2 3 5 6 4 9
3 5 6 4 9 7 8 1 2
4 9 7 8 1 2 3 5 6
8 1 2 3 5 6 4 9 7
[Online Matrix Calculator -- bluebit]http://www.bluebit.gr/matrix-calculator/
to verify the matrix rank (bluebit's demo
of their .NET matrix library).

Hi, Luca:

[The OP wrote me to say that he'd had trouble
posting follow-ups to this thread, but that
the notion of NxN sudoku matrix he has in mind
is for N a perfect square.]

It turns out the rank of a 9x9 sudoku matrix
can be even less than that of a cyclic latin
square (7). The following sudoku matrix:

1 2 3 6 4 5 8 9 7
6 4 5 8 9 7 1 2 3
8 9 7 1 2 3 6 4 5
2 3 1 4 5 6 9 7 8
4 5 6 9 7 8 2 3 1
9 7 8 2 3 1 4 5 6
3 1 2 5 6 4 7 8 9
5 6 4 7 8 9 3 1 2
7 8 9 3 1 2 5 6 4

has rank 5. My construction was motivated by
the idea that, since each symbol appears once
in each column, the rows all sum to a constant
row. But in the upper left 3x3 matrix we can
arrange that those 3 rows sum to a constant,
and by permuting its rows and columns into the
other 3x3 matrices, we obtain the constant
vector as a sum in more than one way.

regards, chip

[Chip Eastham]

Post by Merciadri Luca
Hi,
I am currently wondering if the rank $\rho$ of a Sudoku matrix ($n
\times n$) $S$ can verify
$\rho < n-1$.
It is clear that $\rho < n$ is possible: it suffices to take $\rho =
n-1$, which is achieved iff $\det(S)=0$, but $\rho <= n-2\equiv \rho <
n-1$ (as we work in $\mathbb Z$) is already more difficult to say.
Any idea? Currently, my strongest (i.e. the most exigent, thus leading
to the `smallest' [on the cardinality point of view] set of matrices
verifying the property) affirmation is that, for some Sudoku matrices,
$1 <= \rho <= n-1$. But can one give examples about matrices whose
rank would restrict this equality (i.e. giving a subset $\mathcal P$
of [1, n-1] such that $\mathcal P\neq [1, n-1]$)?
Thanks.

I wondered to what extent the answer to these
questions might depend on the choice of latin
square symbols. While entries 1,..,N seem
natural enough, might a programmer not make
an equally good case for 0,...,N-1 symbols
(for an NxN latin square)?

Let L be a latin square using 1,..,N and M be
the result of subtracting one from each entry
of L. Trivially if N = 1, then rank(L) > rank(M).

But if N > 1, then rowspace(L) = rowspace(M)
and thus they are of equal rank. It follows
that the minimum and maximum ranks of various
kinds of latin squares, including in particular
sudoku matrices, would not change if symbols
1,..,N were replaced by 0,..,N-1.

regards, chip