0

Exercise 1.18 in Rudin states:

Rudin Exc 1.18) If $k \geq 2$ and $x \in \mathbb{R}^k$, prove that there exists $y \in \mathbb{R}^k$ such that $y \neq 0$ but $x \cdot y = 0$. Is this also true if $k = 1$?

I'm trying to understand a solution to the first half of this problem. The $x = 0$ case is immediate, as any $y \neq 0$. So we suppose $x \neq 0$. So $x = (x_1, \ldots, x_k)$ has at least one non-zero component, $x_i$. The proof then says, "without loss of generality, permuting indices if necessary, we can assume $x_1 \neq 0$." It then constructs a $y$ on that basis.

Why does this not sacrifice generality? It only treats a certain subset of $x$ with non-zero first components. Is the idea that I could have done this construction for any index, so I might as well do it for the $i$th decimal position? It seems more naturally to me to just pick an arbitrary $i \in \{1, \ldots, n\}$.

Thomas Andrews
  • 177,126
JohnT
  • 1,368
  • 1
    Because if $x\ne 0$, there exist at least one $x_i\ne 0$ and you can swap $x_1$ and $x_i$ in your base. – FreeFunctor Jan 14 '22 at 16:47
  • 3
    Related. WLOG does not mean we are handling all the cases, just that handling these cases is “enough” to deduce all cases. https://math.stackexchange.com/a/257961/7933 – Thomas Andrews Jan 14 '22 at 16:51
  • 1
    We can instead prove it without this technique. If $x_1=0,$ we let $y_1=1, y_i=0$ for $i>1.$ And if $x_1\neq 0,$ then $y_1=x_2,y_2=-x_1$ and $y_i=0$ for $i>2.$ – Thomas Andrews Jan 14 '22 at 16:58
  • 1
    WLOG usually means there is an “obvious” approach to vary the proof to handle the other cases. I wouldn’t have used it here, because it is so easy to do it directly, but I suppose Rudin might have chosen it precisely because it is a useful tool in general and part of the purpose of the book is to introduce you to proofs. – Thomas Andrews Jan 14 '22 at 17:02
  • 2
    Here, if $\pi$ is a permutation of ${1,2,\dots,n},$ then $Tx=(x_{\pi 1},\dots,x_{\pi n})$ permutes the vector entries, and it is easy to see that $(Tx)\cdot (Ty)=x\cdot y,$ and if $y$ is non-zero, then $Ty$ is non-zero. This is a lot of verbiage for something that is essentially “obvious.” – Thomas Andrews Jan 14 '22 at 17:06
  • @ThomasAndrews: Those last comments would make a good answer. I don't think that the other link is really quite enough to explain what WLOG means in the context of this post. – Lee Mosher Jan 14 '22 at 17:35
  • @ThomasAndrews This is very helpful, but could you explain how we know $Tx \cdot Ty = x \cdot y$? This is the only thing I'm not able to fully follow. – JohnT Jan 14 '22 at 17:37
  • @johnT it follows because if we consider $(Tx)\cdot(Ty),$ written as a sum, it is just a rearrangement of the sum for $x\cdot y,$ and addition is commutative and associate, and rearranging a finite sum does not change the value. – Thomas Andrews Jan 14 '22 at 17:49

1 Answers1

3

When mathematicians say “without loss of generality,” they are usually saying, “We can handle the other cases similarly,” or “We can deduce the other cases from this subset of cases.”

Often, writing out the other cases just adds noise to the proof, adding “obvious” logic to get it to work.

Here, by referencing permutation, Rudin seems to mean “We can deduce the other cases.”

He could have just as well meant, “We can handle the other cases similarly.” The general $i$ just requires a $j\neq i$ for $1\leq j\leq k$ and we can define $y$ in terms of $x, i,j.$

If you were to flesh out Rudin’s “permute” proof, you’d have to make explicit some things about permutations and the dot product.

Specifically, for a permutation $\pi$ on $\{1,2,\dots,k\}$ we can define a function $T_{\pi}:\mathbb R^k\to\mathbb R^k$ defined as: $$T_\pi(x_1,\dots,x_k)=\left(T_{\pi (1)},\dots,T_{\pi (k)}\right)$$

Then:

Lemma 1: For any $i,$ there is a permutation $\pi$ such that $\pi(1)=i.$

Lemma 2: $T_{\pi}(x)=0\iff x=0$

Lemma 3: $T_{\pi}(x)\cdot T_{\pi}(y)=x\cdot y.$ (This is essentially that addition is commutative and associative. The left side is just a permutation of the sum on the right.)

Lemma 4: $T_{\pi}\left(T_{\pi^{-1}}(x)\right)=x.$

From these Lemmas, we can deduce the general case of some $x_i\neq 0$ from the case when $x_1\neq 0.$

If $x_i\neq 0,$ then, by Lemma 1, there is a $\pi$ such that $\pi(1)=i,$ and then $x’=T_{\pi}(x)$ is a vector with $x_1’=x_i\neq 0.$ So there is a $y’\neq 0$ with$x’\cdot y’=0.$

Then we let $y=T_{\pi^{-1}}(y’)$ and we use the other lemmas to prove $y\neq 0$ and $x\cdot y=0.$

All of this is essentially obvious, although writing it out this way is verbose and obscures the fact that it is essentially trivial. (I’d argue it is worth sometimes writing out such obvious things in this long form, just for the experience, but it is terrible as a form of communication.)

As I noted in a comment above, Rudin could have avoided “without loss of generality” here, just by considering the two cases $x_1=0$ and $x_1\neq 0.$

I suspect that Rudin uses this technique here because, in addition to teaching you real analysis, the goal of Rudin’s book is to introduce you to proofs, and “without loss of generality” is a very common and useful technique for simplifying proofs.

Thomas Andrews
  • 177,126
  • This is verbose. In fact Rudin starts by assuming $x_i\ne 0$ si it is enough to consider the permutation $i \leftrightarrow 1$, which in turn reduces to choosing a different basis ${e_i, \dots e_1 \dots e_n}$. – Miguel Jan 14 '22 at 18:23
  • Careful: “A different basis” doesn’t give you the same dot product, unless the different basis is a permutation of the original basis. Unless you meant a different orthonormal basis, but this is a basic question about dot products, and usually orthonormal bases aren’t covered until after such basic theorems about dot products. My answer is definitely verbose, but I wanted to make clear that (1) writing it out is cumbersome, and (2) how essentially it is trivial. @Miguel – Thomas Andrews Jan 14 '22 at 19:04
  • In any event, I can certainly imagine a course which teaches about the dot product before the concept of basis and change of basis. Don’t know how much Rudin covers linear algebra before this section, but my memory is he doesn’t assume any knowledge of linear algebra before you read the book, at least. (Nor formal notions of permutations, for that matter, of course. The argument is highly informal and meant to be read as intuitively obvious.) @Miguel – Thomas Andrews Jan 14 '22 at 19:36
  • Indeed I explicitly wrote the basis permutation. But I appreciate your effort that trivial things must be written at least once in life. – Miguel Jan 14 '22 at 19:38