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?