How much redundancy resides in an $n \times n$ orthogonal matrix? 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.
 A: 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$.
A: 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).
A: 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.
A: $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.
