3,939 reputation
621
bio website cs.ox.ac.uk/people/…
location Oxford, United Kingdom
age 50
visits member for 3 years, 9 months
seen 27 mins ago

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