Timeline for determining if a matrix of linear forms represents a non-degenerate matrix
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 7, 2011 at 18:26 | comment | added | Emil Jeřábek | Thanks for accepting the answer, even though it doesn’t really resolve the main question. | |
| Dec 7, 2011 at 18:12 | vote | accept | Łukasz Grabowski | ||
| Dec 7, 2011 at 17:43 | comment | added | Łukasz Grabowski | Thanks Emil, I've learned a lot. I'll accept this answer and ask another more specific question. | |
| Dec 7, 2011 at 17:08 | comment | added | Emil Jeřábek | No, it is only NP-complete for finite fields. For efficiently representable infinite fields (such as $\mathbb Q$ or the algebraic closure of $\mathbb F_p$) the problem is in RP, using the randomized algorithm I outlined in my answer. | |
| Dec 7, 2011 at 16:47 | comment | added | Łukasz Grabowski | On a tangential note: I believe this shows the problem is NP-complete for any field of non-zero characteristic. But is it NP-complete also for $k = \mathbb Q$? (we need to remember that the size of the input depends not only on $n$ but also on how big denominators and numerators are, and let's no longer assume that the cost of arithmetic operations is $1$) | |
| Dec 7, 2011 at 14:23 | comment | added | Emil Jeřábek | Yes, you are right. | |
| Dec 7, 2011 at 14:14 | comment | added | Łukasz Grabowski | It's useful to know it's NP complete, but note that you encode a 3-sat instance of $m$ clauses with $n$ variables into a $3m \times 3m$ matrix. I believe this can be solved in a number of steps which is polynomial in $2^m$, so this doesn't seem to directly answer my question whether you can go from $p^{n^2}$ to $p^n$. | |
| Dec 7, 2011 at 13:48 | comment | added | Emil Jeřábek | I realized that what I called the adjacency matrix of a bipartite graph is officially known as the biadjacency matrix. I’m sorry if this is what confused you. | |
| Dec 7, 2011 at 13:44 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
fix terminology
|
| Dec 7, 2011 at 13:39 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
make it linear rather than affine
|
| Dec 7, 2011 at 13:15 | comment | added | Łukasz Grabowski | Ok, I though the vertex set is $(1,\ldots, n )$. I'll think it over. | |
| Dec 7, 2011 at 13:12 | comment | added | Emil Jeřábek | I’m talking about bipartite graphs. Your matrix corresponds to the graph with vertex set $U\cup V$, $U=\{u_1,u_2,u_3\}$, $V=\{v_1,v_2,v_3\}$, and edge set $E=\{(u_1,v_2),(u_2,v_3),(u_3,v_1)\}$. This graph has a perfect matching, in fact, it is a perfect matching. | |
| Dec 7, 2011 at 13:08 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
added 629 characters in body
|
| Dec 7, 2011 at 13:06 | comment | added | Łukasz Grabowski | Also, if you conider the case when $M_{ij}$ is non-zero for $(i,j)= (1,2), (2,3), (3,1)$, there's no perfect matching. Perhaps you meant that vertiices lie in a union of disjoint cycles? (mathings would be then "cycles of length 2", but then the problem dangerously reminds me of finding a hamiltonian cycle) | |
| Dec 7, 2011 at 13:03 | comment | added | Łukasz Grabowski | After thinking about it, I don't understand your solution to the special problem. I agree that it's equivalen to checking if there is a permutaion $\pi$ such that $M_{i\pi(i)}\neq 0$ for all $i$. But what doe it have to do with perfect matchings? Could you give a reference or expand the argument? | |
| Dec 7, 2011 at 0:11 | comment | added | Łukasz Grabowski | Thanks, this solves the special problem. I'll reformulate the question to make clear that I mean $p$ to be fixed; in particular the probabilistic polynomial-time algorithm you suggest is of not much use. | |
| Dec 6, 2011 at 18:30 | history | answered | Emil Jeřábek | CC BY-SA 3.0 |