Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $X$ be a finite-dimensional inner product space, and $T$ a linear operator on $X$. Let $W$ be a subset of $X$ with the following property:

If $T$ preserves norms on $W$, then $T$ is orthogonal on $X$.

One might say that the set $W$ 'detects' orthogonality.

My question is: what is the smallest number of elements that $W$ may contain (as a function of dim$(X) = n$) ?

Quite simply, we can observe that $n + {n \choose 2}$ would form an upper bound for the minimal cardinality of $W$. However, I cannot think of a way to proof whether or not this upper bound is also a lower bound.

share|improve this question
    
It's not quite clear what you're saying. Does that condition on $W$ hold for all $T$? –  lhf Mar 2 '11 at 1:41
    
The idea is that $W$ is "big" enough that if $T$ preserves norms on $W$, it is orthogonal on the entire space. –  Isaac Solomon Mar 2 '11 at 2:26

2 Answers 2

up vote 2 down vote accepted

Suppose a set $W$ is a 'detector'. This means that for any matrix $T$, if $w'T'Tw = w'w$ for all $w \in W$ then $T$ must be orthogonal. This is a set of $|W|$ linear equations on $T'T$.

If $|W| < \binom{n+1}{2}$, then there is a non-zero symmetric matrix $A$ such that $w'Aw = 0$ for all $w \in W$. Note that $A$ has some non-zero eigenvalue.

Clearly $w'Iw = w'w$ for all $w \in W$, and so for all $\epsilon \in \mathbb{R}$, we have $w'(I+\epsilon A)w = w'w$ for all $w \in W$. Choosing $\epsilon > 0$ small enough, we get some matrix $P = I+\epsilon A$ which is positive semidefinite, and thus has a square root $T$ such that $P=T'T$.

Since $\epsilon \neq 0$, $P$ has some positive eigenvalue different than $1$. Thus $T$ has some eigenvalue which is not of unit magnitude, and so cannot be orthogonal.

Addendum: This argument shows that $W$ is a detector iff the outer products $\{ w \otimes w : w \in W\}$ generate the linear space of all symmetric matrices. An example is the set $$W = \{ e_i+e_j : 1 \leq i \leq j \leq n \}.$$


What follows answers the related question where $T$ preserves all inner products on $W$.

You can take any basis of $X$ as $W$: if $T$ preserves all inner products among a basis, it will preserve all inner products.

On the other hand, if you take less than $n$ elements, then consider the projection into their linear span. On $W$ it acts as the identity, so it preserves inner products. But its not even regular.

The same arguments show that $W$ detects orthogonality iff it spans $X$.

share|improve this answer

Edit: This answer gives a construction of $W$ which shows that it need not contain more than ${n+1\choose 2}$ elements (if $X$ is real), but does not answer the question posed, as Yuval's argument does.

The easiest way to construct a finite set $W\subset X$ which detects orthogonality is as follows:

Let $\{\alpha_1,\dots,\alpha_n\}$ be a basis for $X$. Let

$W=\{\alpha_j+c\alpha_k:j\leq k;c=0,1\text{ or }i\}.$

Then $|W|=n^2$. Suppose $T$ is a linear operator on $X$ such that $\|T\alpha\|=\|\alpha\|$ for every $\alpha\in W$. If $j\leq k$, then

$\langle T\alpha_j,T\alpha_k\rangle=\frac{1}{2}\left(\|T\alpha_j+T\alpha_k\|^2+i\|T\alpha_j+iT\alpha_k\|^2\right)-\left(\|T\alpha_j\|^2+\|T\alpha_k\|^2\right)$

$=\frac{1}{2}\left(\|T(\alpha_j+\alpha_k)\|^2+i\|T(\alpha_j+i\alpha_k)\|^2\right)-\left(\|T\alpha_j\|^2+\|T\alpha_k\|^2\right)$

$=\frac{1}{2}\left(\|\alpha_j+\alpha_k\|^2+i\|\alpha_j+i\alpha_k\|^2\right)-\left(\|\alpha_j\|^2+\|\alpha_k\|^2\right)$

$=\langle \alpha_j,\alpha_k\rangle.$

If $j>k$, the above calculation shows that $\langle T\alpha_k,T\alpha_j\rangle=\langle \alpha_k,\alpha_j\rangle$, hence $\langle T\alpha_j,T\alpha_k\rangle=\overline{\langle T\alpha_k,T\alpha_j\rangle}=\overline{\langle \alpha_k,\alpha_j\rangle}=\langle\alpha_j,\alpha_k\rangle.$ Thus $T$ preserves inner products, and $T$ is unitary. Notice that if $X$ is real, $W$ need not contain more than ${n+1\choose2}$ elements; simply choose the set above, without the $n\choose2$ elements $\alpha_j+i\alpha_k$, $j\leq k$.

share|improve this answer
    
Right, I misread the question. –  Yuval Filmus Mar 2 '11 at 2:25
    
Now I also have a real answer. –  Yuval Filmus Mar 2 '11 at 3:19
    
I tried to vote your answer up but I don't have the requisite '15 reputation.' Could you answer what is probably a dumb question about your solution? Why if $|W|<{n+1\choose2}$ must there exist the non-zero symmetric matrix $A$ such that $w'Aw=0$ for all $w\in W$? I understand that the system of $|W|$ equations $w'T'Tw=w'w$ in the ${n+1\choose2}$ variables $T'T$ is invertible only if $|W|\geq{n+1\choose2}$, I am just having trouble making the leap from there. I have been thinking about this problem for a while along with the original poster, which is why I'm interested. –  Nick Strehlke Mar 2 '11 at 6:31
    
The space of all symmetric matrices has dimension $\binom{n+1}{2}$. The solutions of the non-homogeneous system $w'Aw = w'w$ are $I+B$, where $B$ are the solutions for the corresponding homogeneous system $w'Bw = 0$. If $|W|<\binom{n+1}{2}$ then this system is underspecified and so has a non-trivial solution. –  Yuval Filmus Mar 2 '11 at 19:38
    
Right, I thought about that for a while after reading your solution, which is very elegant. Thanks for explaining that. –  Nick Strehlke Mar 2 '11 at 23:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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