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
    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
    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
    Feb 7, 2019 at 12:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.