Is a convex set of permutation matrices $ntimes n$ ($mathbb{P}_{n}cap mathbb{C}$) a singleton?

$mathbb{C}$ is a closed convex set.

In detail,

$min_{Xinmathbb{P}_{n}capmathbb{C}} f(x):= x^{T}Wx + c^{T}x$

$x:=vec(X)in mathbb{R}^{n^2}$

What is wrong if I remove the $capmathbb{C}$ as the below?

$min_{Xinmathbb{P}_{n}} f(x):= x^{T}Wx + c^{T}x$

Another statement is as the title,

If a subset of permutation matrices is convex set, is this subset Singleton, which has only one element in the set?

@Robert Israel Yeah, I also think it ends up a singleton, but it should not be like that..

@John Hughes, thanks for quick response!
Have you looked at the cases n=1,2,3 and tried writing out all the permutation matrices?

Yes, n=1, 0, 1 leads 1/2 1/3 many arbitrary convex combination element if the set have 0 and 1. So, possible answer is {0}, {1}. They are singleton.

0 & 1\
1 & 0\
or $P_{2}=begin{pmatrix}
1 & 0\
0 & 1\
The same analogy, {${P_{2}}$} with one element is only possible.

n=3, n=4… I think if there is any pairs which is not matched as (0,0) or (1,1), it causes the element which is out of Permutation matrices. I cannot get any valid subset of Permutation matrices which has over 1 element.

Have you looked at convex combinations of pairs of permutation matrices in these low-dimensional cases? Did it lead to any insight?

So the answer is the above.

Mathematics Asked by Joey Cho on November 14, 2021

0 Answers

Add your own answers!

Related Questions

Nimber multiplication

2  Asked on July 30, 2020 by yberman


Calculating distance when velocity is given

1  Asked on July 27, 2020 by aruha


Ask a Question

Get help from others!

© 2021 All rights reserved.