Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I - MathOverflow

Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I

2011-02-04T18:11:21Z

Hello everyone,

I have a very interesting question on orthogonal projection matrices. Intuitively it is quite straightforward to understand. But for me it is not easy to prove.

In $R^2$ space, $a_i$, $i=1,..,n>2$ are unit verctors, which are located on the unit circle uniformly. That means the angle subtended by any adjacent vectors is $2\pi/n$. It is known $A_i=a_ia_i^T$ is an orthogonal projection matrix satisfying $A_i^T=A_i$ and $A_i^2=A_i$.

Prove: $A_1+..+A_n=a_1a_1^T+...+a_na_n^T=n/2I$ where $I$ is the identity matrix.

Remark: 1. Intuitively, consider three vectors. If their sum is zero, the vectors are distributed on the unit circle uniformly. 2. Guess: In $R^d$ space instead of $R^2$, the 1/2 in the equation should be 1/d. 3. My approach: prove $B=a_1a_1^T+...+a_na_n^T$ equals $n/2I$ if and only if $Bx=n/2x$ for arbitrary $x$ in $R^2$. Maybe a bad approach.

Thank you very much!

Shiyu

PS: consider the converse question: if $a_1a_1^T+...+a_na_n^T=n/2I$, can we say $a_1+...+a_n=0$? Answer: using Nick's method, it can be shown this converse statement does not hold. Please refer to Nick's solution.

Now I'd like to pose a more general question.

If $\sum k_ia_i=0$ where $k_i>0$ and $\sum k_i=1$, then $ \sum k_ia_ia_i^T=1/dI$ where $d$ is the dimension of the space $R^d$.

The original problem in fact is a special case of the above statement where $k_i=1/n$. Of course, this above statement is wrong becasue I must add some hypothesis like the unit vectors $a_i$ should be located on the unit circle uniformly. But I am not sure how to state it rigorously at present.

Answer by Alan for Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I

2011-02-04T18:33:41Z

This is false.

If $a_1 + \cdots + a_n=0$ and if $a_1 a_1^T + \cdots a_n a_n^T = (1/2)I$, then $$(a_1 + \cdots + a_n)+(a_1+\cdots a_n)=0$$ and $$(a_1 a_1^T + \cdots a_n a_n^T)+(a_1 a_1^T + \cdots a_n a_n^T) = I.$$ So, having a sum of unit vectors be zero, does NOT imply that the sum of the matrices $a_i a_i^T$ is $(1/2)I$.

You are missing a hypothesis.

Answer by David Speyer for Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I

2011-02-04T19:08:58Z

OK, here might be an answer to the question you are meaning to ask:

Let $a_1$, ..., $a_n$ be unit vectors in $\mathbb{R}^d$. Let $G$ be a group acting linearly on $\mathbb{R}^d$, which permutes the $a_i$, and such that the representation $\mathbb{R}^d$ of $G$ is irreducible. For example, maybe $d=2$ and $G$ is the cyclic group of order $n$ acting by rotations. This seems to be the example you started out thinking of. Note that, when $n=2$, this representation is not irreducible, which gives you darij's counterexample.

Then I claim that $\sum a_i a_i^T = (n/d) \mathrm{Id}$.

Proof: $\sum a_i a_i^T$ is the matrix of a $G$ invariant bilinear form. Since $\mathbb{R}^d$ is irreducible, the space of such forms is one dimensional and $\sum a_i a_i^T = r \mathrm{Id}$ for some $r$. Taking traces of both sides, we get $n = rd$, so $r=n/d$.

Here is this answer written in the most elementary way I can: Let's first look at the case you started with, where the vector are evenly spaced at angle $\theta$. Let $g(\theta)$ be the matrix $\left( \begin{smallmatrix} \cos \theta & \sin \theta \\ - \sin \theta & \cos \theta \end{smallmatrix} \right)$ . Then we have $$g(\theta) \left( \sum a_i a_i^T \right) g(-\theta) = \sum \left( g(\theta) a_i \right) \left( g(\theta) a_i \right)^T = \sum a_i a_i^T$$ where the second equality is because multiplying by $g(\theta)$ permutes the $a_i$'s. So the sum $Q:=\sum a_i a_i^T$ obeys $g(\theta) Q g(-\theta) = Q$. This is a collection of four linear equations in the entries of $Q$. (Computationally, you may find it easier to work with the equivalent $g(\theta) Q = Q g (\theta)$.) As long as $\theta$ is not a multiple of $\pi$, the space of solutions is $1$-dimensional, spanned by the identity matrix. So $Q=r \mathrm{Id}$ for some $r$. Taking traces of both sides, $r=n/2$.

Now, what to do in higher dimensions? Are the vertices of a cube regularly spaced? What about a dodecahedron? The answer is yes, and group representation theory is the correct vocabulary to explain why. Let $g_1$, $g_2$, ..., $g_k$ be a finite collection of orthogonal matrices permuting the $a_i$ amongst themselves. So, the rotational symmetries of the cube or the dodecahedron or, back in your original example, the matrix $g(\theta)$.

Set $Q = \sum a_i a_i^T$. Just like before, we deduce that $g_1 Q = Q g_1$, $g_2 Q = Q g_2$, ..., $g_k Q = Q g_k$. This is a bunch of linear equations for $Q$. If the space of solutions to these equations is one-dimensional, we win!

We now come to a nontrivial theorem: The space of solutions to these equations is one dimensional if and only if there is no linear subspace $V$ of $\mathbb{R}^d$ (other than $(0)$ and $\mathbb{R}^d$ itself) such that $g_i V = V$ for each $g_i$. For the cube, the dodecahedron, the original evenly spaced points, and many harder examples, this is easily checked. For the case darij raised, of two points evenly spaced at distance $\pi$, this condition fails: every line through the origin is taken to itself under $g(\pi)$.

Some vocabulary: It is usual to work not just with the $g_i$, but with all of their products. (For example, working with not just $g(\theta)$ but $g(2 \theta)$, $g(3 \theta)$, etcetera.) Let $G$ be the set of all of these products. Since they permute a finite set of vectors, $G$ cannot be infinite. (Experienced mathematicians will see that I am glossing over something here, please let me do so.) For example, in our two dimensional example, $\theta/\pi$ cannot be irrational. So $G$ is finite, and is what is called a finite group. Every element of $G$ is a symmetry of $\mathbb{R}^d$, so we say that $G$ acts on $\mathbb{R}^d$ and those actions are by linear maps so we say that $G$ acts linearly. In this setting of a group acting linearly, we say that $\mathbb{R}^d$ is a representation of $G$. The condition that there be no subspace of $\mathbb{R}^d$ which is taken to itself by $G$ is usually stated using the technical term: $\mathbb{R}^d$ is an irreducible representation.

A personal note: If you aren't comfortable switching between matrices and bilinear forms, you don't know the vocabulary of groups and group actions, and you have never seen any group representation theory, you might fit in better at math.stackexchange.com than here. That said, nice problem! I may save it for when I teach representation theory.

Answer by Igor Rivin for Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I

2011-02-04T19:29:26Z

This is for the original question, not the "distributed uniformly" version, which is not very interesting. in $d=2,$ if you use complex numbers, the OP is equivalent to asserting that if $z_1, \dotsc, z_n$ are unit complex numbers such that $\sum z_k = 0,$ then $\sum z_k^2 = 0.$ (Proof: write the projection matrices in terms of sines and cosines). This is obviously false, since you can put $n/2$ of the $z_k$ near $1$ and the other $n/2$ be the negations of the first $n/2.$

Answer by Nick S for Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I

2011-02-04T22:50:52Z

Here is an elementary solution:

Let $a_1=(\cos(\theta), \sin(\theta))$ then $a_i= \cos(\theta+\frac{2(i-1)\pi}{n}), \sin(\theta+\frac{2(i-1)\pi}{n})$ thus

$$a_i a_i^T= \left( \begin{array}{c c} \cos^2(\theta+\frac{2(i-1)\pi}{n}) & \cos(\theta+\frac{2(i-1)\pi}{n})\sin(\theta+\frac{2(i-1)\pi}{n}) \\ \cos(\theta+\frac{2(i-1)\pi}{n})\sin(\theta+\frac{2(i-1)\pi}{n}) & \sin^2(\theta+\frac{2(i-1)\pi}{n}) \\ \end{array} \right)$$

Now the result follows imediatelly from the simple trig identities

$$\sum_{i=1}^n \cos^2(\theta+\frac{2(i-1)\pi}{n})= \sum_{i=1}^n \sin^2(\theta+\frac{2(i-1)\pi}{n}) =n/2$$

$$\sum_{i=1}^n \cos(\theta+\frac{2(i-1)\pi}{n})\sin(\theta+\frac{2(i-1)\pi}{n})=\frac{12}{2} \sum_{i=1}^n \sin(2\theta+\frac{4(i-1)\pi}{n})=0 \,.$$

The last question in the problem is equivalent to the following:

Does

$$\sum_{i=1}^n \cos^2(\theta_i)= \sum_{i=1}^n \sin^2(\theta_i) =n/2$$

$$ \sum_{i=1}^n \sin(2\theta_i)=0 \,.$$

imply

$$ \sum_{i=1}^n \sin(\theta_i)=\sum_{i=1}^n \cos(\theta_i)=0 \,?$$

P.S. Can anyone fix my matrix?

Prove: if a1,...,an are uniformly distributed unit vectors, then a1*a1'+...+an*an'=n/2*I - MathOverflow

Prove: if a1,...,an are uniformly distributed unit vectors, then a1*a1'+...+an*an'=n/2*I

Answer by Alan for Prove: if a1,...,an are uniformly distributed unit vectors, then a1*a1'+...+an*an'=n/2*I

Answer by David Speyer for Prove: if a1,...,an are uniformly distributed unit vectors, then a1*a1'+...+an*an'=n/2*I