4
$\begingroup$

Birkhoff–von Neumann theorem states that a polytope formed by a set of doubly-stochastic matrices has extreme points that are permutation matrices.

I am wondering if there is a similar theorem for a permutation matrix whose elements are replaced by some values of $e^{ix}$.

$\endgroup$
4
  • 1
    $\begingroup$ Does "some values of $e^{-i\omega}$" mean "some norm-$1$ complex numbers"? $\endgroup$
    – LSpice
    Jun 18, 2021 at 12:40
  • 5
    $\begingroup$ These matrices are called "complex permutation matrices". I don't know any result that describes their convex hull, but they are exactly the isometries of the $p$-norms ($p \neq 2$) on $\mathbb{C}^n$. $\endgroup$ Jun 18, 2021 at 13:04
  • 1
    $\begingroup$ @LSpice Yes, that is what I meant. $\endgroup$
    – CWC
    Jun 18, 2021 at 13:20
  • $\begingroup$ Edited the title and text: changed $e^{-i\omega}$ to $e^{ix}$ $\endgroup$
    – CWC
    Jun 18, 2021 at 16:59

1 Answer 1

7
$\begingroup$

A statement similar to the Birkhoff theorem holds: these matrices are the extreme points of the set of matrices for which the $\ell_1$ norm of each row and column is $\leq 1$. I denote by $K$ this set.

It is clear that every such matrix is an extreme point in $K$. Conversely, let $A$ be an extreme point in $K$. The $\ell_1$ norm of each row and column must be $1$. Write the entrywise polar decomposition, i.e. write $A$ as an entrywise product $A=U \circ B$ where $B$ is a bistochastic matrix and $U$ a matrix with entries having modulus $1$. The matrix $B$ is an extremal bistochastic matrix: if $B=(B_1 + B_2)/2$ for bistochastic matrices $B_1 \neq B_2$, then the equation $A = (U \circ B_1+U\circ B_2)/2$ contradicts the extremality of $A$. By the usual Birkhoff theorem, $B$ is a permutation matrix and the result follows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.