Ponder This Challenge - December 2004 - Projecting points onto the complex plane

Ponder This Challenge:

Puzzle for December 2004

This month's puzzle is proposed by Michael Brand.

Consider N vectors, V_1 ... V_N, (not all zero) in an N-dimensional space. Project these vectors orthogonally to a 2-dimensional plane, P. Let us denote the results for the i'th vector as (a_i,b_i) in Cartesian coordinates defined on the plane. We will be interested in considering these coordinates as a complex number: x_i = a_i + j*b_i.

Now, these N vectors hold the following property: regardless of the chosen P, the sum of all {x_i}^2 is always equal to 0.

The question: give an explicit description of the property that the N vectors most hold. Prove that this property is both sufficient and necessary.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  ANSWER:

  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

Solvers

• Dan Dima (12.01.2004 @10:28:45 AM EST)
• Raicho Tchalkov (12.01.2004 @11:52:08 AM EST)
• Stephen Lesko (12.01.2004 @03:35:49 PM EST)
• Rubén Hernández Aza (12.01.2004 @04:04:32 PM EST)
• Divyesh Dixit (12.01.2004 @04:30:23 PM EST)
• Frank Mullin (12.01.2004 @04:41:18 PM EST)
• Dion K Harmon (12.01.2004 @08:01:40 PM EST)
• Patrick J. LoPresti (12.01.2004 @11:22:38 PM EST)
• Yong Liu (12.02.2004 @09:27:34 AM EST)
• Vineet Dwivedi (12.02.2004 @11:48:15 AM EST)
• Kalyana Chakravarthy (12.02.2004 @01:34:03 PM EST)
• Max Alekseyev (12.02.2004 @06:59:45 PM EST)
• Vineet Gupta (12.02.2004 @08:17:23 PM EST)
• Piotr Zielinski (12.02.2004 @09:08:06 PM EST)
• Eugene Vasilchenko (12.03.2004 @01:05:16 AM EST)
• Amit Jayant Deshpande (12.03.2004 @01:05:16 AM EST)
• John Ritson (12.03.2004 @05:29:52 AM EST)
• Mayank Kabra (12.03.2004 @08:50:23 AM EST)
• Luke Pebody (12.03.2004 @12:50:23 AM EST)
• Hao Wu (12.03.2004 @01:07:25 PM EST)
• Golovach Ivan (12.03.2004 @01:41:39 PM EST)
• Lauri Ylinen (12.03.2004 @03:39:03 PM EST)
• Alexandru Sofronia (12.04.2004 @04:42:55 PM EST)
• Hagen von Eitzen (12.04.2004 @05:33:34 PM EST)
• Vanhulle Christian (12.04.2004 @06:15:53 PM EST)
• Erick Wong (12.05.2004 @02:19:51 AM EST)
• Kevin Costello (12.05.2004 @07:05:44 AM EST)
• Hoffmann Klaus (12.05.2004 @11:16:29 AM EST)
• John G. Fletcher (12.05.2004 @07:45:56 PM EST)
• Avi Gozolchiani (12.06.2004 @11:22:00 AM EST)
• Zabara Maxim (12.06.2004 @09:26:39 AM EST)
• Yakov Sirotkin (12.06.2004 @03:42:23 PM EST)
• Kim Se Kwon (12.06.2004 @08:23:53 PM EST)
• Dharmadeep Muppalla (12.08.2004 @05:35:13 AM EST)
• Devin Myers (12.08.2004 @10:44:01 AM EST)
• Claudio Baiocchi (12.09.2004 @07:04:51 AM EST)
• Jose H. Nieto (12.10.2004 @10:50:14 PM EST)
• John Tromp and Troy Lee (12.13.2004 @03:48:41 AM EST)
• Sergey Povetkin (12.15.2004 @11:33:57 AM EST)
• Alan O'Donnell (12.15.2004 @05:14:36 PM EST)
• Bhaskara Aditya (12.16.2004 @10:15:27 AM EST)
• Michael Nedzelsky (12.16.2004 @05:44:20 PM EST)
• Andreas Kabel (12.17.2004 @07:48:11 PM EST)
• Chris Hills (12.20.2004 @09:38:19 AM EST)
• Siddhartha Kanungo (12.22.2004 @11:55:22 AM EST)
• Leonardo Liang (12.24.2004 @04:32:22 AM EST)
• Dr. Bert Fischer (12.24.2004 @05:46:19 AM EST)
• Nagi Nahas (12.24.2004 @03:07:43 PM EST)
• Mihai Cioc (12.24.2004 @06:55:23 PM EST)
• Alex Tikhonov (12.28.2004 @09:29:46 AM EST)
• Ananda Raidu (12.31.2004 @06:56:46 AM EST)
• IQSTAR (12.31.2004 @11:42:38 AM EST)
• Jonathan Poritz (12.31.2004 @02:18:00 PM EST)
• Aditya K. Prasad (12.31.2004 @07:48:28 PM EST)
• Ramanjit Ahuja (01.03.2005 @11:10:55 AM EST)