Let v=(x[1],...,x[n]) be a n-dimensional real vector. Find the dimension of the subspace of R^n spanned by v and all vectors obtained by permuting the components of v.

Printable View

- May 1st 2006, 09:44 AMmbbx3wsbpermuting vectors
Let v=(x[1],...,x[n]) be a n-dimensional real vector. Find the dimension of the subspace of R^n spanned by v and all vectors obtained by permuting the components of v.

- May 1st 2006, 12:38 PMrgep
The answer is "it depends". Consider, for example, the permutations of (1,1,1,...1) and the permutations of (1,0,0,...,0).

- May 2nd 2006, 12:47 AMJakeD
Rgep's examples suggest to me this conjecture: The dimension of the subspace is 0 if , 1 if for some , and otherwise. Suggestions for a proof or counter-examples?

- May 2nd 2006, 10:14 AMRebesques
Well, that seems to be the case. The proof is really straightforward, let have a nonzero entry a at the i-th place: . We can take , as otherwise we can consider .

Let be the subspace created by and its permutations, and consider the j-axis of .

We consider a permutation of with 1 occupying the j-th place, and denote the vector obtained by .

Then

where is the jth euclidean basis vector. And

This proves contains the j-th axis of . So contains every axis, and therefore . - May 2nd 2006, 01:40 PMThePerfectHacker
Generalizing what rgep said, it seems to me I was (unable to prove it).

That there are only two cases, given,

And if

Then, the dimension of this subspace is 1.

Otherwise its dimension is - May 2nd 2006, 04:29 PMRebesques
-Doctor, i feel people don't pay attention to me.

-Who's next please? :D - May 2nd 2006, 07:00 PMThePerfectHacker
Sorry, 'bout that did not wish to steal anyone's answers :o I just found the problem interesting.

Quote:

Originally Posted by**JakeD**

- May 2nd 2006, 08:22 PMCaptainBlackQuote:

Originally Posted by**ThePerfectHacker**

RonL - May 3rd 2006, 03:49 AMRebesquesQuote:

Sorry, 'bout that did not wish to steal anyone's answers

I just felt invisible for a moment there :o :p - May 3rd 2006, 01:18 PMThePerfectHackerQuote:

Originally Posted by**CaptainBlack**

- May 6th 2006, 02:08 PMJakeD
In working up a proof of my conjecture, I found a counter example and had to revise the conjecture. (Rebesques, take note. :( ) Here is the revised conjecture and a proof.

Let The dimension of the subspace spanned by and its permutations is

As examples in , for while for

Claims C and D are proven by showing that the given number is the maximum number of independent linear combinations of and its permutations. So assume for any Under this assumption we may further assume wlog that

since we can permute as we like. Let

We will use the following linear combinations of and its permutations.

Putting these vectors into a matrix

it is clear that the first vectors are linearly independent and their elements sum to zero. If the elements of the last vector do not sum to zero, it will be independent of the first vectors and the number of independent vectors in will be the maximum possible. This proves claim D.

Proving C, if the elements of the last vector sum to zero, it will be linearly dependent on the first vectors. Since the last vector could represent any permutation of , this means there cannot be more than independent vectors in This proves C and completes the proof.