1
$\begingroup$

Let us build a square array in the following manner, which I would like to call a modified sudoku:

1) Every row and column contains only one copy of a positive entry and there are exactly $t$ such entries.

2) The zeros must repeat a fixed number of times, equal to $n-\text{number of distinct positive entries}=n-t$(the entries left unfilled by positive entries is filled by zeros).

3) Every row should have a distinct vector from each of its corresponding column vectors to positive entries.

4) The positive entries are from a set of given positive integers which is atmost the order of the array, i.e, the vectors(t-tuples of positive entries) are chosen from a set of an $t+1$ positive entries where $t+1$ is atmost the order of array$=n$.

What could be a probable algorithm to build such an array? One probable combination satisfying the above rules for order of array$=4$, and cardinality of the set of positive integers is $4$: $$\begin{pmatrix}1&2&3&0\\4&3&0&1\\2&0&4&3\\0&4&1&2\end{pmatrix}$$

Another example involving the order of array $=6$ and number of positive integer options $=4$, i.e length of tuple of positive entries $=3$ is: \begin{pmatrix}1&2&3&0&0&0\\4&3&0&0&0&1\\2&0&0&0&4&3\\0&0&0&4&3&2\\0&0&4&2&1&0\\0&4&1&3&0&0\end{pmatrix}

Also, a very important question is, whether such a n array can be built for every $n$ and $t$? Or, are there any constraints on $n,t$? I find that barring the case of $t=2$, other cases are possible, by combinatorial arguments, since we need to choose at most $t=1$ distinct vectors, which is possible as we are choosing the $t$ positive entries from $t+1$ entries. Any hints? Thanks beforehand.

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't understand what point (3) means. Could you explain it in a different way, please? $\endgroup$
    – hexomino
    Commented Feb 7, 2019 at 11:50
  • $\begingroup$ @hexomino What point (3) means is that suppose you have a vector say, of $6$ entries with $3$ positive entries, like $\begin{pmatrix}1&2&3&0&0&0\end{pmatrix}$, then each corresponding column vector to entries $1$, $2$ and $3$ should have different positive entries than $1,2,3$. Like, the corresponding column vectors can be $\begin{pmatrix}1\\2\\4\\0\\0\\0\end{pmatrix}$ corresponding to $1$, contd... $\endgroup$
    – vidyarthi
    Commented Feb 7, 2019 at 12:05
  • $\begingroup$ $\begin{pmatrix}2\\4\\1\\0\\0\\0\end{pmatrix}$ corresponding to $2$ and $\begin{pmatrix}3\\0\\1\\4\\0\\0\end{pmatrix}$ corresponding to $3$, but any of the corresponding column vectors should contain their positive entries as $1,2,3$ or their permutations, like $\begin{pmatrix}2\\0\\0\\0\\1\\3\end{pmatrix}$ corresponding to $2$ $\endgroup$
    – vidyarthi
    Commented Feb 7, 2019 at 12:09

0

Reset to default

Browse other questions tagged or ask your own question.