Timeline for Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2014 at 20:44 | vote | accept | CommunityBot | ||
| Dec 26, 2013 at 8:29 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 1 characters in body
|
| Dec 26, 2013 at 6:58 | history | edited | D.W. | CC BY-SA 3.0 |
Make the title more specific. Clarify that everything is over Z (not Z/2Z). List two equivalent formulations (from the comments).
|
| Dec 25, 2013 at 19:45 | answer | added | Marzio De Biasi | timeline score: 7 | |
| Dec 25, 2013 at 16:38 | answer | added | Peter Shor | timeline score: 7 | |
| Dec 25, 2013 at 13:18 | comment | added | Peter Shor | Consider the vectors to be representations of binary numbers, find a gadget that lets you do carries, and use a reduction from the problem of: given a set of integers, find two subsets with the same sum. | |
| Dec 22, 2013 at 4:59 | comment | added | Carter Tazio Schonwald | One perspective is to view $M$ as a projection matrix, and then look for $M$ such that $M M v = M v, \forall v$. So maybe some ideas relating to the various randomize dimension reduction algorithms could be relevant. | |
| Dec 21, 2013 at 23:38 | answer | added | John D. | timeline score: 3 | |
| Dec 21, 2013 at 0:06 | comment | added | user17100 | The operations are over $\mathbb{Z}$ as you suggest. | |
| Dec 20, 2013 at 23:11 | comment | added | D.W. | If operations are over $\mathbb{Z}/2\mathbb{Z}$, isn't this problem solved by mhum's comment? (Since $Mv_1=Mv_2$ is equivalent to $M(v_1-v_2)=0$, i.e., $Mw=0$ where $w \in (\mathbb{Z}/2\mathbb{Z})^n$ is not identically zero.) So presumably the author intended that operations should be over $\mathbb{Z}$? | |
| Dec 20, 2013 at 22:37 | history | tweeted | twitter.com/#!/StackCSTheory/status/414162720771301376 | ||
| Dec 20, 2013 at 22:06 | comment | added | John D. | Reformulation of the problem: Given $n$ vectors $X = \{ x_1,\dots,x_n \}$ over $\{ 0,1 \}^m$. Are there two different subsets $A,B \subseteq {X}$ such that $\sum_{x \in A} x = \sum_{x \in B} x$? I'd think that it is more likely to be NP-hard if the sums are not taken modulo two, that is operations are over $\mathbb{Z}$ | |
| Dec 20, 2013 at 21:45 | comment | added | Kaveh | Seems like the feasibility problem for 0/1-Integer Programming. Are operations over $\mathbb{Z}$ or over $\mathbb{Z_2}$? | |
| Dec 20, 2013 at 21:44 | comment | added | mhum | Ah. I missed that $v_i$ also had to be binary. My mistake. | |
| Dec 20, 2013 at 21:38 | comment | added | Sasho Nikolov | @mhum no, it's equivalent to determining if there is a nonzero $v \in \{-1, 0, 1\}^n$ such that $Mv = 0$. | |
| S Dec 20, 2013 at 21:37 | history | suggested | David Richerby |
Added linear algebra tag
|
|
| Dec 20, 2013 at 21:36 | comment | added | mhum | Unless I misunderstand the question, is this not equivalent to determining if there is a non-zero $v$ such that $Mv = 0$? And isn't this solved by determining the rank of $M$? | |
| Dec 20, 2013 at 21:26 | review | Suggested edits | |||
| S Dec 20, 2013 at 21:37 | |||||
| Dec 20, 2013 at 19:24 | history | edited | user17100 |
edited tags
|
|
| Dec 20, 2013 at 19:15 | history | asked | user17100 | CC BY-SA 3.0 |