4
$\begingroup$

The question is motivated by this question on Mathematics SE.

Let $A \in O(n)$ be an orthogonal matrix that is not a signed permutation matrix, and let $P$ be the nearest signed permutation matrix to $A$ (for 'nearest', use the distance induced by the Frobenius norm, i.e., $d(A,P)=||A-P||_F$). Then can $A$ move 'monotonically' to $P$? I.e., in every neighborhood of $A$, does there exist $B \in O(n)$ such that:

(1) $|b_{ij}| \geq |a_{ij}|$ at every non-zero entry $(i,j)$ of $P$ (and at least one inequality is strict), and

(2) $|b_{ij}| \leq |a_{ij}|$ at every other entry

Note that if we remove the condition that $P$ is the nearest signed permutation matrix to $A$ , then the claim is not true and a counterexample is given in the original question. Also note that the claim is true if $A$ is sufficiently close to $P$, as we can form a path from $A$ to $P$ by using exponential maps, say a path $B_t$ where $B_0 = A$ and $B_1 = P$. Since the entries of $B_t$ is analytic in $t$, in a small enough neighborhood the entries of $B_t$ would be monotonic in $t$, which shows every matrix in the path satisfies our property.

I am leaning toward that the claim is correct, but I am not sure. Any thoughts?

Edit:

Here is a weaker problem: for every $A\in O(n)$, $\textit{does there always exist}$ a signed permutation matrix $P$ where $A$ could move 'monotonically' to $P$ in the sense described above?

A possible approach is that, let $$C_P=\{B\in M_{n\times n}\mid B \text{ has the same sign as }A\text{ at the non-zero entries of }P, B \text{ has different sign from }A\text{ at the zero entries of }P\}.$$ Because the tangent space of $A$ is $n(n-1)/2$ dimensional, we would be done if we can prove that every $n(n-1)/2$ dimensional subspace of $M_{n\times n}$ intersects $\bigcup_{P\text{ is a permutation matrix}}C_P$ untrivially.

Edit 2:

Maybe the original question is still too strong, so I would like to weaken (2) to be:

(2) $|b_{ij}| \leq |a_{ij}|+\epsilon$ at every other entry

Then for every $\epsilon>0$, does such $B$ exists? Since we have some freedom here, maybe Gram-Schmidt would work?

$\endgroup$
3
  • $\begingroup$ When you say "any distance induced by a matrix norm" am I allowed to use the operator norm, i.e. the one for which every orthogonal matrix has norm 1? $\endgroup$
    – Yemon Choi
    Jun 29, 2020 at 1:39
  • 1
    $\begingroup$ Question also posted several hours ago to math.stackexchange.com/questions/3737954/… $\endgroup$
    – Yemon Choi
    Jun 29, 2020 at 1:44
  • $\begingroup$ @YemonChoi Maybe it's better to fix one. I editted the question. $\endgroup$
    – ryanriess
    Jun 29, 2020 at 2:43

0

Your Answer

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