What is Z_2^n and its role in proving the vertices of a hypercube in R^n?

[TheMathNoob]

Homework Statement

Attached is the problem.
I didn't find anyway to apply the hamming distance to this problem, but I hope that at least this is close to show something.

Homework Equations

The Attempt at a Solution

Lets consider Rn over Z 2 n, so the basis of R n under Z 2 is

(0,0,………0 )all the way until the n coordinate

(1,0,……….0) all the way until the n coordinate

(0,1…………0) all the way until the n coordinate

………………..

(0,0,………….1) all the way until the n coordinateBased on this sequence dim(basis)=n+1

I think that finding the total number of vectors in Rn over Z2 will be useful.

To find the total # of vectors in the vector space spanned by this basis, we can’t use each vector in the basis more than once in each group operation ( I will clarify this later with an example) because for some vectors, it will take us more than 1 unit away from the range. For example (1,0,0…0)+(1,0,0….0)= (2,0,0…) “not allowed”. We won’t take into account the zero vector hence just the vectors with non-zero coordinates will be enough to spanned the other vectors. Taking into account the 0 vector will generate duplicates in the next operation that I am about to performed. We will just use n vectors from the basis hence the 0 vector is discarded. What we are going to trying to do is to find the total number of groups that can be made out of these vectors. In each group, we will perform addition among the vectors and the outcome will be equivalent to one vector in the vector space. The mathematical idea to compute this is doing n choose 0 + n choose 1 + n choose 2+ n choose 3 … +n choose n, this is equal to 2^n-1 without considering the empty set by the binomial theorem. If we add back the 0 vector, the total number of vectors in this vector space is 2^n-1+1=2^n. The n-unit cube in R n over z2 has 2^n vertices, so each vertex must be represented in one coordinate. Hence there are 2^n coordinates, then each vector has to represent one vertex.

 

[fresh_42]

Homework Statement

Attached is the problem.
I didn't find anyway to apply the hamming distance to this problem, but I hope that at least this is close to show something.

Homework Equations

The Attempt at a Solution

Lets consider Rn over Z 2 n, so the basis of R n under Z 2 is

(0,0,………0 )all the way until the n coordinate

(1,0,……….0) all the way until the n coordinate

(0,1…………0) all the way until the n coordinate

………………..

(0,0,………….1) all the way until the n coordinateBased on this sequence dim(basis)=n+1

I think that finding the total number of vectors in Rn over Z2 will be useful.

To find the total # of vectors in the vector space spanned by this basis, we can’t use each vector in the basis more than once in each group operation ( I will clarify this later with an example) because for some vectors, it will take us more than 1 unit away from the range. For example (1,0,0…0)+(1,0,0….0)= (2,0,0…) “not allowed”. We won’t take into account the zero vector hence just the vectors with non-zero coordinates will be enough to spanned the other vectors. Taking into account the 0 vector will generate duplicates in the next operation that I am about to performed. We will just use n vectors from the basis hence the 0 vector is discarded. What we are going to trying to do is to find the total number of groups that can be made out of these vectors. In each group, we will perform addition among the vectors and the outcome will be equivalent to one vector in the vector space. The mathematical idea to compute this is doing n choose 0 + n choose 1 + n choose 2+ n choose 3 … +n choose n, this is equal to 2^n-1 without considering the empty set by the binomial theorem. If we add back the 0 vector, the total number of vectors in this vector space is 2^n-1+1=2^n. The n-unit cube in R n over z2 has 2^n vertices, so each vertex must be represented in one coordinate. Hence there are 2^n coordinates, then each vector has to represent one vertex.

I find the most difficult part of the exercise is to find out what to prove. Therefore you have to be quite exact in your language. $ℝ^n$ under or over $ℤ_2 = \{0,1\}$ doesn't make sense, neither does dimension of a basis. Basis here are finite sets, sets of $n$ elements.

The vector space $ℤ_2^n$ over the field $ℤ_2$ has a finite number of elements which can be counted directly. Its dimension is $n$.
The identification of the vertices of $Q_n$ with elements of $ℤ_2^n$ is rather obvious and already described in the exercise. You don't even have to use the word vector.

For the second part I admit that I do not understand it. The Hamming distance between two adjacent vertices should be exactly $1$ and not zero, as far as I see it. Again you only have to be exact in your wording since the edges of $Q_n$ in $ℝ^n$ are already described. In $ℤ_2^n$ there are no "edges" anymore since there are no points between vertices. So you only have adjacent vertices to define an edge.

 

[TheMathNoob]

I find the most difficult part of the exercise is to find out what to prove. Therefore you have to be quite exact in your language. $ℝ^n$ under or over $ℤ_2 = \{0,1\}$ doesn't make sense, neither does dimension of a basis. Basis here are finite sets, sets of $n$ elements.

The vector space $ℤ_2^n$ over the field $ℤ_2$ has a finite number of elements which can be counted directly. Its dimension is $n$.
The identification of the vertices of $Q_n$ with elements of $ℤ_2^n$ is rather obvious and already described in the exercise. You don't even have to use the word vector.

For the second part I admit that I do not understand it. The Hamming distance between two adjacent vertices should be exactly $1$ and not zero, as far as I see it. Again you only have to be exact in your wording since the edges of $Q_n$ in $ℝ^n$ are already described. In $ℤ_2^n$ there are no "edges" anymore since there are no points between vertices. So you only have adjacent vertices to define an edge.

I have to prove that the vertices of a hypercube in R^n are the vectors in the n dimensional vector space over Z_2. For example, if we look at R^2 over Z_2, you may realize that the possible strings of bits are 00,01,10,11. The basis for R2 over Z_2 are 00,01 and 1,0. I thought that finding the total number of vectors in R^n would be useful. I don't know how to do it. Can you explain what is Z_2^n because I see it like a subspace in R^n made out by vectors which coordinates are just 0 and 1.

 

[fresh_42]

I have to prove that the vertices of a hypercube in R^n are the vectors in the n dimensional vector space over Z_2. For example, if we look at R^2 over Z_2, you may realize that the possible strings of bits are 00,01,10,11. The basis for R2 over Z_2 are 00,01 and 1,0. I thought that finding the total number of vectors in R^n would be useful. I don't know how to do it. Can you explain what is Z_2^n because I see it like a subspace in R^n made out by vectors which coordinates are just 0 and 1.

$ℝ^2$ over $ℤ_2$ still doesn't make sense. $ℤ_2^n = \{0,1\}^n$ is no subspace in $ℝ^n$. What is done here is that the author defines the unit cube in $ℝ^n$ and the describes its $2^n$ vertices which formally can be identified by (all) the points of $ℤ_2^n$. Therefore there are only vertices in $ℤ_2^n$ and no edges because there are no more points left to build an edge. To encode edges anyway the author uses the fact that an edge (in $ℝ^n$) is also a connection between two adjacent vertices. So he now defines in $ℤ_2^n$ two adjacent vertices instead by using the Hamming distance. Both pictures of $Q_n$ are basically the same (which is to be verified, proven). However $ℝ^n$ and $ℤ_2^n$ are not! There are two different ways of encoding this $1-$skeleton $Q_n$. (You can imagine it as losing all points of the unit cube but the vertices when regarded in $ℤ_2^n$).

Edit: "Can you explain what is Z_2^n because I see it like a subspace in R^n made out by vectors which coordinates are just 0 and 1." Yes, except the fact that it is no subspace. It is a subset here.