bio | website | cs.ox.ac.uk/people/… |
---|---|---|

location | Oxford, United Kingdom | |

age | 50 | |

visits | member for | 3 years, 11 months |

seen | 1 hour ago | |

stats | profile views | 1,809 |

Sep 3 |
comment |
Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete
Why do you talk about finding a sequence? The order you pick up your $v_i$'s does not matter. Better talk about a subset of A. Do you allow weights to be negative? If not, then you trivially will have to take the whole A. |

Sep 3 |
comment |
On the positivity of matrices
The vector space of matrices commuting with G has a basis {$I$,$\pi+\pi^4$,$\pi^2+\pi^3$}, where $\pi$ is the permutation matrix corresponding to the cyclic permutation (1,2,3,4,5). Thus $P$ will be a linear combination of these 3 matrices. |

Sep 3 |
comment |
On the positivity of matrices
$G$ is able to guarantee that $P_{ij}=p$, as the dimension of the centraliser algebra (i.e. the vector space of matrices commuting with every element in $G$) is 3, which can be e.g. checked directly, or by computing the permutation character of $G$. All these things I don't define may be found in books on permutation groups, e.g. P.Cameron's books.google.co.uk/books/about/… |

Sep 2 |
comment |
On the positivity of matrices
G depends on M only, and can be checked to be of size 10. |

Sep 2 |
comment |
On the positivity of matrices
One way to conclude that for $P$ being the average over an orbit all these $P_{ij}=p$, would be to note that $P$ commutes with all $\Pi\in G$. One can check that the algebra of all matrices commuting with $G$ coincides with the algebra of symmetric circulant matrices. Thus $P$ has the claimed form. |

Sep 2 |
revised |
On the positivity of matrices
added a link to the article I referred to |

Sep 2 |
comment |
On the positivity of matrices
@Hansen: I don't see how you would complete a proof "by hand" without being able to reduce the number of parameters significantly. |

Sep 2 |
comment |
On the positivity of matrices
here it is: journals.cambridge.org/article_S0305004100036185 |

Sep 2 |
awarded | Enlightened |

Sep 1 |
comment |
On the positivity of matrices
What I am saying is: take an offending P, and average it over G. This gives a symmetric circulant matrix which is still offending, and which only depends on one parameter, $p$. |

Sep 1 |
awarded | Nice Answer |

Aug 31 |
comment |
On the positivity of matrices
@gondolf - you're welcome. Please click on "accept this answer" if you're happy with it. |

Aug 31 |
comment |
On the positivity of matrices
@Hansen - see my latest edit. |

Aug 31 |
revised |
On the positivity of matrices
more details as requested |

Aug 31 |
comment |
On the positivity of matrices
@Hansen - see my latest edit for a proof and a reference. |

Aug 31 |
revised |
On the positivity of matrices
added 1384 characters in body |

Aug 30 |
comment |
On the positivity of matrices
yes, it is true for $n\leq 4$. This was shown by P.Diananda in 1962 (Proc. Cambridge Phil.Soc., vol 58). The counterexample for n=5 (see my answer) is also from this text. |

Aug 30 |
revised |
On the positivity of matrices
added 285 characters in body |

Aug 30 |
revised |
On the positivity of matrices
edited tags |

Aug 30 |
revised |
On the positivity of matrices
added 204 characters in body |