城南讲马堂

陶哲轩实分析8.5及习题-Analysis I 8.5-part 2

2019年9月19日2019年12月19日christangdt22条评论

本节为8.5习题第二部分，包含13-20题。

Exercise 8.5.13. Prove the claim in the proof of Lemma 8.5.14, namely that every element of $Y'\backslash Y$ is an upper bound for $Y$ and vice versa.

Solution: We first prove the result using Principle of strong induction. Let $P(a)$ be the property

$\{y\in Y:y\leq a\}=\{y\in Y':y\leq a\}=\{y\in Y\cap Y':y\leq a\}$

Then $P(x_0 )$ is true, since the three sets all equal to $\{x_0 \}$ .
Now suppose given some $n\in (Y\cap Y' )\backslash \{x_0\}$ , and for any $m\in Y\cap Y',m<n, P(m)$ is true, we consider $P(n)$ . Assume $P(n)$ is false, then we must have

$\{y\in Y:y\leq n\}\neq \{y\in Y':y\leq n\}$

so at least one of the set $A=\{y\in Y\backslash Y':y\leq n\}$ and $A'=\{y\in Y'\backslash Y:y\leq n\}$ shall be non-empty, we first suppose $A\neq \emptyset$ , since $A\subseteq Y$ , and $Y$ is well-ordered, we can find a minimum of $A$ , namely $\min A\in A$ , as $\min A\notin Y'$ , we have $\min A<n$ . Next we define

$B:=\{y\in Y:y<\min A \}$

since $Y$ is good and $\min A\in Y$ , we have $\min A=s(B)$ , and for any $b\in B$ , if $b\notin Y'$ , then $b\in Y\backslash Y'$ and $b<\min A<n$ , so $b\in A$ , contradicting the definition of $\min A$ , we can conclude $B\subseteq Y\cap Y'$ .
Define $C:=\{y\in Y'\backslash B:y\leq n\}$ , then $C\subseteq Y'$ and is not empty $(n\in C)$ , as $Y'$ is well-ordered, we can find a minimum of $C$ , namely $\min C\in C$ , since $\min C\in Y'$ and $Y'$ is good, we have

$\min C=s\{y\in Y':y<\min C \}$

Obviously $\min C\leq n$ . If $y\in Y',y<\min C$ , then we must have $y\in B$ , otherwise $y\in C$ , contradiction the definition of $\min C$ , from this we can see $\{y\in Y':y<\min C \}\subseteq B$ . Conversely if $b\in B$ , then $b\in Y'$ , assume $b\geq \min C$ , then using $b<\min A<n$ and the induction hypothesis we have $\min C\in \{y\in Y':y\leq b\}$ and

$\{y\in Y:y\leq b\}=\{y\in Y':y\leq b\}=\{y\in Y\cap Y':y\leq b\}$

thus $\min C\in \{y\in Y:y\leq b\}$ , so $\min C\in Y$ , a contradiction. So we must have $b<\min C$ , from this we can see $B\subseteq \{y\in Y':y<\min C \}$ , thus $B=\{y\in Y':y<\min C \}$ . As they are the same set, we shall have $\min C=s\{y\in Y':y<\min C \}=s(B)=\min A$ , but $\min A\in Y\backslash Y'$ and $\min C\in Y'$ , this is the final contradiction.
Next suppose $A'\neq \emptyset$ , then interchanging $Y$ and $Y'$ we can derive a contradiction, too. Thus $P(n)$ is true. Use Proposition 8.5.10 we conclude $P(a)$ is true for any $a\in Y\cap Y'$ .
To see $Y\cap Y'$ is good, we notice $Y\cap Y'$ is well-ordered, contains $x_0$ as minimum, and by the property of $P(a)$ we can see $x=s(\{y\in Y\cap Y':y<x\}),\forall x\in (Y\cap Y')\backslash \{x_0\}$ . Hence $s(Y\cap Y')$ exists by the assignment of $s$ .
If $Y\backslash Y'$ is non-empty, we can find $\min Y\backslash Y'$ since $Y$ is well-ordered. Also we know $Y$ is good, so $\min Y\backslash Y'=s(\{y\in Y:y<\min Y\backslash Y'\})$ , in fact, we have

$\{y\in Y:y<\min Y\backslash Y'\}=Y\cap Y'$

Because $\forall x\in \{y\in Y:y<\min Y\backslash Y'\}$ , if $x\notin Y'$ , then it’s a contradiction to the definition of $\min Y\backslash Y'$ . And if $x\in Y\cap Y'$ and $x\geq \min Y\backslash Y'$ , then the existence of $\min Y\backslash Y'$ would contradict the property $P(x)$ .
Thus $\min Y\backslash Y'=s(Y\cap Y' )$ if $Y\backslash Y'$ is non-empty, similarly we can get $\min Y'\backslash Y=s(Y\cap Y')$ if $Y'\backslash Y$ is non-empty, thus one of $Y\backslash Y'$ and $Y'\backslash Y$ must be empty. So we either have $Y\subseteq Y'$ or $Y'\subseteq Y$ , and
If $Y'\subseteq Y$ , then $Y\cap Y'=Y'$ and every element of $Y\backslash Y'$ is an upper bound of $Y'$ .
If $Y\subseteq Y'$ , then $Y\cap Y'=Y$ and every element of $Y'\backslash Y$ is an upper bound of $Y$ .

$\blacksquare$

Exercise 8.5.14. Use Lemma 8.5.14 to prove Lemma 8.5.15 (Zorn’s Lemma).

Solution: Suppose $X$ has no maximal elements, then for any $Y\subseteq X$ which has an upper bound $M\in X$ , we can find an $M'\in X,M'>M$ , then $M'\notin Y$ , otherwise $M$ can’t be an upper bound of $Y$ , and for any $y\in Y,y\leq M<M'$ , shows that $M'$ is a strict upper bound of $Y$ .
Now as $X$ is non-empty, we let $x_0\in X$ , then by Lemma 8.5.14, there’s a well-ordered set $Y$ , such that $Y$ has no strict upper bound. Notice that $Y$ is totally ordered, thus by the condition given, $Y$ has an upper bound, thus also have a strict upper bound, this leads to a contradiction.

$\blacksquare$

Exercise 8.5.15. Let $A$ and $B$ be two non-empty sets such that $A$ does not have lesser or equal cardinality to $B$ . Using the principle of transfinite induction, prove that $B$ has lesser or equal cardinality to $A$ .

$\blacksquare$

Exercise 8.5.16. Let $X$ be a set, and let $P$ be the set of all partial ordering of $X$ . We say that one partial ordering $\leq\in P$ is coarser than abother partial ordering $\leq'\in P$ if for any $x,y\in P$ , we have the implication $(x\leq y)\implies (x\leq' y)$ . Thus for instance the partial ordering in Exercise 8.5.3 is coarser than the usual ordering $\leq$ . Let us write $\leq \preceq \leq'$ if $\leq$ is coarser than $\leq'$ . Show that $\preceq$ turns $P$ into a partially ordered set; thus the set of partial ordering on $X$ is itself partially ordered. There is exactly one minimal element of $P$ ; what is it? Show that the maximal elements of $P$ are precisely the total orderings of $P$ . Using Zorn’s lemma, show that given any partial ordeing $\leq$ of $X$ there exists a total ordering $\leq'$ such that $\leq$ is coarser than $\leq'$ .

Solution:
$\preceq$ turns $P$ into a partially ordered set:
Reflexivity: given any $\leq \in P$ , we have $(x\leq y)\implies (x\leq y),\forall x,y\in X$ , so $\leq \preceq \leq$ .
Anti-symmetric: let $\leq ,\leq '\in P, \leq \preceq \leq ', \leq '\preceq \leq$ , then $\forall x,y\in X$ , we have $(x\leq y)\iff (x\leq ' y)$ , which means the two relations are equal.
Transitivity: let $\leq ,\leq ',\leq ''\in P, \leq \preceq \leq ', \leq '\preceq \leq ''$ , then $\forall x,y\in X$ , we have
$\Big((x\leq y)\implies (x\leq ' y)\implies (x\leq '' y)\Big) \implies \leq \preceq \leq ''$

The one minimal element of P is empty order relation $\leq _{\emptyset}$ .

The maximal elements of $P$ are the total orderings of $X$ :
Let $\leq _t$ be any total ordering of $X$ , then $\leq _t\in P$ , and assume there’s a $\leq \in P$ such that $\leq _t\preceq \leq$ and $\leq \neq \leq _t$ , then $\forall x,y\in X,(x\leq _t y)\implies (x\leq y)$ . Since $\leq _t$ is a total ordering of $X$ , $\forall x,y\in X$ , we have either $x\leq _t y$ or $y\leq _t x$ , this means either $x\leq y$ or $y\leq x$ , thus $\leq$ is also a total ordering, and if $x\leq y$ , we must have $x\leq _t y$ , so $\leq =\leq _t$ , a contradiction. Thus there’s not element of $P$ can satisfy $\leq _t\preceq \leq$ and $\leq \neq \leq _t$ , so $\leq _t$ is a maximal element of $P$ .

Given any $\leq \in P$ , there’s a total ordering $\leq '$ , s.t. $\leq \preceq \leq '$ :
Let the set $S=\{y\in P:\leq \text{ is coarser than }y\}$ . $S$ is a poset with $\preceq$ as the partial ordering. Since $\leq \in S, S$ is not empty. Let $S'$ be any totally ordered subset of $S$ .
We define $\leq _s$ as below: $x\leq _s y$ if $\exists R\in S',xRy$ . Since $S'$ is totally ordered, for distinct $x,y\in X$ , we can’t simultaneously have $xRy$ and $yR'x$ for $R,R'\in S'$ , because $R$ and $R'$ are comparable, $xRy\implies xR'y$ or $yR'x\implies yRx$ , leading to contradictions. Thus $\leq _s$ is well-defined.
Next, we show $\leq _s\in P$ . For reflexivity, since any $R\in S'$ satisfy $xRx,\forall x\in X$ , we have $x\leq _s x$ . For anti-symmetric, let $x\leq _s y$ and $y\leq _s x$ , then $\exists R,R'\in S',xRy,yR'x$ . We have $R\preceq R'$ or $R'\preceq R$ , if $R\preceq R'$ , then $xRy\implies xR' y$ , thus $x=y$ since $R'\in P$ , if $R'\preceq R$ , then $xR'y\implies xRy$ , thus $x=y$ since $R\in P$ . For transitivity, let $x\leq _s y, y\leq _s z$ , then $\exists R,R'\in S',xRy,yR'z$ . We have $R\preceq R'$ or $R'\preceq R$ , if $R\preceq R'$ , then $xRy\implies xR' y$ , thus $xR'z$ since $R'\in P$ , which means $x\leq _s z$ , if $R'\preceq R$ , then $yR'z\implies yRz$ , thus $xRz$ since $R\in P$ , which means $x\leq _s z$ .
Third, we show $\leq _s\in S$ , suppose we have $x\leq y$ , then $\forall R\in S',xRy$ since $\leq$ is coarser than $R$ , so we have $x\leq _s y$ by the definition of $\leq _s$ .
Last, we show $R\preceq \leq _s,\forall R\in S'$ . For any $x,y$ such that $xRy$ , we see $x\leq _s y$ by definition.
Now for $S'$ , we find $\leq _s$ to be the upper bound of it. This means the condition of Zorn’s Lemma is satisfied, so $S$ has a maximum, namely $\leq '$ . Since $\leq '\in S$ , we have $\leq \preceq \leq '$ . To show $\leq '$ is a total ordering, assume for some $a,b\in X$ we have neither $a\leq ' b$ nor $b\leq ' a$ , so we shall have both $a\leq b$ and $b\leq a$ invalid, then define a relation $R$ like this: $\forall x,y\in X, xRy$ if $x\leq y$ , and in addition $aRb$ . Then $R\in S$ , but $R \npreceq \leq '$ , since $aRb\nRightarrow (a\leq ' b)$ , this is a contradiction.

$\blacksquare$

Exercise 8.5.17. Use Zorn’slemma to give another proof of the claim in Exercise 8.4.2. Deduce that Zorn’s lemma and the axiom of choice are in fact logically equivalent.

Solution: Let $\Omega =\{Y\subseteq \bigcup_{{\alpha} \in I}X_{\alpha} :\#(Y\cap X_{\alpha} )\leq 1,\forall {\alpha} \in I\}$ . Then $\Omega$ is not empty. Let $S$ be a totally ordered subset of $\Omega$ , with the ordering relation to be $\subseteq$ .
Define $M_S=\{x\in \bigcup_{{\alpha} \in I}X_{\alpha} : x\in Y\text{ for some }Y\subseteq S\}$ , then $\forall A\in S,A\subseteq M_S$ by definition. Also, assume $\exists {\beta}$ ,s.t. $\#(M_S\cap X_{\beta} )\geq 2$ , then we can choose $a,b\in (M_S\cap X_{\beta} ), a\neq b$ . since $a,b\in M_S$ , there’s $A,B\in S$ , s.t. $a\in A,b\in B$ , as $S$ is totally ordered, we either have $A\subseteq B$ or $B\subseteq A$ , so either $a,b\in A$ or $a,b\in B$ , thus either $\#(A\cap X_{\beta} )\geq 2$ or $\#(B\cap X_{\beta} )\geq 2$ , both leads to contradiction. So $M_S\in \Omega$ , and is an upper bound of $S$ .
By Zorn’s lemma, there’s a maximal element of $\Omega$ . Let it be $M$ . Now assume that $\exists {\gamma}\in I$ , s.t. $M\cap X_{\gamma}=\emptyset$ , we choose an element $c\in X_{\gamma}$ and $M'=M\cup \{c\}$ , then $M'\in \Omega$ , since $\{X_{\alpha} \}$ are disjoint sets, but this contradicts $M$ to be the maximal element of $\Omega$ . So we can conclude for $\forall {\alpha} \in I,M\cap X_{\alpha} \neq \emptyset$ , since $M\in \Omega$ , we conclude $\forall {\alpha} \in I,\#(M\cap X_{\alpha} )=1$ .
Since Exercise 8.4.2 can deduce the axiom of choice, we can see Zorn’s lemma can deduce the axiom of choice, thus the two are logically equivalent.

$\blacksquare$

Exercise 8.5.18. Using Zorn’s lemma, prove Hausdorff’s maximality principle: if $X$ is a partially ordered set, then there exists a totally ordered subset $Y$ of $X$ which is maximal with respect to set inclusion (i.e. there is no other totally ordered subset $Y'$ of $X$ which contains $Y$ . Conversely, show that if Hausdorff’s maximality principle is true, then Zorn’s lemma is true. Thus by Exercise 8.5.17, these two statements are logically equivalent to the axiom of choice.

Solution: If $X=\emptyset$ , the conclusion is obvious since $Y=\emptyset$ is what we want. Now suppose $X\neq \emptyset$ .
Let $\Omega =\{Y\subseteq X:Y\text{ is totally ordered}\}$ , in which the order is set inclusion. Then $\Omega$ is not empty since singleton belongs to it. Let $S$ be a totally ordered subset of $\Omega$ , then the elements of $S$ are tosets of $X$ , denote

$M=\{x\in X:x\in A\text{ for some }A\in S\}$

then $\forall A\in S,A\subseteq M$ . To prove $M\in \Omega$ , let $\forall x,y\in M$ , then $\exists A,B\in S$ ,s.t. $x\in A,y\in B$ , we shall have $(A\subseteq B)\vee (B\subseteq A)$ , thus $(x,y\in A)\vee (x,y\in B)$ , so $x,y$ can be ordered, proving $M$ is a toset. Now we can say $M$ is an upper bound of $S$ .
By Zorn’s lemma, there’s a maximum of $\Omega$ , namely $\max \Omega$ . We have $\max\Omega \in \Omega$ , thus is a toset, and there’s no other toset which contains $Y$ , otherwise contradicting to the definition of $\max \Omega$ . So we proved Hausdorff’s maximality principle.
Conversely, if Hausdorff’s maximality principle is true, and we have a non-empty poset $X$ with every totally ordered subset has an upper bound, then we can first use Hausdorff to find a totally ordered subset $Y$ such that for any totally ordered subset $Y'\subseteq X$ , we have $Y'\subseteq Y$ . Next we let $m$ be the upper bound of $Y$ , and for $\forall x\in X$ , the set $\{x\}$ is a toset, since $x\leq x$ for whatever partially ordered relation $\leq$ on $X$ , so $(\{x\}\subseteq Y)\implies (x\in Y)\implies (x\leq m)$ . This means $m$ is a maximum of $X$ , and Zorn’s lemma is proved.

$\blacksquare$

Exercise 8.5.19. Let $X$ be a set, and let $\Omega$ be the space of all pairs $(Y,\leq)$ , where $Y$ is a subset of $X$ and $\leq$ is a well-ordering of $Y$ . If $(Y,\leq)$ and $(Y',\leq')$ are elements of $\Omega$ , we say that $(Y,\leq)$ is an initial segment of $(Y',\leq')$ if there exists an $x\in Y'$ such that $Y:={y\in Y':y<'x}$ (so in particular $Y\subsetneq Y'$ ), and for any $y,y'\in Y,y\leq y'$ if and only if $y\leq' y'$ . Defing a relation $\preceq$ on $\Omega$ by defining $(Y,\leq)\preceq (Y',\leq')$ if either $(Y,\leq)=(Y',\leq')$ , or if $(Y,\leq)$ is an initial segment of $(Y',\leq')$ . Show that $\preceq$ is a partial ordering of $\Omega$ . There is exactly one minimal element of $\Omega$ ; what is it? Show that the maximal elements of $\Omega$ are precisely the well-orderings $(X,\leq)$ of $X$ . Using Zorn’s lemma, conclude the well ordering principle: every set $X$ has at least one well-ordering. Conversely, use the well-ordering principle to prove the axiom of choice, Axiom 8.1.

Solution:
$\preceq$ is a partial ordering of $\Omega$ :
Reflexivity: $(Y,\leq )=(Y,\leq )$ , thus $(Y,\leq )\preceq (Y,\leq )$ .
Anti-symmetric: Let $(Y,\leq )\preceq (Y',\leq ' )$ and $(Y',\leq ' )\preceq (Y,\leq )$ , assume $(Y,\leq )\neq (Y',\leq')$ , then $(Y,\leq )\preceq (Y',\leq ' )$ means $Y\subsetneq Y'$ , and $(Y',\leq ' )\preceq (Y,\leq )$ means $Y'\subsetneq Y$ , a contradiction.
The only remaining possibility is $(Y,\leq )=(Y',\leq ' )$
Transitivity: Let $(Y,\leq )\preceq (Y',\leq ' )$ and $(Y',\leq ' )\preceq (Y'',\leq '' )$ , if either $(Y,\leq )=(Y',\leq ' )$ or $(Y',\leq ' )=(Y'',\leq '' )$ the result is obvious. If $(Y,\leq )$ is an initial segment of $(Y',\leq ' )$ , and $(Y',\leq ' )$ is an initial segment of $(Y'',\leq '' )$ , then

$\exists x_1\in Y',\text{ s.t. }Y:={y\in Y':y<' x_1 } ,\quad \exists x_2\in Y'',\text{ s.t. }Y':={y\in Y'':y<'' x_2 }$

Also for

$\forall y,y'\in Y,(y\leq y')\iff (y\leq ' y' ) \\ \forall y,y'\in Y',(y\leq ' y')\iff (y\leq '' y' )$

So since $Y'\subseteq Y'', x_1\in Y''$ , and we also have $y\in Y\implies y\in Y'\implies y\in Y''$ , so

$(y<' x_1 )\iff (y\leq ' x_1 )\wedge (y\neq x_1)\iff (y\leq '' x_1 )\wedge (y\neq x_1)\iff (y<'' x_1)$

Thus $\exists x_1\in Y'',\text{ s.t. }Y:={y\in Y'':y<'' x_1 }$ . And $\forall y,y'\in Y$ , we have $y,y'\in Y'$ , so

$(y\leq y')\iff (y\leq ' y' )\iff (y\leq '' y' )$

The one minimal element of $\Omega$ is $(\emptyset ,\leq _{\emptyset})$ .

The maximal elements of $\Omega$ are the well orderings $(X,\leq )$ of $X$ :
First $(X,\leq )\in \Omega$ , assume there is $(X',\leq')\in \Omega$ , such that $(X,\leq )\preceq (X',\leq ' )$ , then we either have $(X,\leq )=(X',\leq ' )$ , thus there’s nothing to prove, or $(X,\leq )$ is an initial segment of $(X',\leq ' )$ , but this requires $X\subsetneq X'\subseteq X$ , a contradiction.

Using Zorn’s lemma to conclude the well-ordering principle:
Let $X$ be a set, and $\Omega$ be defined as given. Since $(\emptyset ,\leq_{\emptyset} )\in \Omega$ and $\emptyset \subseteq X, \Omega$ is not empty. Let $S$ be a totally ordered subset of $\Omega$ , if $S$ is empty we have nothing to prove. Now suppose $S$ is non-empty, then for any $(Y,\leq ),(Y',\leq ' )\in S$ , we have either $(Y,\leq )\preceq (Y',\leq ' )$ or $(Y',\leq ' )\preceq (Y,\leq )$ . Define $U:=\bigcup_{(Y,\leq )\in S}Y$ and for any $a,b\in U$ , we define $a\leq _U b$ if $\exists (Y,\leq )\in S$ such that $a,b\in Y,a\leq b$ .
This order definition is successful, since if we can find two different sets $(Y,\leq ),(Y',\leq ' )\in S$ s.t. $a\leq b$ and $a\leq ' b$ , then one of $(Y',\leq ' )$ and $(Y,\leq )$ is an initial segment of the other, so $a\leq b$ and $a\leq ' b$ are equivalent. Notice that $\leq _U$ is also a total order, since $\forall a,b\in U$ , we can find $(Y,\leq ),(Y',\leq ' )\in S$ s.t. $a\in Y,b\in Y'$ , then either $Y\subseteq Y'$ or $Y'\subseteq Y$ , so $a,b$ must belong to the larger of the two, and thus can be ordered by the well-order of the larger set.
To see $\leq _U$ is a well order on $U$ , choose any non-empty set $V\subseteq U$ , then $\exists (Y,\leq _Y )\in S$ , s.t. $V\cap Y\neq \emptyset$ , using the well-order $\leq _Y$ we can find a minimal element $m$ of $V\cap Y$ , then $m$ is also the minimal element of $V$ , since: if $t\in V,t\leq _U m$ , then $\exists (Y',\leq ' )\in S$ s.t. $t,m\in Y',t\leq ' m$ , so either $(Y',\leq ' )\preceq (Y,\leq _Y )$ , which means $Y'\subseteq Y$ and $t\in Y$ , or $(Y,\leq _Y )\preceq (Y',\leq ' )$ , which means $Y'=Y$ and $t\in Y$ , or $(Y,\leq _Y )$ is an initial segment of $(Y',\leq ' )$ , i.e. there’s $x\in Y'$ s.t. $Y=\{y\in Y':y<' x\}$ , since $m\in Y$ , we have $m<' x$ , so $t<' x$ and $t\in Y$ . Thus in any case we have $t\in Y$ , and so $t\in V\cap Y$ , by the definition of $m$ , we have $m\leq _U t$ and $m$ is the minimal element of $V$ .
Now $U\subseteq X$ means $(U,\leq _U )\in \Omega$ , and if we assume there is some $(Y,\leq )\in S$ such that $(U,\leq _U )\preceq (Y,\leq )$ but $(U,\leq _U )\neq (Y,\leq )$ , then $(U,\leq _U )$ should be an initial segment of $(Y,\leq )$ , thus $U\subsetneq Y$ , contradicting the fact that $Y\subseteq U$ . So we must have $(Y,\leq )\preceq (U,\leq _U )$ for all $(Y,\leq )\in S$ , and then $(U,\leq _U )$ is a maximal element of $S$ . So every totally ordered subset of $\Omega$ has a maximal element.
Now apply Zorn’s lemma to the set $\Omega$ , we see it has a maximum, which should be in the form $(X,\leq )$ by previous conclusion. So $X$ has at least one well-ordering.

Use the well-ordering principle to prove the axiom of choice:
By the well-ordering principle, we can find a well-ordering on $\bigcup_{{\alpha} \in I}X_{\alpha}$ , since every $X_{\alpha}$ is a subset of $\bigcup_{{\alpha} \in I}X_{\alpha}$ and nonempty, we can have a minimum $x_{\alpha}$ for each $X_{\alpha}$ , this proves the axiom of choice.

$\blacksquare$

Exercise 8.5.20. Let $X$ be a set, and let $\Omega\subset 2^X$ be a collection of subsets of $X$ . Assume that $\Omega$ does not contain the empty set $\emptyset$ . Using Zorn’s lemma, show that there is a subcollection $\Omega'\subseteq \Omega$ such that all the elements of $\Omega'$ are disjoint from each other (i.e., $A\cap B=\emptyset$ whenever $A,B$ are distinct elements of $\Omega'$ ), but that all the elements of $\Omega$ intersect at least one element of $\Omega'$ (i.e., for all $C\in \Omega$ there exists $A\in \Omega'$ such that $C\cap A\neq \emptyset$ ). Conversely, if the above claim is true, show that it implies the claim in Exercise 8.4.2, and thus this is yet another claim which is logically equivalent to the axiom of choice.

Solution: Let $S=\{K\subseteq \Omega :(\forall A,B\in K,A\neq B)\implies (A\cap B=\emptyset)\}$ , then $S$ is a set whose elements are subsets of $\Omega$ , we can know $S$ is a partially ordered subset by set inclusion. And $S$ is not empty since if $A\subseteq X,A\neq \emptyset$ , then $\{A\}\in S$ .
Now let $S'$ be a totally ordered subset of $S$ , then $S'$ contains SOME collection of disjoint subsets of $\Omega$ , we denote $M=\{a\subseteq X:a\in K\text{ for some }K\in S' \}$ . $M$ is a collection of subsets of $X$ , we can see $M\subseteq \Omega$ . To prove $M\in S$ , we choose $a,b\in M$ , then $\exists K,K'\in S'$ s.t. $a\in K$ and $b\in K'$ , as $S'$ is totally ordered, we have $(K\subseteq K' )\vee (K'\subseteq K)$ , thus for $a,b$ we have $(a,b\in K)\vee (a,b\in K' )$ , so $a\cap b=\emptyset$ , this means $M\in S$ .
To prove $M$ is an upper bound of $S'$ , we choose any $K\in S'$ , then for $\forall A\in K,A\in M$ by the definition of $M$ , thus $K\subseteq M$ .
Now use Zorn’s lemma, there’s a maximum of $S$ , namely $\Omega '\in S$ , so $\Omega '\subseteq \Omega$ , and all the elements of $\Omega '$ are disjoint from each other. Assume we have some $C\in \Omega$ s.t. $C\cap A=\emptyset ,\forall A\in \Omega '$ , then $\{C\}\cup \Omega '$ would be a set whose elements are disjoint from each other, thus $(\{C\}\cup \Omega ' )\in S$ , contradicting the statement that $\Omega '$ is a maximum of $S$ .
Conversely, if the above claim is true, and we have a set $I$ , with $\{X_{\alpha} :{\alpha} \in I\}$ be disjoint from each other. Let $\Omega =\left\{\{(0,{\alpha} ),(1,x_{\alpha})\}:{\alpha} \in I,x_{\alpha} \in X_{\alpha} \right\}$ , then $\Omega$ doesn’t contain $\emptyset$ . By the above claim we can find a subset $\Omega '\subseteq \Omega$ such that all the elements of $\Omega '$ are disjoint from each other, and all the elements of $\Omega$ intersect at least one element of $\Omega '$ . Thus we first have $\forall A=\{(0,{\alpha} ),(1,x_{\alpha})\},B=\{(0,{\alpha} ' ),(1,x_({\alpha} ' ) )\}\in \Omega '$ , there is ${\alpha} \neq {\alpha} '$ , so $\forall {\alpha} \in I$ , we cannot have more that one $\{(0,{\alpha} ),(1,x_{\alpha} )\}\in \Omega '$ . On the other hand, assume $\exists {\beta}\in I$ , s.t. $\{(0,{\alpha} ),(1,x_{\alpha} )\}\in \Omega '$ means ${\alpha} \neq {\beta}$ , choose $x_{\beta}\in X_{\beta}$ , then $\{(0,{\beta}),(1,x_{\beta} )\}\in \Omega$ , so $\exists \{(0,{\alpha} ),(1,x_{\alpha} )\}\in \Omega '$ , s.t. $\{(0,{\beta}),(1,x_{\beta} )\}\cap \{(0,{\alpha} ),(1,x_{\alpha} )\}\neq \emptyset$ , thus $(1,x_{\alpha} )=(1,x_{\beta} )$ , this contradicts $\{X_{\alpha} :{\alpha} \in I\}$ be disjoint since $x_{\alpha} =x_{\beta}\in X_{\alpha} \cap X_{\beta}$ . This means we can select a $\{(0,{\alpha} ),(1,x_{\alpha} )\}\in \Omega '$ for $\forall {\alpha} \in I$ . Let $Y=\{x_{\alpha} :\{(0,{\alpha} ),(1,x_{\alpha} )\}\in \Omega ' \}$ and we see there’s exactly one $x_{\alpha}$ for each ${\alpha} \in I$ .

$\blacksquare$

Linear Algebra (2ed) Hoffman&Kunze 3.4

2019年9月18日2020年3月16日christangdt留下评论

这一节通过Theorem 11和Theorem 12 将linear transformation和矩阵建立了一对一的关联，此外Theorem 13说明linear transformation的composition与矩阵乘法也有天然的联系。Theorem 14则说明在linear operator的情况下，同一个linear transformation不同basis的矩阵存在相似（similar）的关系，且这个导致相似的矩阵实质上就是一组基在另一组基下的矩阵。

Exercises

1. Let $T$ be the linear operator on $C^2$ defined by $T(x_1,x_2)=(x_1,0)$ . Let $\mathfrak B$ be the stantard ordered basis for $C^2$ and let $\mathfrak B'=\{\alpha_1,\alpha_2\}$ be the ordered basis defined by $\alpha_1=(1,i),\alpha_2=(-i,2)$ .
( a ) What is the matrix of $T$ relative to the pair $\mathfrak B,\mathfrak B'$ ?
( b ) What is the matrix of $T$ relative to the pair $\mathfrak B',\mathfrak B$ ?
( c ) What is the matrix of $T$ in the ordered basis $\mathfrak B'$ ?
( d ) What is the matrix of $T$ in the ordered basis $\{\alpha_2,\alpha_1\}$ ?

Solution:
( a ) $T{\epsilon}_1=2{\alpha}_1-i{\alpha}_2,T{\epsilon}_2=0{\alpha}_1+0{\alpha}_2$ , thus the matrix of $T$ relative to the pair $\mathfrak B,\mathfrak B'$ is $\begin{bmatrix}2&0\\-i&0\end{bmatrix}$ .
( b ) $T{\alpha}_1={\epsilon}_1,T{\alpha}_2=-i{\epsilon}_1$ , thus the matrix of $T$ relative to the pair $\mathfrak B',\mathfrak B$ is $\begin{bmatrix}1&-i\\0&0\end{bmatrix}$ .
( c ) $T{\alpha}_1=2{\alpha}_1-i{\alpha}_2,T{\alpha}_2=-2i{\alpha}_1-{\alpha}_2$ , thus $[T]_{\mathfrak B'}=\begin{bmatrix}2&-2i\\-i&-1\end{bmatrix}$ .
( d ) $T{\alpha}_2=-{\alpha}_2-2i{\alpha}_1,T{\alpha}_1=-i{\alpha}_2+2{\alpha}_1$ , thus $[T]_{\{{\alpha}_2,{\alpha}_1\}}=\begin{bmatrix}-1&-i\\-2i&2\end{bmatrix}$ .

2. Let $T$ be the linear transformation from $R^3$ into $R^2$ defined by

$\displaystyle{T(x_1,x_2,x_3)=(x_1+x_2,2x_3-x_1)}$

( a ) If $\mathfrak B$ is the standard ordered basis for $R^3$ and $\mathfrak B'$ is the standard ordered basis for $R^2$ , what is the matrix of $T$ relative to the pair $\mathfrak B,\mathfrak B'$ ?
( b ) If $\mathfrak B=\{\alpha_1,\alpha_2,\alpha_3\}$ and $\mathfrak B'=\{\beta_1,\beta_2\}$ , where

$\displaystyle{\alpha_1=(1,0,-1),\quad\alpha_2=(1,1,1),\quad\alpha_3=(1,0,0),\quad\beta_1=(0,1),\quad\beta_2=(1,0)}$

what is the matrix of $T$ relative to the pair $\mathfrak B,\mathfrak B'$ ?

Solution:
( a ) We let ${\epsilon}_1,{\epsilon}_2,{\epsilon}_3$ be the standard ordered basis for $R^3$ and ${\epsilon}_1',{\epsilon}_2'$ be the standard ordered basis for $R^2$ , then

$\displaystyle{T{\epsilon}_1=(1,-1),T{\epsilon}_2=(1,0),T{\epsilon}_3=(0,2)}$

thus the matrix of $T$ relative to the pair $\mathfrak B',\mathfrak B$ is

$\displaystyle{A=\begin{bmatrix}1&1&0\\-1&0&2\end{bmatrix}}$

( b ) A direct calculation shows

$\displaystyle{T{\alpha}_1=(1,-3)=-3{\beta}_1+{\beta}_2,\quad T{\alpha}_2=(2,1)={\beta}_1+2{\beta}_2,\quad T{\alpha}_3=(1,-1)=-{\beta}_1+{\beta}_2}$

thus the matrix of $T$ relative to the pair $\mathfrak B',\mathfrak B$ is

$\displaystyle{A=\begin{bmatrix}-3&1&-1\\1&2&1\end{bmatrix}}$

3. Let $T$ be a linear operator on $F^n$ , let $A$ be the matrix of $T$ in the standard ordered basis for $F^n$ , and let $W$ be the subspace of $F^n$ spanned by the column vectors of $A$ . What does $W$ have to do with $T$ ?

Solution: By the condition given, if we write $A=\begin{bmatrix}A_{11}&\cdots&A_{1n}\\\vdots&\ddots&\vdots\\A_{n1}&\cdots&A_{nn}\end{bmatrix}$ , then $T{\epsilon}_j=\sum_{i=1}^nA_{ij} {\epsilon}_i=A_j$ , the $j$ -th column vector of $A$ , thus if $W$ is spanned by $A_1,\dots,A_n$ , it is easy to see $W=\text{range }T$ .

4. Let $V$ be a two-dimensional vector space over the field $F$ , and let $\mathfrak B$ be an ordered basis for $V$ . If $T$ is a linear operator on $V$ and

$\displaystyle{[T]_{\mathfrak B}=\begin{bmatrix}a&b\\c&d\end{bmatrix}}$

prove that $T^2-(a+d)T+(ad-bc)I=0$ .

Solution: We write $\mathfrak B=\{{\alpha}_1,{\alpha}_2\}$ , then for any ${\alpha}\in V$ , we have ${\alpha}=x_1 {\alpha}_1+x_2 {\alpha}_2,x_1,x_2\in F$ , notice that

$\displaystyle{[T{\alpha}_1]_{\mathfrak B}=[T]_{\mathfrak B} [{\alpha}_1]_{\mathfrak B}=\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}a\\c\end{bmatrix},}$
$\displaystyle{[T{\alpha}_2]_{\mathfrak B}=[T]_{\mathfrak B} [{\alpha}_2]_{\mathfrak B}=\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}=\begin{bmatrix}b\\d\end{bmatrix},}$
$\displaystyle{[T^2 {\alpha}_1]_{\mathfrak B}=[T]_{\mathfrak B} [T{\alpha}_1]_{\mathfrak B}=\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}a\\c\end{bmatrix}=\begin{bmatrix}a^2+bc\\ac+cd\end{bmatrix},}$
$\displaystyle{[T^2 {\alpha}_2]_{\mathfrak B}=[T]_{\mathfrak B} [T{\alpha}_2 ]_{\mathfrak B}=\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}b\\d\end{bmatrix}=\begin{bmatrix}ab+bd\\bc+d^2\end{bmatrix}}$

thus

$\displaystyle{\begin{aligned}&\quad(T^2-(a+d)T+(ad-bc)I) {\alpha}_1\\&=T^2 {\alpha}_1-(a+d)T{\alpha}_1+(ad-bc) {\alpha}_1\\&=(a^2+bc) {\alpha}_1+(ac+cd) {\alpha}_2-(a+d)(a{\alpha}_1+c{\alpha}_2 )+(ad-bc) {\alpha}_1\\&=(a^2+bc-a^2-ad+ad-bc) {\alpha}_1+(ac+cd-ac-cd) {\alpha}_2\\&=0\end{aligned}}$
$\displaystyle{\begin{aligned}&\quad (T^2-(a+d)T+(ad-bc)I) {\alpha}_2\\&=T^2 {\alpha}_2-(a+d)T{\alpha}_2+(ad-bc) {\alpha}_2\\&=(ab+bd) {\alpha}_1+(bc+d^2) {\alpha}_2-(a+d)(b{\alpha}_1+d{\alpha}_2 )+(ad-bc) {\alpha}_2\\&=(ab+bd-ab-bd) {\alpha}_1+(bc+d^2-ad-d^2+ad-bc) {\alpha}_2\\&=0\end{aligned}}$

Now we have $(T^2-(a+d)T+(ad-bc)I) {\alpha}_1=(T^2-(a+d)T+(ad-bc)I) {\alpha}_2=0$ , and so

$\displaystyle{\begin{aligned}&\quad (T^2-(a+d)T+(ad-bc)I){\alpha}\\&=(T^2-(a+d)T+(ad-bc)I)(x_1 {\alpha}_1+x_2 {\alpha}_2 )\\&=x_1 (T^2-(a+d)T+(ad-bc)I) {\alpha}_1+x_2 (T^2-(a+d)T+(ad-bc)I) {\alpha}_2\\&=0\end{aligned}}$

5. Let $T$ be the linear operator on $R^3$ , the matrix of which in the standard ordered basis is

$\displaystyle{A=\begin{bmatrix}1&2&1\\0&1&1\\-1&3&4\end{bmatrix}}$

Find a basis for the range of $T$ and a basis for the null space of $T$ .

Solution: Using Exercise 3 we know the range of $T$ is spanned by the column vectors of $A$ , using elementary column operations we have

$\displaystyle{A=\begin{bmatrix}1&2&1\\0&1&1\\-1&3&4\end{bmatrix}\to \begin{bmatrix}1&0&0\\0&1&1\\-1&5&5\end{bmatrix}\to \begin{bmatrix}1&0&0\\0&1&0\\-1&5&0\end{bmatrix}}$

so a basis for the range of $T$ is $(1,0,-1),(0,1,5)$ , notice that $T{\epsilon}_3-T{\epsilon}_1=T{\epsilon}_2-2T{\epsilon}_1$ , thus

$\displaystyle{T({\epsilon}_3+{\epsilon}_1-{\epsilon}_2 )=T(1,-1,1)=0}$

and the dimension of the null space of $T$ is $1$ , so a basis for the null space of $T$ is $(1,-1,1)$ .

6. Let $T$ be the linear operator on $R^2$ defined by

$\displaystyle{T(x_1,x_2)=(-x_2,x_1)}$

( a ) What is the matrix of $T$ in the standard ordered basis for $R^2$ ?
( b ) What is the matrix of $T$ in the ordered basis $\mathfrak B=\{\alpha_1,\alpha_2\}$ , where $\alpha_1=(1,2)$ and $\alpha_2=(1,-1)$ ?
( c ) Prove that for every real number $c$ the operator $(T-cI)$ is invertible.
( d ) Prove that if $\mathfrak B$ is any ordered basis for $R^2$ and $[T]_{\mathfrak B}=A$ , then $A_{12}A_{21}\neq 0$ .

Solution:
( a ) $T{\epsilon}_1=(0,1)={\epsilon}_2,T{\epsilon}_2=(-1,0)=-{\epsilon}_1$ , so the matrix of $T$ in the standard ordered basis for $R^2$ is $\begin{bmatrix}0&-1\\1&0\end{bmatrix}$ .
( b ) We have

$\displaystyle{T{\alpha}_1=(-2,1)=-\frac{1}{3} {\alpha}_1-\frac{5}{3} {\alpha}_2,\quad T{\alpha}_2=(1,1)=\frac{2}{3}{\alpha}_1+\frac{1}{3}{\alpha}_2}$

thus

$\displaystyle{[T]_{\mathfrak B}=\begin{bmatrix}-1/3&2/3\\-5/3&1/3\end{bmatrix}}$

( c ) The matrix of $T-cI$ in the standard ordered basis for $R^2$ is $\begin{bmatrix}-c&-1\\1&-c\end{bmatrix}$ , thus

$\displaystyle{(T-cI) {\epsilon}_1=(-c,1),\quad (T-cI) {\epsilon}_2=(-1,-c)}$

since $(-c,1),(-1,-c)$ are linearly independent for any $c\in R$ , thus a basis of $R^2$ , this means $T-cI$ is invertible.
( d ) Let $\mathfrak B'=\{{\epsilon}_1,{\epsilon}_2\}$ , then $[T]_{\mathfrak B' }=\begin{bmatrix}0&-1\\1&0\end{bmatrix}$ , given any $\mathfrak B$ , we can find an invertible $P$ s.t.

$\displaystyle{[T]_{\mathfrak B}=A=P[T]_{\mathfrak B'} P^{-1}}$

we can assume $P=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ , then $P^{-1}=\dfrac{1}{ad-bc} \begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ , obviously $a,b,c,d$ cannot be all zero.

$\displaystyle{\begin{aligned}A&=\frac{1}{ad-bc}\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}0&-1\\1&0\end{bmatrix}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}\\&=\frac{1}{ad-bc}\begin{bmatrix}b&-a\\d&-c\end{bmatrix}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}\\&=\frac{1}{ad-bc}\begin{bmatrix}bd+ac&-b^2-a^2\\d^2+c^2&-bd-ac\end{bmatrix}\end{aligned}}$

thus $A_{12} A_{21}=-\dfrac{(a^2+b^2 )(c^2+d^2)}{ad-bc}\neq 0$ .

7. Let $T$ be the linear operator on $R^3$ defined by

$\displaystyle{T(x_1,x_2,x_3)=(3x_1+x_3,-2x_1+x_2,-x_1+2x_2+4x_3)}$ .

( a ) What is the matrix of $T$ in the standard ordered basis for $R^3$ ?
( b ) What is the matrix of $T$ in the ordered basis $\{\alpha_1,\alpha_2,\alpha_3\}$ , where $\alpha_1=(1,0,1),\alpha_2=(-1,2,1),\alpha_3=(2,1,1)$ ?
( c ) Prove that $T$ is invertible and give a rule for $T^{-1}$ like the one which defines $T$ .

Solution:
( a ) The matrix of $T$ in the standard ordered basis for $R^3$ is $\begin{bmatrix}3&0&1\\-2&1&0\\-1&2&4\end{bmatrix}$ .
(b) We form $P$ where $P_j=[{\alpha}_j]_{\{{\epsilon}_1,{\epsilon}_2,{\epsilon}_3\}}$ , it’s easy to see $P=\begin{bmatrix}1&-1&2\\0&2&1\\1&1&1\end{bmatrix}$ , and we perform

$\displaystyle{\begin{aligned}\begin{bmatrix}1&-1&2&1&0&0\\0&2&1&0&1&0\\1&1&1&0&0&1\end{bmatrix}&\to \begin{bmatrix}1&-1&2&1&0&0\\0&2&1&0&1&0\\0&2&-1&-1&0&1\end{bmatrix}\\&\to \begin{bmatrix}1&-1&2&1&0&0\\0&2&1&0&1&0\\0&0&-2&-1&-1&1\end{bmatrix}\\&\to \begin{bmatrix}1&-1&0&0&-1&1\\0&2&0&-1/2&1/2&1/2\\0&0&1&1/2&1/2&-1/2\end{bmatrix}\\&\to \begin{bmatrix}1&0&0&-1/4&-3/4&5/4\\0&1&0&-1/4&1/4&1/4\\0&0&1&1/2&1/2&-1/2\end{bmatrix}\end{aligned}}$

thus

$\displaystyle{P^{-1}=1/4 \begin{bmatrix}-1&-3&5\\-1&1&1\\2&2&-2\end{bmatrix}}$

and then

$\begin{aligned} {[T]_{\{{\alpha}_1,{\alpha}_2,{\alpha}_3\}}} &=P^{-1} [T]_{\{{\epsilon}_1,{\epsilon}_2,{\epsilon}_3\}} P\\&=\frac{1}{4} \begin{bmatrix}-1&-3&5\\-1&1&1\\2&2&-2\end{bmatrix}\begin{bmatrix}3&0&1\\-2&1&0\\-1&2&4\end{bmatrix}\begin{bmatrix}1&-1&2\\0&2&1\\1&1&1\end{bmatrix}\\&=\frac{1}{4} \begin{bmatrix}-2&7&19\\-6&3&3\\4&-2&-6\end{bmatrix}\begin{bmatrix}1&-1&2\\0&2&1\\1&1&1\end{bmatrix}\\&=\frac{1}{4}\begin{bmatrix}17&35&22\\-3&15&-6\\-2&-14&0\end{bmatrix}\end{aligned}$

( c ) It is enough to prove $[T]_{\{{\epsilon}_1,{\epsilon}_2,{\epsilon}_3\}}$ is invertible, this is true since

$\displaystyle{\begin{bmatrix}3&0&1\\-2&1&0\\-1&2&4\end{bmatrix}^{-1}=\begin{bmatrix}4/9&2/9&-1/9\\8/9&13/9&-2/9\\-1/3&-2/3&1/3\end{bmatrix}}$

since we know $[T^{-1}]_{\{{\epsilon}_1,{\epsilon}_2,{\epsilon}_3\}}=([T]_{\{{\epsilon}_1,{\epsilon}_2,{\epsilon}_3\}})^{-1}$ , it is able to describe

$\displaystyle{T^{-1} (x_1,x_2,x_3 )=\left(\frac{4}{9} x_1+\frac{2}{9} x_2-\frac{1}{9} x_3,\frac{8}{9} x_1+\frac{13}{9} x_2-\frac{2}{9} x_3,-\frac{1}{3} x_1-\frac{2}{3} x_2+\frac{1}{3} x_3\right)}$

8. Let $\theta$ be a real number. Prove that the following two matrices are similar over the field of complex numbers:

$\displaystyle{\begin{bmatrix}\cos{\theta}&\sin{\theta}\\\sin{\theta}&\cos{\theta}\end{bmatrix},\quad \begin{bmatrix}e^{i{\theta}}&0\\0&e^{-i\theta}\end{bmatrix}}$

Solution: Let $T$ be the linear operator on $C^2$ which is represented by the first matrix in the standard ordered basis, then $T(1,0)=(\cos {\theta},\sin {\theta}), T(0,1)=(-\sin {\theta},\cos {\theta})$ , let ${\alpha}_1=(i,1),{\alpha}_2=(1,i)$ , then

$\begin{aligned}T{\alpha}_1&=i(\cos {\theta},\sin {\theta} )+(-\sin {\theta},\cos {\theta})\\&=(i \cos {\theta}-\sin {\theta},i \sin {\theta}+\cos {\theta})\\&=e^{i{\theta}} (i,1)=e^{i{\theta}} {\alpha}_1\end{aligned}$

and similarly we can see $T{\alpha}_2=e^{-i{\theta}} {\alpha}_2$ , it is easy to see $\{{\alpha}_1,{\alpha}_2 \}$ are linearly independent, thus a basis of $C^2$ , since $[T]_{\{{\alpha}_1,{\alpha}_2\}} =\begin{bmatrix}e^{i{\theta}}&0\\0&e^{-i{\theta}} \end{bmatrix}$ , the two matrices are similar, with $P=\begin{bmatrix}i&1\\1&i\end{bmatrix}$ and

$\displaystyle{[T]_{\{{\alpha}_1,{\alpha}_2\}} =P^{-1} \begin{bmatrix}\cos {\theta}&-\sin {\theta}\\\sin {\theta}&\cos {\theta} \end{bmatrix}P}$

9. Let $V$ be a finite-dimensional vector space over the field $F$ and let $S$ and $T$ be linear operators on $V$ . We ask: When do there exist ordered bases $\mathfrak B$ and $\mathfrak B'$ for $V$ such that $[S]_{\mathfrak B}=[T]_{\mathfrak B'}$ ? Prove that such bases exist if and only if there is an invertible linear operator $U$ on $V$ such that $T=USU^{-1}$ .

Solution: If $[S]_{\mathfrak B}=[T]_{\mathfrak B'}$ , then let $U$ be the linear operator that carries ${\mathfrak B}$ onto ${\mathfrak B'}$ , i.e., if we let

$\displaystyle{{\mathfrak B}=\{a_1,\dots,a_n \},\quad {\mathfrak B'}=\{b_1,\dots,b_n \}}$

and define $U$ by $Ua_i=b_i, i=1,\dots,n$ . Then $U$ is invertible since it carries a basis onto another basis, and $U^{-1} b_i=a_i,i=1,\dots,n$ . If we denote $[S]_{\mathfrak B}=[T]_{\mathfrak B'}=A=(A_{ij})$ , then by definition we have $Sa_j=\sum_{i=1}^nA_{ij} a_i ,Tb_j=\sum_{i=1}^nA_{ij} b_i$ , so

$\displaystyle{USU^{-1}(b_j )=USa_j=U\left(\sum_{i=1}^nA_{ij} a_i \right)=\sum_{i=1}^nA_{ij} Ua_i=\sum_{i=1}^nA_{ij}b_i=Tb_j,\quad j=1,\dots,n}$

Since $USU^{-1}$ and $T$ are equal on a basis of $V$ , we have $T=USU^{-1}$ .
Conversely, if $T=USU^{-1}$ for some invertible $U$ , we let $B=\{a_1,\dots,a_n \}$ be an ordered basis for $V$ , and $\mathfrak B'=\{Ua_1,\dots,Ua_n \}$ , since $U$ is invertible, $\mathfrak B'$ is a basis for $V$ . Notice that if ${\alpha}\in V$ , then

$\displaystyle{{\alpha}=k_1 a_1+\dots+k_n a_n,\quad k_1,\dots,k_n\in F}$

thus $[{\alpha}]_{\mathfrak B}=\begin{bmatrix}k_1\\ \vdots\\k_n\end{bmatrix}$ , and $U{\alpha}=k_1 Ua_1+\dots+k_n Ua_n$ , so $[U{\alpha}]_{\mathfrak B'}=\begin{bmatrix}k_1\\\vdots\\k_n\end{bmatrix}$ , so we have $[{\alpha}]_{\mathfrak B}=[U{\alpha}]_{\mathfrak B'}$ , from this and the fact that $TU=US$ we can have

$\displaystyle{[S]_{\mathfrak B} [{\alpha}]_{\mathfrak B}=[S{\alpha}]_{\mathfrak B}=[US{\alpha}]_{\mathfrak B'}=[TU{\alpha}]_{\mathfrak B'}=[T]_{\mathfrak B'} [U{\alpha}]_{\mathfrak B'}=[T]_{\mathfrak B'} [{\alpha}]_{\mathfrak B}}$

and it must follow that $[S]_{\mathfrak B}=[T]_{\mathfrak B'}$ .
Alternatively, one easier proof is using Theorem 14 and the consequence of Theorem 13, since in this case we have

$\displaystyle{[T]_{\mathfrak B'}=[U^{-1}]_{\mathfrak B} [T]_{\mathfrak B} [U]_{\mathfrak B}=[U^{-1} TU]_{\mathfrak B}=[U^{-1}(USU^{-1})U]_{\mathfrak B}=[S]_{\mathfrak B}}$

10.We have seen that the linear operator $T$ on $R^2$ defined by $T(x_1,x_2)=(x_1,0)$ is represented in the standard ordered basis by the matrix

$\displaystyle{A=\begin{bmatrix}1&0\\0&0\end{bmatrix}.}$

This operator satisfies $T^2=T$ . Prove that if $S$ is a linear operator on $R^2$ such that $S^2=S$ , then $S=0$ ,or $S=I$ , or there is an ordered basis $\mathfrak B$ for $R^2$ such that $[S]_{\mathfrak B}=A$ (above).

Solution: If $S=0$ or $S=I$ , we obviously have $S^2=S$ , now suppose $S\neq 0,S\neq I$ , but $S^2=S$ , then it is able to find ${\alpha},{\beta}\in R^2$ , s.t. $S{\alpha}\neq 0,S{\beta}\neq {\beta}$ , since $S{\alpha}\in \text{range }S$ , we have $\dim \text{range }S\geq 1$ , also since $S(S{\beta}-{\beta})=S^2 {\beta}-S{\beta}=S{\beta}-S{\beta}=0$ , we know $S{\beta}-{\beta}\in \text{null }S$ , and $\dim \text{null }S\geq 1$ , as we discuss in $R^2$ , $\dim \text{range }S+\dim \text{null }S=2$ , thus $\dim \text{range }S=\dim \text{null }S=1$ . Now if we let $a=S{\alpha},b=S{\beta}-{\beta}$ , and ${\mathfrak B}=\{a,b\}$ , then ${\mathfrak B}$ is an ordered basis for $R^2$ and $[S]_{\mathfrak B}=A$ .

11. Let $W$ be the space of all $n\times 1$ column matrices over a field $F$ . If $A$ is an $n\times n$ matrix over $F$ , then $A$ defines a linear operator $L_A$ on $W$ through left multiplicaition: $L_A(X)=AX$ . Prove that every linear operator on $W$ is left multiplication by some $n\times n$ matrix, i.e., is $L_A$ for some $A$ .
Now suppose $V$ is an $n$ -dimensional vector space over the field $F$ , and let $\mathfrak B$ be an ordered basis for $V$ . For each $\alpha$ in $V$ , define $U\alpha =[\alpha]_{\mathfrak B}$ . Prove that $U$ is an isomorphism of $V$ onto $W$ . If $T$ is a linear operator on $V$ , then $UTU^{-1}$ is a linear operator on $W$ . Accordingly, $UTU^{-1}$ is left multiplication by some $n\times n$ matrix $A$ . What is $A$ ?

Solution: If $T$ is a linear operator on $W$ , let $\mathfrak B'=\{{\epsilon}_1,\dots,{\epsilon}_n \}$ be the standard basis on $W$ , for each $X=\begin{bmatrix}x_1\\\vdots\\x_n \end{bmatrix}$ , we have $X=\sum_{j=1}^nx_j {\epsilon}_j$ , and if we define $A:=[T]_{\mathfrak B'}$ , then $T(X)=T(\sum_{j=1}^nx_j {\epsilon}_j )=\sum_{j=1}^nx_j T{\epsilon}_j =\sum_{j=1}^nx_j \sum_{i=1}^nA_{ij} {\epsilon}_i =\sum_{i=1}^n(\sum_{j=1}^nA_{ij} x_j ){\epsilon}_i =AX$ , thus $T=L_A$ .
For the second question, let $\mathfrak B=\{a_1,\dots,a_n \}$ , if $[{\alpha}]_{\mathfrak B}=[{\beta}]_{\mathfrak B}=\begin{bmatrix}x_1\\\vdots \\x_n\end{bmatrix}$ , then ${\alpha}={\beta}=\sum_{j=1}^nx_j a_j$ , this shows $(U{\alpha}=U{\beta})\implies ({\alpha}={\beta})$ , so $U$ is injective. Also for any $X=\begin{bmatrix}x_1\\\vdots\\x_n \end{bmatrix}\in W$ , define ${\alpha}=\sum_{j=1}^nx_j a_j$ , then $U{\alpha}=X$ , thus $U$ is surjective, combined we show $U$ is an isomorphism.
If $T$ is a linear operator on $V$ , then let $X=\begin{bmatrix}x_1\\\vdots\\x_n\end{bmatrix},Y=\begin{bmatrix}y_1\\\vdots\\y_n \end{bmatrix}\in W$ , by definition we have

$\displaystyle{\begin{aligned}UTU^{-1} (cX+Y)&=UT(U^{-1} (cX+Y))\\&=UT\left(\sum_{j=1}^n(cx_j+y_j)a_j \right)=U\left(T\Big(\sum_{j=1}^n(cx_j+y_j)a_j \Big)\right)\\&=U\left(\sum_{j=1}^n(cx_j+y_j)Ta_j \right)=\sum_{j=1}^n(cx_j+y_j)UTa_j \\&=c\sum_{j=1}^nx_j UTa_j +\sum_{j=1}^ny_j UTa_j =c\left(UT\sum_{j=1}^nx_j a_j \right)+UT\left(\sum_{j=1}^ny_j a_j \right)\\&=c(UT(U^{-1}(X)))+(UT(U^{-1}(Y)))=c(UTU^{-1})(X)+(UTU^{-1})(Y)\end{aligned}}$

thus $UTU^{-1}$ is a linear operator on $W$ .
If $T$ is a linear operator on $V$ , then let $C=[T]_{\mathfrak B}$ , i.e. $Ta_j=\sum_{j=1}^nC_{ij} a_i$ , in the first part we proved $A=[UTU^{-1}]_{\mathfrak B'}$ , to compute $A$ , we see that $UTU^{-1}({\epsilon}_j )=UTa_j=U(\sum_{j=1}^nC_{ij}a_i)=\sum_{j=1}^nC_{ij}Ua_i =\sum_{j=1}^nC_{ij}{\epsilon}_j$ , thus $[UTU^{-1}]_{\mathfrak B'}=C=[T]_{\mathfrak B}$ , or $A=[T]_{\mathfrak B}$ .

12. Let $V$ be an $n$ -dimensional vector space over the field $F$ , and let $\mathfrak B=\{\alpha_1,\dots,\alpha_n\}$ be an ordered basis for $V$ .
( a ) According th Theorem 1, there is a unique linear operator $T$ on $V$ such that

$\displaystyle{T{\alpha}_j={\alpha}_{j+1},\qquad j=1,\dots,n-1,\qquad T{\alpha}_n=0.}$

What is the matrix $A$ of $T$ in the ordered basis $\mathfrak B$ ?
( b ) Prove that $T^n=0$ but $T^{n-1}\neq 0$ .
( c ) Let $S$ be any linear operator on $V$ such that $S^n=0$ but $S^{n-1}\neq 0$ . Prove that there is an ordered basis $\mathfrak B'$ for $V$ such that the matrix of $S$ in the ordered basis $\mathfrak B'$ is the matrix $A$ of part (a).
( d ) Prove that if $M$ and $N$ are $n\times n$ matrices over $F$ such that $M^n=N^n=0$ but $M^{n-1}\neq 0\neq N^{n-1}$ , then $M$ and $N$ are similar.

Solution:
( a ) A direct computation shows $A=\begin{bmatrix}0&0&\dots&0\\1&0& & \\ &\ddots&\ddots& \\0& &1&0\end{bmatrix}$ .
( b ) We have $T^k {\alpha}_{n+1-k}=0,k=1,\dots,n$ , thus $T^n=0$ , but $T^{n-1}{\alpha}_1={\alpha}_n\neq 0$ .
( c ) It is able to choose ${\alpha}$ s.t. $S^{n-1}{\alpha}\neq 0$ but $S^n {\alpha}=0$ , notice ${\alpha}\neq 0$ , and $\{{\alpha},S{\alpha},\dots,S^{n-1}{\alpha}\}$ is linearly independent, for if we have

$\displaystyle{k_1 {\alpha}+k_2 S{\alpha}+\dots+k_n S^{n-1} {\alpha}=0}$

then $S^{n-1}(k_1 {\alpha}+k_2 S{\alpha}+\dots+k_n S^{n-1}{\alpha})=k_1 S^{n-1}{\alpha}=0$ , thus $k_1=0$ , the above becomes

$\displaystyle{k_2 S{\alpha}+\dots+k_n S^{n-1}{\alpha}=0}$

then $S^{n-2}(k_2 S{\alpha}+\dots+k_n S^{n-1}{\alpha})=k_2 S^{n-1}{\alpha}=0$ , thus $k_2=0$ , continue this step we eventually have $k_1=\dots=k_n=0$ . Thus we can define $\mathfrak B'=\{{\alpha},S{\alpha},\dots,S^{n-1} {\alpha}\}$ , and $[S]_{\mathfrak B'}=A$ .
( d ) Let $T$ and $S$ be linear operators which satisfies $[T]_{\mathfrak B}=M,[S]_{\mathfrak B}=N$ , in which ${\mathfrak B}=\{{\epsilon}_1,\dots,{\epsilon}_n \}$ . From ( c ) we can find two ordered basis ${\mathfrak B}_1$ and ${\mathfrak B}_2$ s.t. $[T]_{\mathfrak B_1}=[S]_{\mathfrak B_2}=A$ , by Theorem 14, let $P$ be the $n\times n$ matrix with columns $P_j=[{\epsilon}_j ]_{\mathfrak B_1}$ , and $Q$ be the $n\times n$ matrix with columns $Q_j=[{\epsilon}_j ]_{\mathfrak B_2}$ , then

$\displaystyle{M=[T]_{\mathfrak B}=P^{-1} AP,\quad N=[S]_{\mathfrak B}=Q^{-1}AQ}$

thus $M=P^{-1} QAQ^{-1}P=(Q^{-1}P)^{-1}A(Q^{-1}P)$ .

13. Let $V$ and $W$ be finite-dimensional vector spaces over the field $F$ and let $T$ be a linear transformation from $V$ into $W$ . If

$\displaystyle{\mathfrak B=\{\alpha_1,\dots,\alpha_n\}\text{ and }\mathfrak B'=\{\beta_1,\dots,\beta_m\}}$

are ordered base for $V$ and $W$ , respectively, define the linear transformations $E{p,q}$ as in the proof of Theorem 5: $E^{p,q}(\alpha_i)=\delta_{iq}\beta_p$ . Then the $E{p,q},1\leq p\leq m,1\leq q\leq n$ , form a basis for $L(V,W)$ , and so

$\displaystyle{T=\sum_{p=1}^m\sum_{q=1}^nA_{pq}E^{p,q}}$

for certain scalars $A_{pq}$ (the coordinates of $T$ in this basis for $L(V,W)$ ). Show that the matrix $A$ with entries $A(p,q)=A_{pq}$ is precisely the matrix of $T$ relative to the pair $\mathfrak B,\mathfrak B'$ .

Solution:

$\begin{aligned}T{\alpha}_j&=(\sum_{p=1}^m\sum_{q=1}^nA_{pq} E^{p,q})({\alpha}_j )=\sum_{p=1}^m\sum_{q=1}^nA_{pq} E^{p,q}({\alpha}_j)\\&=\sum_{p=1}^m\sum_{q=1}^nA_{pq}{\delta}_{jq} {\beta}_p=\sum_{p=1}^mA_{pj} {\beta}_p\end{aligned}$ ,

and the conclusion follows.

Linear Algebra (2ed) Hoffman&Kunze 3.3

2019年9月17日2020年3月15日christangdt留下评论

这一节把isomorphism单独阐述，即既是一对一又是onto的，也就是一个bijection。其本质可以用文中的一句话概括：isomorphism is an equivalence relation on the class of vector spaces。Theorem 10说明了所有n维vector space都和 $F^n$ 是isomorphic的，实际上，isomorphism是“dimension preserving”。

Exercises

1. Let $V$ be the set of complex numbers and let $F$ be the field of real numbers. With the usual operations, $V$ is a vector space over $F$ . Describe explicitly an isomorphism of this space onto $R^2$ .

Solution: For any $c=a+bi\in V$ , define $U(c)=(a,b)$ , then $U$ is an isomorphism of $V$ onto $R^2$ .

2.Let $V$ be a vector space over the field of complex numbers, and suppose there is an isomorphism $T$ of $V$ onto $C^3$ . Let $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ be vectors in $V$ such that

$T\alpha_1=(1,0,i),\qquad T\alpha_2=(-2,1+i,0),\\ T\alpha_3=(-1,1,1),\qquad T\alpha_4=(\sqrt2,i,3).$

( a ) Is $\alpha_1$ in the subspace spanned by $\alpha_2$ and $\alpha_3$ ?
( b ) Let $W_1$ be the subspace spanned by $\alpha_1$ and $\alpha_2$ , and let $W_2$ be the subspace spanned by $\alpha_3$ and $\alpha_4$ . What is the intersection of $W_1$ and $W_2$ ?
( c ) Find a basis for the subspace of $V$ spanned by the four vectors $\alpha_j$ .

Solution:
( a ) It is easy to see $T{\alpha}_2,T{\alpha}_3$ are linearly independent, thus ${\alpha}_2,{\alpha}_3$ are linearly independent, since

$\displaystyle{\begin{bmatrix}1&0&i\\-2&1+i&0\\-1&1&1\end{bmatrix}\to \begin{bmatrix}1&0&i\\0&1+i&2i\\0&1&1+i\end{bmatrix}\to \begin{bmatrix}1&0&i\\0&1&1+i\\0&0&0\end{bmatrix}}$

$T{\alpha}_1,T{\alpha}_2,T{\alpha}_3$ are linearly dependent, thus ${\alpha}_1$ is in the subspace spanned by ${\alpha}_2,{\alpha}_3$ .
( b ) From ( a ) we have $(1+i)(T{\alpha}_2+2T{\alpha}_1 )=T{\alpha}_3+T{\alpha}_1$ , thus we have

$\displaystyle{(1+i)({\alpha}_2+2{\alpha}_1 )={\alpha}_3+{\alpha}_1}$

Since $T{\alpha}_4$ is not in the span of $T{\alpha}_1,T{\alpha}_2$ , we have $W_1\cap W_2=\{k{\alpha}_3:k\in C\}$ .
( c ) One basis can be $({\alpha}_1,{\alpha}_2,{\alpha}_4)$ .

3.Let $W$ be the set of all $2\times 2$ complex Hermitian matrices, that is, the set of $2\times 2$ complex matrices $A$ such that $A_{ij}=\overline{A_{ji}}$ (the bar denoting complex conjugation). As we pointed out in Example 6 of Chapter 2, $W$ is a vector space over the field of real numbers, under the usual operations. Verify that

$\displaystyle{(x,y,z,t)\to\begin{bmatrix}t+x&y+iz\\y-iz&t-x \end{bmatrix}}$

is an isomorphism of $R^4$ onto $W$ .

Solution: Denote $T(x,y,z,t)=\begin{bmatrix}t+x&y+iz\\y-iz&t-x\end{bmatrix}$ , if $U(x,y,z,t)=0=\begin{bmatrix}0&0\\0&0\end{bmatrix}$ , then it is easy to see $t+x=t-x=0$ , thus $t=x=0$ , and $y+iz=0$ means $z=0$ and $y=0$ . So $T$ is one-one. Next let any $A\in W$ , then $A=\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}$ , since $\overline{a_{11}}=a_{11}$ we know $a_{11}\in R$ , also $a_{22}\in R$ , then we let

$\displaystyle{t=\frac{a_{11}+a_{22}}{2},\quad x=\frac{a_{11}-a_{22}}{2},\quad y=\Re(a_{12}),\quad z=\Im(a_{12})}$

it is easy to see $T(x,y,z,t)=A$ .

4. Show that $F^{m\times n}$ is isomorphic to $F^{mn}$ .

Solution: For any $A=\begin{bmatrix}a_{11}&\cdots&a_{1n}\\ \vdots&\ddots&\vdots\\a_{m1}&\cdots&a_{mn}\end{bmatrix}\in F^{m\times n}$ , we define $T(A)=(a_{11},\dots,a_{1n},\dots,a_{m1},\dots,a_{mn})$ , i.e., $T(A)$ is a sequence of ordered list of the row vectors of $A$ . $T$ is an isomorphism from $F^{m\times n}$ to $F^{mn}$ .

5. Let $V$ be the set of complex numbers regarded as a vector space over the field of real numbers (Exercise 1). We define a function $T$ from $V$ into the space of $2\times 2$ real matrices, as follows. If $z=x+iy$ with $x$ and $y$ real numbers, then

$\displaystyle{T(z)=\begin{bmatrix}x+7y&5y\\-10y&x-7y \end{bmatrix}.}$

( a ) Verify that $T$ is a one-one (real) linear transformation of $V$ into the space of $2\times 2$ real matrices.
( b ) Verify that $T(z_1z_2)=T(z_1)T(z_2)$ .
( c ) How would you describe the range of $T$ ?

Solution:
( a ) It is enough to show $T(z)=0$ means $z=0$ , it is easy to see

$\displaystyle{\begin{bmatrix}x+7y&5y\\-10y&x-7y\end{bmatrix}=\begin{bmatrix}0&0\\0&0\end{bmatrix} \implies x=0,y=0}$

( b ) Let $z_1=a+bi,z_2=c+di$ , then $z_1 z_2=(ac-bd)+(ad+bc)i$ , so

$\displaystyle{T(z_1 z_2 )=\begin{bmatrix}ac-bd+7(ad+bc)&5(ad+bc)\\-10(ad+bc)&ac-bd-7(ad+bc)\end{bmatrix}}$
$\displaystyle{\begin{aligned}T(z_1)T(z_2)&=\begin{bmatrix}a+7b&5b\\-10b&a-7b\end{bmatrix}\begin{bmatrix}c+7d&5d\\-10d&c-7d\end{bmatrix} \\&=\begin{bmatrix}(a+7b)(c+7d)-50bd&5d(a+7b)+5b(c-7d)\\-10b(c+7d)-10d(a-7b)&(a-7b)(c-7d)-50bd\end{bmatrix} \\&=T(z_1 z_2)\end{aligned}}$

( c ) The range of $T$ is the subspace of $2\times 2$ matrices $A$ such that $A_{21}=-2A_{12}$ .

6. Let $V$ and $W$ be finite-dimensional vector spaces over the field $F$ . Prove that $V$ and $W$ are isomorphic if and only if $\dim V=\dim W$ .

Solution: If $V$ and $W$ are isomorphic, then let $T$ be an isomorphism from $V$ to $W$ , and $\{a_1,\dots,a_n \}$ be a basis of $V$ , so $\dim V=n$ , consider $\{Ta_1,\dots,Ta_n \}$ , for any $w\in W,w=Tv,v\in V$ , then we can find scalars $x_1,\dots,x_n$ such that $v=\sum_{i=1}^nx_i a_i$ , so $w=T(\sum_{i=1}^nx_i a_i)=\sum_{i=1}^nx_i Ta_i$ , so $\{Ta_1,\dots,Ta_n \}$ spans $W$ . If $\sum_{i=1}^nx_i Ta_i=0$ , then $T(\sum_{i=1}^nx_i a_i)=0$ since $T$ is non-singular, then

$\displaystyle{x_i=0,\quad i=1,\dots,n}$

which means $\{Ta_1,\dots,Ta_n \}$ is linearly independent, we can conclude $\{Ta_1,\dots,Ta_n \}$ is a basis of $W$ , and then $\dim W=n=\dim V$ .
Conversely, if $\dim V=\dim W:=n$ , then $V$ and $W$ are isomorphic to $F^n$ , by Theorem 10, let $T:V\to F^n$ and $U:W\to F^n$ be two isomorphism, then $U^{-1} T:V\to W$ is an isomorphism.

7. Let $V$ and $W$ be vector spaces over the field $F$ and let $U$ be an isomorphism of $V$ onto $W$ . Prove that $T\to UTU^{-1}$ is an isomorphism of $L(V,V)$ onto $L(W,W)$ .

Solution: Denote $M(T)=UTU^{-1}$ , if $M(T)=0$ , then $UTU^{-1}(w)=0$ for all $w\in W$ , since $U$ is non-singular, we have $TU^{-1}(w)=0$ for all $w\in W$ , given any $v\in V$ , we can have some $w\in W$ s.t. $U^{-1}(w)=v$ , so $Tv=0$ for all $v\in V$ , thus $T$ is the zero transformation.
For any $M'\in L(W,W)$ , if we choose a basis $w_1,\dots ,w_n$ of $W$ , then $M'$ can be written as

$\displaystyle{M'(w_i)=a_{i1} w_1+\cdots +a_{in} w_n,\quad i=1,\dots ,n}$

Notice that $U^{-1} (w_1),\dots ,U^{-1}(w_n)$ is a basis for $V$ , so if we define

$\displaystyle{T(U^{-1}(w_i))=a_{i1} U^{-1}(w_1)+\cdots+a_{in}U^{-1}(w_n),\quad i=1,\dots ,n}$

then $T\in L(V,V)$ , and we have

$\displaystyle{UTU^{-1}(w_i )=U(a_{i1}U^{-1}(w_1)+\cdots+a_{in}U^{-1}(w_n))=a_{i1} w_1+\cdots+a_{in}w_n,\quad i=1,\dots ,n}$

this means $M(T)=UTU^{-1}=M'$ , thus $M(T)$ is onto and the proof is complete.

	匿名发表在《陶哲轩实分析（下）7.2及习题-Analysis II 7.…》
	swimming5cc5e307af发表在《陶哲轩实分析11.2及习题-Analysis I 11.2》
	匿名发表在《陶哲轩实分析3.4及习题-Analysis I 3.4》
	匿名发表在《陶哲轩实分析9.9及习题-Analysis I 9.9》
	匿名发表在《陶哲轩实分析（下）1.2及习题-Analysis II 1.…》