How much redundancy resides in an $n \times n$ orthogonal matrix?

Question

Suppose one has an $n \times n$ orthogonal matrix $M$: $$ \left( \begin{array}{ccc} 0.239326 & 0.846726 & 0.475161 \\ 0.768893 & 0.13356 & -0.625272 \\ 0.592897 & -0.514992 & 0.619077 \\ \end{array} \right) $$ Because it is orthogonal, $M^T M = I$. Suppose one entry of $M$ is erased, say $M(2,2)$: $$ \left( \begin{array}{ccc} 0.239326 & 0.846726 & 0.475161 \\ 0.768893 & \color{red}{x} & -0.625272 \\ 0.592897 & -0.514992 & 0.619077 \\ \end{array} \right) $$ It can be recovered from $M^TM=I$. For example, we must have the $(2,2)$ entry of $M^TM$ equal to $1$: \begin{eqnarray} 0.982162 + x^2 &=& 1 \\ x &=& \pm 0.13356 \end{eqnarray} and then, e.g., entry $(2,1)$ of $M^TM$ disambiguates (or determines on its own): \begin{eqnarray} -0.102694 + 0.768893 x &=& 0 \\ x &=& 0.13356 \end{eqnarray}

My question is:

Q. What is the maximum number $k$ of entries of an $n \times n$ orthogonal matrix $M$ that can be erased and then uniquely recovered, knowing only that $M$ is orthogonal?

It could well be that $k$ depends on which entries are erased, which itself could be interesting. But I am at the moment seeking the maximum of $k$ over all possible entries that permits exact recovery.

Answer 1

$O(n)$ is a manifold of dimension $n(n-1)/2$, so "generically" one might hope to recover up to $n(n+1)/2$ entries from the other $n(n-1)/2$. This won't quite work, however. Given any set $A$ of rows and any set $B$ of columns, generically we need at least one entry to survive that is either in both rows $A$ and columns $B$ or in neither: otherwise we could multiply each entry $a_{ij}$ by $(-1)^{\chi_A(i) + \chi_B(j)}$ where $\chi_A$ and $\chi_B$ are the indicator functions of $A$ and $B$. Thus in the case $n=2$ we can only erase a single entry.

Answer 2

Let $P$ be any $(n-2)\times (n-2)$ orthogonal matrix and $Q$ any $2\times 2$ orthogonal matrix. Let $M=P\oplus Q$. If we erase the four entries of $Q$, then there are uncountably many ways to fill them in to obtain an orthogonal matrix.

Perhaps the "correct" condition on $M$ should be that it is an orthogonal matrix with no zero entries.

Answer 3

According to the Noam's post, the good question is: how to choose $n(n-1)/2$ entries of a matrix so that there are a $>0$ finite number of associated solutions in $O(n)$. Let $\mathcal{T}$ be the set of strictly upper triangular matrices. Let $M\in O(n)$ and $M^S\in\mathcal{T}$ be the matrix that is deduced from $M$ by canceling the $\{m_{i,j}|i\geq j\}$; $M$ can be written in the form $e^K$ where $K\in SK_n$ -the set of skew-symmetric matrices-. Since $O(n)$ is a group, the tangent space of $O(n)$ in $M$ is of the form $M+MH$ where $H\in SK_n$. If the linear application $f_M:H\in SK_n\rightarrow (MH)^S\in\mathcal{T}$ is an isomorphism, then there are neighborhoods $U$ of $M^S$ in $\mathcal{T}$ and $V$ of $M$ in $O(n)$ s.t. any $N\in U$ is associated to a matrix in $V$.

Proposition. There is $\epsilon >0$ s.t. any $N\in\mathcal{T}$ satisfying $||N||<\epsilon$ is associated to an orthogonal matrix close to $I_n$.

Proof. Generally, $\det(f_M)=d_1\cdots,d_{n-1}$ where $d_k$ is the determinant of the matrix constituted with the $k$ first rows and the $k$ first columns of $M$. Clearly $\det(f_{I_n})=1$ and we are done.

Remark . I think that the previous result is also true for a generic choice of $M$ in $O(n)$.

EDIT 1. Using Maple, I thought I eliminated the complex solutions but, unfortunately, that was not the case! In a second time, I used a software that gives false results. The third one seems to work correctly on real numbers and gives that follows: if we make public any $n(n-1)/2$ entries of $M$, then there are at least $4$ associated (real) orthogonal matrices.

About the Denis'reasoning, it is well-known that the Cayley transform $\mathcal{C}$ is a parametrization of $O^+(n)$ by the set of skew symmetric matrices (a vector space of dimension $n(n-1)/2$). If $p$ is the projector $M\rightarrow M^S$, then there is no reason why $p\circ \mathcal{C}$ is one to one (generically).

EDIT 2. If $n\leq 11$, then to make public $M^S$ and $m_{n,1},m_{n,2}$ implies that whole matrix $M$ can be recovered. Hence the:

Conjecture: Let $M\in O(n)$ be generic. If we know $M^S$ and $m_{n,1},m_{n,2}$, then we can recover the whole matrix $M$.

Answer 4

The fact that $\frac{n(n-1)}2$ well chosen coefficients determine the other ones is supported by the Schur parametrization : let $U$ be unitary (it works as well for real orthogonal matrices) and Hessenberg (that is $i\ge j+2$ implies $u_{ij}=0$). Up to multiplication by a diagonal unitary matrix, we may assume that the diagonal of $U$ is real non-negative. Then there are unique pairs $(a_k,b_k)$ with $b_k$ real and $|a_k|^2+b_k^2=1$, such that $U=G_1\cdots G_{n-1}$ with $$G_k={\rm diag}\left(I_{k-1},\begin{pmatrix} -a_k & b_k \\ b_k & \overline{a_k} \end{pmatrix},I_{n-k-1}\right).$$ It is a case where one gives the sub-diagonal part of $U$ (with many zeroes).The pairs are determined by the entries $u_{i,i-1}$.

Notice that in the unitary case, the dimension of the tangent space $SK_n$ over $\mathbb R$ is $n^2$, and we are given $n^2$ real data, namely $\frac{n(n-1)}2$ complex numbers (sub-diagonal entries) and $n$ real numbers (the imaginary parts of the diagonal entries).