19
$\begingroup$

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.

$\endgroup$
4
  • 11
    $\begingroup$ What's the quantification over matrices and locations? It's not always true that even a single diagonal entry can be recovered uniquely: what's $x$ such that ${\rm diag}(1,x)$ is orthogonal? $\endgroup$ Jun 6, 2015 at 0:15
  • 16
    $\begingroup$ And in the other direction, if an orthogonal matrix has $\pm 1$'s on the diagonal then every other entry is zero because each row has norm $1$; so in this sense $k$ can be as large as $n^2-n$, and that's clearly maximal because any more would leave an entire row $r$ undetermined and $-r$ works as well. $\endgroup$ Jun 6, 2015 at 0:18
  • 1
    $\begingroup$ @NoamD.Elkies: Thank you for the clarity of your observations, which have uncovered the essence of the situation explored in my question. $\endgroup$ Jun 6, 2015 at 0:51
  • $\begingroup$ if the sign of the determinant is given, then a higher number of entries can be recovered, specifically $2$ for $n=2$ $\endgroup$ Jun 6, 2015 at 3:53

4 Answers 4

11
$\begingroup$

$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.

$\endgroup$
1
  • 8
    $\begingroup$ Generally I'd expect that $(n^2-n)/2$ entries would determine the rest up to finite choice, and that one more entry would have to be specified to remove the ambiguity (though as you note there are other ways that a collection of entries can fail almost always despite the dimension heuristic, such as when an entire row or column is unspecified). $\endgroup$ Jun 6, 2015 at 0:56
15
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.