IBM Research | Ponder This | December 2004 solutions

# Ponder This

## December 2004

<<November December January>>

The N vectors are a scaled orthonormal system.
(The are orthogonal to each other and all have the same length.)

Let us first formalize the question.
Plane P is defined by two vectors u and v that have the following properties:

|u|=1, |v|=1, <u,v>=0

Saying that we can use any plane means that we can choose any two vectors with this property.

The projection of vector V_i to the plane yields (<V_i,u>,<V_i,v>), so
x_i = <V_i,u>+j<V_i,v>
and
{x_i}^2 = (<V_i,u>^2-<V_i,v>^2) + j(2*<V_i,v>*<V_i,u>)

The question can now be formulated as follows:
forall u and v s.t. |u|=1, |v|=1, <u,v>=0, the following holds:
sum from i=1 to N {<V_i,u>^2-<V_i,v>^2} = 0
sum from i=1 to N {<V_i,v>*<V_i,u>} = 0

In order to prove that this property is equivalent to saying that the N vectors form a scaled orthonormal system, let us first note that the property is invariant to the system of coordinates according to which we represent the vectors and the plane. Instead of using the standard e_1 ... e_N vectors, let us switch to a different set of N orthonormal vectors e'_1 ... e'_N.

We will choose these new vectors in a way that is similar to an orthonormalization process: e'_1 will be the unit vector in the direction of V_1. (If V_1 is the zero vector, choose e'_1 arbitrarily.) Each subsequent e'_i will be the unit vector in the direction of V_i's component in the direction perpendicular to the already spanned subspace. (If V_i is inside the subspace, choose e'_i arbitrarily.)

Using this new system of coordinates, let us denote u and v as column vectors and M as the matrix in which the i'th row is the vector V_i.

The desired property can now be described as follows: M*u and M*v are equal-sized and perpendicular to each other.

Note that due to the special coordinate system, M is a matrix containing only zeros above the diagonal.

In order to prove necessity, let us use e'_i and e'_j as u and v.

First, take i=N.
The vector M*u will be (0,0,0,....,0,M[N,N]).
For any choice of j, the vector M*v must have zero as its last coordinate, for the two vectors to be perpendicular.
For j=N-1, the vector M*v must be (0,0,0,.....,0,M[N,N],0), or else the two vectors will not be of equal size.

This process can be repeated inductively with i decreasing from N to 1. Its ultimate result is that M=I*c, for some constant c, not equal to zero. This means that V_i=c*e'_i. They are a scaled orthonormal system.

In order to prove sufficiency, we must show that the property holds for any u and v given that M=I*c. In this case:

M*u = c*u
M*v = c*v

Because u and v have been defined as perpendicular vectors of equal length (a unit), the same must be true for their scaled versions.

Q.E.D.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com