Timeline for Constructing a vector consisting of nonnegative entries
Current License: CC BY-SA 4.0
41 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2021 at 18:30 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
added SageMath code
|
| Feb 10, 2021 at 17:35 | comment | added | Max Alekseyev | Let us continue this discussion in chat. | |
| Feb 10, 2021 at 17:30 | comment | added | Max Alekseyev | My answer gives you a construction that answers your original question here and the new question at MSE (since it's still a duplicate). I'm not sure what else you are asking in your questions -- it seems you have some additional restrictions in mind, which you do not state explicitly. | |
| Feb 10, 2021 at 16:21 | comment | added | vidyarthi | Done some slight modification. By the way, I just want that whenever I put a nonzero number, I have a complementary nonzero number determined modulo $m$. We could put the zeros in the other places. Thus, in this sense, there is no condition of zeros as such. Could you explain your dilemma a bit more? | |
| Feb 10, 2021 at 14:36 | comment | added | Max Alekseyev | I do not see any difference from the question here, which I answered. In the comments you imposed additional restriction on positions of zeros - why didn't you mention this restriction in the new question? | |
| Feb 10, 2021 at 14:15 | comment | added | vidyarthi | done, its here | |
| Feb 9, 2021 at 18:54 | comment | added | Max Alekseyev | @vidyarthi: Since it's a different problem, I'd recommend to accurately formulate it as a new question, which would be more suitable at math.stackexchange.com I may have another algorithm for your new problem, but I cannot explain it here. | |
| Feb 9, 2021 at 16:16 | vote | accept | vidyarthi | ||
| Feb 9, 2021 at 16:17 | |||||
| Feb 9, 2021 at 16:16 | comment | added | vidyarthi | yes, the positions of zeros are not fixed, but once we put a nonzero entry before $n/2$th column, we automatically put another after $n/2$, so in that sense, the nonzero entries before $n/2$th column are the real variables. Yes, brute force is the natural thought, but whether it is always possible is my only question | |
| Feb 9, 2021 at 15:45 | comment | added | Max Alekseyev | @vidyarthi: In your original problem, the positions of zeroes were not fixed. The one you just asked is more restrictive in that sense. I did not claim that brute-force is the only way - it's just the first thing that comes to mind. | |
| Feb 9, 2021 at 7:02 | comment | added | vidyarthi | how is it a different problem? I think i asked the same problem. Anyways, is brute force the only way, or can we state the possibility from by a fixed algorithm; or, is it altogether unpredictable to construct such a vector | |
| Feb 9, 2021 at 4:02 | comment | added | Max Alekseyev | @vidyarthi: This is a different problem from what you originally asked. Here is a solution obtained by brute-force: $$(1,11,0,8,7,9,0,2,0,0,0,0,0,6,0,4,3,5,0,10)$$ | |
| Feb 8, 2021 at 23:05 | comment | added | vidyarthi | Sorry, again a problem. Suppose I want to construct a vector like $\{1,*, 0, *,*,*,0,*,0,0,0,0,0,*,0,*,*,*,0,*\}$, where $*$ denotes the nonnegative entries. The differences between nonnegatives in this case modulo $m=11$ in this case are $1, 3,4, 5, 7$. So isnt is asymmetric. What are the entries in this case? | |
| Jun 4, 2020 at 20:39 | comment | added | vidyarthi | The proof i think need not mention the parity of differences. Instead, only the distinctness of the numbers in both the pairs would do to prove that all the numbers from $2$ to $m$ are covered. But anyways, the answer is right and works well! | |
| Jun 4, 2020 at 20:32 | comment | added | vidyarthi | but take $t=2, m=17$ . Then $2+t=4,m-t=15$, and the difference is odd. The problem is that the difference is $2+2t-m$, which is less than (in magnitude) $m$, whence modulo does not keep the parity unaffected | |
| Jun 4, 2020 at 12:26 | comment | added | Max Alekseyev | We consider differences modulo $m$. So, here it does not matter if $m$ is even or odd - in either case we get $(2+t)-(m-t)\equiv 2+2t\pmod m$. | |
| Jun 4, 2020 at 11:07 | comment | added | vidyarthi | again a problem, the differences in the first pair $(2+t,m-t)$ are always odd if $m$ is odd. So, how can you ensure all the dfferences? Although the pairs give distinct entries, but the proof you give is not clear. | |
| Feb 25, 2020 at 14:06 | comment | added | Max Alekseyev | Then simply assign pairs of values as in my answer, but if such assignment violates your additional restriction, then re-assign both values to any available $a_j$ with $j>n/2$. | |
| Feb 24, 2020 at 22:38 | comment | added | vidyarthi | say, by symmetry that $\frac{n}{6}$ entries are nonzero before $a_{n/2}$ | |
| Feb 24, 2020 at 17:29 | comment | added | Max Alekseyev | How many nonzero entries you want before $a_{n/2}$? When $m\leq n/3$, it's unavoidable that some of these entries will be zero. | |
| Feb 24, 2020 at 16:11 | comment | added | vidyarthi | oh yes thanks, i forgot about that. so you have completely answered the modified problem. only last thing is whether i could have nonzero entries before $a_{\frac{n}{2}}$. | |
| Feb 24, 2020 at 13:49 | comment | added | Max Alekseyev | I do not quite follow again. According to your original question, the congruence $a_j\equiv a_{n+2-j}+j-1\pmod m$ is required only for nonzero $a_j$. In the above example, for $j=n/2-1$ we have $a_j=0$, and so the congruence may not hold. | |
| Feb 23, 2020 at 21:23 | comment | added | vidyarthi | sorry, again a confusion. For $m\le\frac{n}{3}$, suppose $a_{\frac{n}{2}+3}=3$. Then, since we have $a_{\frac{n}{2}-1}=0$, therefore the difference is $-3=m-3\pmod m$.So how is the difference in this case $j-1=\frac{n}{2}-2\pmod m$? And, by the way, can I not have nonzero entries before $a_{\frac{n}{2}}$? | |
| Feb 22, 2020 at 22:11 | comment | added | Max Alekseyev | For $m\leq n/3$, simply set $a_{n/2+k}=k$ for $k=1..m$, and all other $a_j$ to 0. If $n/3<m<n/2$, then $m$ cannot divide $n$. | |
| Feb 22, 2020 at 21:16 | comment | added | vidyarthi | sorry, I did not get your second part. Could you illustrate the part when $m\le\frac{n}{3}$. And what about the part $\frac{n}{3}<m<\frac{n}{2}$? | |
| Feb 22, 2020 at 6:04 | comment | added | Max Alekseyev | Assume $m|n$. There are no $j\equiv 1\pmod m$ in the interval $[2,n/2]$ if $m\geq n/2$. So, the additional restriction playa role only when $m\leq n/3$. However, in this case we can simply assign all nonzero values to $a_j$'s with $j>n/2$. | |
| Feb 21, 2020 at 18:29 | comment | added | vidyarthi | Yes, it is true that $j\equiv n+1\pmod m$. But, if I were to suppose that $m| n$, then I would get by conclusion. Anyways, the main thing is to ensure that the numbers $a_j$ and $a_{n+2-j}$ are not congruent to $j$ and $n+2-j$ respectively, Can this be done. Assume that $m$ divides $n$ | |
| Feb 21, 2020 at 18:20 | comment | added | vidyarthi | I wanted the difference between $a_j$ and $a_{n+2-j}$ in the OP to be $j-1\pmod m$. Using your rule, I equate this to either $2+2t$(even difference) or $2t+1$(odd difference), obtaining $t=\frac{j-3}{2}$ and $t=\frac{j-2}{2}$ respectively. This means when $j\equiv1\pmod m$, and $j$ is odd, we would obtain $a_j=2+t= 2+\frac{j-3}{2}\equiv j\pmod m$. But, I do not want $a_j$ to be conguent to $j$. Is my method of equating $2+2t$ and $2t+1$ with $j-1$ wrong? | |
| Feb 21, 2020 at 17:30 | comment | added | Max Alekseyev | I do not quite follow. The difference in $(j,n+2-j)$ is $2j-n-2$. If it's assigned to $(a_j,a_{n+2-j})$, the the difference is congruent to $j-1$ modulo $m$, implying $j\equiv n+1\pmod m$. Why you say $j\equiv 1\pmod m$? | |
| Feb 21, 2020 at 9:19 | comment | added | vidyarthi | I meant $r$ to be $m$ in my previous comment | |
| Feb 21, 2020 at 8:19 | comment | added | vidyarthi | Actually, I have another problem now. My problem requirements also state that the numbers in the individual pairs $(a_j,a_{n+2-j})$ must not be equivalent to $(j,n+2-j)$ modulo $r$. Now, is that also possible? By the above construction, this would occur at the point when $j\equiv1\pmod r$. So how to circumvent this problem? | |
| Feb 10, 2020 at 21:45 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
clarified
|
| Feb 10, 2020 at 21:40 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
added 102 characters in body; added 8 characters in body
|
| Feb 10, 2020 at 21:29 | comment | added | Max Alekseyev | @vidyarthi: sort of ;) | |
| Feb 10, 2020 at 21:28 | comment | added | vidyarthi | ok, you are actually a computational biologist, is number theory and combinatorics your hobby? | |
| Feb 10, 2020 at 21:26 | comment | added | Max Alekseyev | @vidyarthi: I drew matchings between residues modulo $m$ giving differences $1,2,\dots$ | |
| Feb 10, 2020 at 21:25 | vote | accept | vidyarthi | ||
| Feb 9, 2021 at 16:16 | |||||
| Feb 10, 2020 at 21:25 | comment | added | vidyarthi | you mean you drew paths of odd and even order between the numbers $a_j$ and $a_{n-j+2}$? | |
| Feb 10, 2020 at 21:23 | comment | added | Max Alekseyev | @vidyarthi: a lot of drawing on a piece of paper ;) | |
| Feb 10, 2020 at 21:22 | comment | added | vidyarthi | great! how did you get such an idea? | |
| Feb 10, 2020 at 21:17 | history | answered | Max Alekseyev | CC BY-SA 4.0 |