Someone please explain what is the meaning of the words in shade

From Proof from the Book, 4th edition page 96:

Let $q$ be a prime power, set $n=4q-2$, and let

$$Q = \{x \in \{+1,-1\}^n: x_1 = 1, \#\{i:x_i=-1\} \text{ is even}\}.$$

This $Q$ is a set of $2^{n-2}$ vectors in $\Bbb R^n$.

We will see that $\langle x,y \rangle \equiv 2 \pmod 4$ holds for all vectors $x,y \in Q$.

Remark: These 4 sentences came together.

And I need to understand what is $|\langle x,y \rangle|$ is in.

We will call $x,y$ nearly orthogonal if $|\langle x,y \rangle|=2$.

  • 2
    $\begingroup$ "the book"? I guess there is only one... $\endgroup$ – Arturo Magidin Jul 20 '12 at 22:08
  • 1
    $\begingroup$ Do you mean, "Proofs from the Book", 4th Edition? $\endgroup$ – Arturo Magidin Jul 20 '12 at 22:13
  • $\begingroup$ @ArturoMagidin - Yes, and thank you again for your answer below $\endgroup$ – Victor Jul 20 '12 at 22:24

$\langle x,y\rangle$ denotes the result of applying the inner product of $\mathbb{R}^n$ to the vectors $x$ and $y$ (which happen to be in $Q$); in this case, it is the usual "dot product". $|\langle x,y\rangle|$ denotes the absolute value of that operation.

E.g., $q=2$, $n=6$, $x=(1,-1,1,1,-1,1)$, $y = (1,1,-1,1,1,-1)$, then $$\langle x,y\rangle = (1)(1) + (-1)(1) + (1)(-1) + (1)(1) + (-1)(1) + (1)(-1) = -2$$ so $|\langle x,y\rangle| = |-2| = 2$.

  • $\begingroup$ What is $\#\{i:x_i=-1\} \text{ is even}\$ mean? $\endgroup$ – Victor Jul 20 '12 at 22:11
  • $\begingroup$ @Victor: If you have multiple questions about the notation, why not put them all in the question in the first place? It means "the cardinality" ($\#$) "of the set of indices corresponding to entries equal to $-1$". In other words, you are looking at vectors in $\mathbb{R}^n$, all of whose entries are either $1$ or $-1$, and such that the number of entries that are equal to $-1$ is even. $\endgroup$ – Arturo Magidin Jul 20 '12 at 22:13
  • $\begingroup$ Appreciate to Arturo Magidin $\endgroup$ – Victor Jul 20 '12 at 22:21

$Q = \{x \in \{+1,-1\}^n: x_1 = 1, \#\{i:x_i=-1\} \text{ is even}\}.$

$Q$ is the set of all vector $x$ with all of the following conditions:

  1. $x$ is a $n$-dimensional vector with entries $+1$ or $-1.$

  2. The first entry in, $x_1 = 1.$

  3. The number of indices $i$ where $x_i = -1$ is even. The cardinality of such set is even. i.e., the number of $-1$ component in the vector is even.

This $Q$ is a set of $2^{n-2}$ vectors in $\Bbb R^n$.

$Q \subset \Bbb R^2,$ and the number of vectors in $Q$ is $2^{n-2}.$

We will see that $\langle x,y \rangle \equiv 2 \pmod 4$ holds for all vectors $x,y \in Q$.

The inner product between any two vectors in $Q$ is congruent to $2$ modulo 4.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.