# Reconstruct orthogonal from an orthostochastic matrix

Given an $n \times n$ orthostochastic matrix $\mathbf{A}$, i.e., there exists an orthogonal matrix $\mathbf{O}$ with $A_{ij} = O_{ij}^2$ for all $1\leq i,j \leq n$. What is the fastest way to find $\mathbf{O}$ from $\mathbf{A}$?

As the missing information is only the signs, a complete search over all sign patterns would solve the problem. However, this involves testing $2^{N^2}$ sign patterns. The number of sign patterns can be reduced slightly by some equivalence operations like sign inverting a row. Also, there are $\textit{sign patterns allowing orthogonality}$, i.e., collection of all sign patterns which occur in orthogonal matrices. Besides that the characterization of sign patterns allowing orthogonality is still open for $n > 6$, it will probably not reduce the number of possible candidates to a polynomial magnitude.

There is an analogous case of reconstructing unitary matrices from unistochastic matrices. There is some literature on the analytic side like "The Importance of Being Unistochastic" by Bengtsson, I. (2004). However, I am more concerned with an efficient algorithmic solution to this problem. Any ideas?

A local improvement can be achieved by the following: given $\mathbf{A}$ and a random $\pm$ sign matrix $\mathbf{S}$. Then we can find the closest orthogonal matrix $\mathbf{P}$ by solving the Procrustes problem $\min \lVert \mathbf{P} - \mathbf{A} \circ \mathbf{S} \rVert_F$ with the singular value decomposition, where $\circ$ is the Hadamard product. If now, $\textrm{sign}(\mathbf{P}) \neq \mathbf{S}$ then we can improve by solving with replacing $\mathbf{S}$ with $\textrm{sign}(\mathbf{P})$, because $\mathbf{A}$ is non-negative. This works until the sign matrices are equal.

• I have some doubt that this could be done efficiently. A reconstruction process would also make a decision whether a bistochastic matrix is orthostochastic (rare) or not. The orthostochastic matrices form an $n(n-1)/2$-dimensional subset in the $(n-1)^2$-convex set of bistochastic matrices. I am not sure that it has a nice, external description. – Denis Serre Jan 5 '18 at 11:21
• Note that the proper definition of orthostochastic is that $a_{ij}=|u_{ij}|^2$ where $U$ is unitary. Then the set of orthostochastic matrices is of positive volume in the polytope of bistochastic matrices, although it is strictly smaller if $n\ge3$. – Denis Serre Jan 5 '18 at 11:33
• @DenisSerre Thanks for the comment on the definition. My impression was that your definition refers to unistochastic matrices, but there are differences in literature. – Sebastian Schlecht Jan 5 '18 at 12:02
• @DenisSerre I agree that it seems unlikely to find something efficient, however, I believe it is possible to help an algorithmic solution. For example, it is possible to improve local solutions by solving iteratively the Procrustes problem. – Sebastian Schlecht Jan 5 '18 at 12:05
• A few questions: Are we interested in an algorithm which works well for a random orthostatic matrix, or for one chosen by an intelligent adversary? How are the entries are $A$ given: rational/algebraic numbers in closed form? Floating point approximations? – David E Speyer Jan 5 '18 at 16:52