# Department of Mathematics, University of California, Berkeley
Fall Semester 2013
1. Please write your 1- or 2-digit student exam number on this cover sheet and on all problem sheets (even problems that you do not wish to be graded).
2. Indicate below which six problems you wish to have graded. Cross out solutions you may have begun for the problems that you have not selected.
3. Extra sheets should be stapled to the appropriate problem at the upper right corner. Do not put work for problem p on either side of the page for problem q if $p \neq q .$
4. No notes, books, or calculators may be used during the exam.
## PROBLEM SELECTION
Part A: List the six problems you have chosen:
## GRADE COMPUTATION
1A.
1B.
2A.
Calculus
2B.
Real analysis
3A.
3B.
Real analysis
4A.
4B.
Complex analysis
5A.
5B.
Complex analysis
6A.
6B.
Linear algebra
7A.
7B.
Linear algebra
8A.
8B.
Abstract algebra
9A.
9B.
Abstract algebra
Part A Subtotal:
Part B Subtotal:
Grand Total:
The set of pairs of positive real numbers $( x , y )$ with $x ^ { y } = y ^ { x }$ is a union of two smooth curves.
Find the point where they intersect.
## Solution:
The set is the set of points with $x ^ { 1 / x } = y ^ { 1 / y }$ The graph of the function $f ( x ) = x ^ { 1 / x }$ rises from (0, 0) to a maximum at $( e , e ^ { 1 / e } )$ and then decreases to $( \infty , 1 )$ . So the points with $x ^ { y } = y ^ { x }$ consists of the line $y = x$ together with the pairs of distinct points having the same value of $f ( x )$ , and these curves meet whenever f has a maximum or minumum value, so the intersection point is (e, e).
Please cross out this problem if you do not wish it graded
Suppose that x is a smooth real-valued function of the real number t, satisfying $d x / d t \leq$ $b ( t ) x ( t )$ for some continuous function b. Prove that if $s \leq t$ then $\begin{array} { r } { x ( t ) \leq x ( s ) \exp { \int _ { s } ^ { t } b ( t ) d t } . } \end{array}$
Solution: Put $\begin{array} { r } { y ( t ) = x ( t ) \exp ( - \int _ { s } ^ { t } b ( t ) d t ) } \end{array}$ . Then the condition ${ d x } / { d t } \le b ( t ) x ( t )$ implies that ${ d y } / { d t } \le 0 , \mathrm { s o } y ( t ) \le y ( s )$ , which is equivalent to the result.
Define a set of positive real numbers as follows. Let $x _ { 0 } > 0$ be any positive number, and let $x _ { n + 1 } = ( 1 + x _ { n } ) ^ { - 1 }$ for all $n \geq 0$ . Prove that this sequence converges, and find its limit.
## Solution:
since . Fi $x _ { 0 } > 0 , 1 + x _ { 0 } > 1$ the, so $0 < x _ { 1 } < 1$ . Similarly,y induction $1 < 1 + x _ { 1 } < 2$ , so $\textstyle { \frac { 1 } { 2 } } \ < \ x _ { 2 } \ < \ 1$ $\begin{array} { r } { \frac { 3 } { 2 } < 1 + x _ { 2 } < 2 } \end{array}$ $\begin{array} { l } { \frac { 1 } { 2 } < x _ { 3 } < \frac { 2 } { 3 } } \end{array}$ $\begin{array} { r } { \frac { 1 } { 2 } < x _ { n } < \frac { 2 } { 3 } } \end{array}$ for all $n \geq 3$
Let $f ( \stackrel { \sim } { x } ) = 1 / ( 1 + x )$ . Solving for $f ( x ) = x$ leads to an equation $x ^ { 2 } + x - 1 = 0$ , so $\alpha : = ( \sqrt { 5 } - 1 ) / 2$ is the unique positive real number for which $f ( \alpha ) = \alpha$
We have $f ^ { \prime } ( x ) = - 1 / ( 1 + x ) ^ { 2 }$ 2 , so
$$
| f ^ { \prime } ( x ) | < { \frac { 4 } { 9 } } \qquad \mathrm { f o r ~ a l l ~ { \frac { 1 } { 2 } } < } x < { \frac { 2 } { 3 } } .
$$
Since α lies in the given range (apply the first paragraph with $x _ { 0 } = \alpha )$ , we have by the Mean Value Theorem that
$$
| x _ { n + 1 } - \alpha | = | f ( x _ { n } ) - f ( \alpha ) | < { \frac { 4 } { 9 } } | x _ { n } - \alpha |
$$
for all $n \geq 3$ , so the sequence $\{ x _ { n } \}$ converges to $\textstyle \alpha = { \frac { { \sqrt { 5 } } - 1 } { 2 } }$ as $n \to \infty$
Show that the polynomial $p ( z ) = z ^ { 5 } - 6 z + 3$ has five distinct complex roots, and that exactly three (and not five) are real.
## Solution:
We know that $p$ has five roots, when counted with multiplicity, so it suffices for the first part to show that $p$ has no multiple roots. Any multiple root of $p$ must be a common root of $p$ and $p ^ { \prime } .$ , hence it must be a root of
$$
5 p ( z ) - z p ^ { \prime } ( z ) = ( 5 z ^ { 5 } - 3 0 z + 1 5 ) - ( 5 z ^ { 5 } - 6 z ) = - 2 4 z + 1 5 .
$$
Thus, the only possible multiple root of $p$ is $z = 5 / 8$ . But this is clearly seen not to be a root of $p ^ { \prime } .$ , since $5 ( 5 / 8 ) ^ { 4 } - 6 \neq 0$ . Thus $p$ has five distinct complex roots.
To count the real roots, we note that $p ( - 2 ) = - 1 7 < 0 , p ( 0 ) = 3 > 0 , p ( 1 ) = - 2 < 0 ,$ and $p ( 2 ) = 2 3 > 0$ . So, by continuity, $p$ has at least three real roots. However, $p ^ { \prime } ( x ) = 5 x ^ { 4 } - 6$ is negative when $\vert x \vert < \sqrt [ 4 ] { 6 / 5 }$ and positive when $\vert x \vert > \sqrt [ 4 ] { 6 / 5 }$ , so it has at most one root on each of the three intervals
$$
( - \infty , - \sqrt [ 4 ] { 6 / 5 } ) , \quad ( - \sqrt [ 4 ] { 6 / 5 } , \sqrt [ 4 ] { 6 / 5 } ) , \quad ( \sqrt [ 4 ] { 6 / 5 } , \infty ) .
$$
Therefore p has exactly three real roots.
## Problem 5A.
Score:
Compute
$$
\int _ { 0 } ^ { 2 \pi } { \frac { \cos ( x ) } { 2 + \cos ( x ) } } d x .
$$
Solution:
Put $z = e ^ { i x }$ . Then
$$
\int _ { 0 } ^ { 2 \pi } { \frac { \cos ( x ) } { 2 + \cos ( x ) } } d x = \int _ { | z | = 1 } { \frac { { \frac { z + z ^ { - 1 } } { 2 } } } { 2 + { \frac { z + z ^ { - 1 } } { 2 } } } } { \frac { d z } { i z } } = \int _ { | z | = 1 } { \frac { z ^ { 2 } + 1 } { z ( z ^ { 2 } + 4 z + 1 ) } } { \frac { d z } { i } } .
$$
The poles inside the unit circle are at $z = 0$ and $z = { \sqrt { 3 } } - 2$ . The answer is
$$
2 \pi \left( R e s _ { z = 0 } \frac { z ^ { 2 } + 1 } { z ( z ^ { 2 } + 4 z + 1 ) } + R e s _ { z = \sqrt { 3 } - 2 } \frac { z ^ { 2 } + 1 } { z ( z ^ { 2 } + 4 z + 1 ) } \right) =
$$
$$
2 \pi \left( 1 + { \frac { 4 - 2 { \sqrt { 3 } } } { 3 - 2 { \sqrt { 3 } } } } \right) = 2 \pi \cdot { \frac { 7 - 4 { \sqrt { 3 } } } { 3 - 2 { \sqrt { 3 } } } } .
$$
Let V be the complex vector space of complex $2 \times 2$ matrices X. Find all quadratic forms $Q$ on V such that $Q ( X ) = Q ( A X A ^ { - 1 } )$ for any complex invertible $2 \times 2$ matrix A.
## Solution:
Take $Q ( X ) = x T r ( X ^ { 2 } ) + y T r ( X ) ^ { 2 }$ . It clearly satisfies the requirements. These are the only possibilities, as the condition of invariance implies that Q is determined by its values on diagonal matrices (as diagonalizable matrices are dense in all matrices). Also Q is invariant under exchanging the two diagonal entries of a diagonal matrix, from which it follows easily that the space of invariant forms is at most 2-dimensional. (A similar argument works for n by n matrices, except that if $n < 2$ the space of quadratic forms has dimension less than 2 due to degeneracies.)
Please cross out this problem if you do not wish it graded
## Problem 7A.
Score:
Let A and B be $n \times n$ complex matrices. Prove or disprove each of the following statements:
1. If A and B are diagonalizable, so is A + B.
2. If A and B are diagonalizable, so is AB.
3. If $A ^ { 2 } = A$ , then A is diagonalizable.
4. If $A ^ { 2 }$ is diagonalizable, then A is diagonalizable.
## Solution:
1, 2, 4 are false, with many 2 by 2 counterexamples using the fact that any matrix of the form ab with b non-zero is not diagonalizable. 3 is true, as the minimal polynomial of A has no repeated roots.
Let R be a (possibly non-commutative) ring with identity, and let u be an element of R with a right inverse. Prove that the following conditions on u are equivalent:
1. u has more than one right inverse;
2. u is a zero divisor;
3. u is not a unit.
## Solution:
Let v be a right inverse of $u \colon u v = 1$
$( 1 ) \Longrightarrow ( 2 )$ : If $v ^ { \prime }$ is another right inverse of $u ,$ then $u ( v - v ^ { \prime } ) = 1 - 1 = 0$ with $v - v ^ { \prime } \neq 0$ so u is a zero divisor.
$( 2 ) \Longrightarrow ( 3 )$ : We prove the contrapositive. If u is a unit and if $u w = 0$ , then $0 = u ^ { - 1 } \cdot 0 =$ $u ^ { - 1 } u w = w .$ , so w = 0. Similarly, $w u = 0$ implies $w = 0$ . Thus u is not a zero divisor.
$( 3 ) \Longrightarrow ( 1 )$ : Since u is not a unit, $v u \ne 1$ . Let $v ^ { \prime } = v + ( v u - 1 )$ . Then $\boldsymbol { v } ^ { \prime } \neq \boldsymbol { v } ,$ , and
$$
u v ^ { \prime } = u ( v + v u - 1 ) = u v + u v u - u = 1 + 1 u - u = 1 .
$$
Thus $v ^ { \prime }$ is another right inverse of u.
Give an example of a group G such that the center of G modulo its center is non-trivial. Give an example of a group H such that the groups H, H0, $H ^ { \prime \prime }$ and $H ^ { \prime \prime \prime }$ are all distinct. (The derived group $H ^ { \prime }$ of a group H is the subgroup generated by commutators, or equivalently the smallest subgroup such that the quotient by this subgroup is an abelian group.)
## Solution:
The group G can be the dihedral group of order 8. The group H can be the symmetric group $S _ { 4 }$ on 4 points, with derived groups the alternating group $A _ { 4 } ,$ the Klein 4-group, and the trivial group.
Fall Semester 2013
1. Please write your 1- or 2-digit student exam number on this cover sheet and on all problem sheets (even problems that you do not wish to be graded).
2. Indicate below which six problems you wish to have graded. Cross out solutions you may have begun for the problems that you have not selected.
3. Extra sheets should be stapled to the appropriate problem at the upper right corner. Do not put work for problem p on either side of the page for problem q if $p \neq q$
4. No notes, books, or calculators may be used during the exam.
## PROBLEM SELECTION
Part B: List the six problems you have chosen:
## Problem 1B.
Score:
For which pairs of real numbers $( a , b )$ does the series $\scriptstyle \sum _ { n = 3 } ^ { \infty } n ^ { a } ( \log n ) ^ { b }$ converge?
## Solution:
By the integral test this is equivalent to asking for convergence of the integra l
$$
\int _ { x = 3 } ^ { \infty } x ^ { a } ( \log x ) ^ { b } d x
$$
This converges if $a < - 1$ and diverges if $a > - 1$ by comparison with $\textstyle \int x ^ { s } d x$ . If $a = - 1$ then it converges for $b < - 1$ and diverges if $b > - 1$ again by doing t he integral explicitly, using the fact that the derivative of $( \log x ) ^ { b + 1 } \mathrm { ~ i ~ s ~ } ( b + 1 ) ( \log x ) ^ { b } x ^ { - 1 }$ . For $a = b = - 1$ it diverges as the derivative of log log x is $x ^ { - 1 } ( \log x ) ^ { - 1 }$
Say that a metric space X has property (A) if the image of every continuous function f : X → R is an interval, which may be open, closed or half-open. Prove that X has property (A) if and only if it is connected.
## Solution:
Suppose that X does not have property (A). Then there is a continuous function f : X → R whose image is not an interval. If X is connected then f(X) is a connected subset of R, which must be an interval. Hence X is not connected.
Suppose that X is not connected. Write $X = X _ { 1 } \cup X _ { 2 }$ , where $X _ { 1 }$ and $X _ { 2 }$ are nonempty disjoint open subsets. Define $f : X \to \mathbf { R }$ to be one on $X _ { 1 }$ and two on $X _ { 2 }$ . Then f is continuous and its image is not an interval. Hence X does not have property (A).
Please cross out this problem if you do not wish it graded
## Problem 3B.
Score:
Suppose that $f : ( 0 , 1 ) \to \mathbf { R }$ is a continuous function with $\textstyle \int _ { 0 } ^ { 1 } | f ( t ) | \ d t < \infty$ . Define g : $( 0 , 1 ) \mathbf { R }$ by
$$
g ( x ) = \int _ { x } ^ { 1 } { \frac { f ( t ) } { t } } d t .
$$
Show that $\begin{array} { r } { \int _ { 0 } ^ { 1 } \left| g ( x ) \right| d x < \infty } \end{array}$
Solution:
For any $\epsilon > 0$
$$
\begin{array} { r l } & { \displaystyle \int _ { \epsilon } ^ { 1 } | g ( x ) | d x = \int _ { \epsilon } ^ { 1 } \left| \int _ { x } ^ { 1 } \frac { f ( t ) } { t } d t \right| d x \leq \int _ { \epsilon } ^ { 1 } \int _ { x } ^ { 1 } \frac { | f ( t ) | } { t } d t d x } \\ & { \quad \quad \quad = \displaystyle \int _ { \epsilon } ^ { 1 } \int _ { \epsilon } ^ { t } \frac { | f ( t ) | } { t } d x d t = \int _ { \epsilon } ^ { 1 } \left( 1 - \frac { \epsilon } { t } \right) | f ( t ) | d t \leq \int _ { 0 } ^ { 1 } | f ( t ) | d t . } \end{array}
$$
Hence $\begin{array} { r } { \int _ { 0 } ^ { 1 } \left| g ( x ) \right| d x < \infty } \end{array}$
## Problem 4B.
Score:
Compute
$$
\operatorname* { l i m } _ { N \to \infty } \int _ { - N } ^ { N } { \frac { x \sin ( x ) } { x ^ { 2 } + 1 } } d x .
$$
## Solution:
Let $C _ { N }$ be the circular arc in the upper half plane of radius N around the origin, oriented counterclockwise. For N large.
$$
\int _ { - N } ^ { N } { \frac { x e ^ { i x } } { x ^ { 2 } + 1 } } d x + \int _ { C _ { N } } { \frac { z e ^ { i z } } { z ^ { 2 } + 1 } } d z = 2 \pi i R e s _ { z = i } { \frac { z e ^ { i z } } { z ^ { 2 } + 1 } } = { \frac { \pi } { e } } i .
$$
$$
\operatorname* { l i m } _ { N \to \infty } \int _ { - N } ^ { N } { \frac { x \sin ( x ) } { x ^ { 2 } + 1 } } d x = { \frac { \pi } { e } } .
$$
By Jordan’s Lemma, lim $\begin{array} { r } { N \to \infty \int _ { C _ { N } } \frac { z e ^ { i z } } { z ^ { 2 } + 1 } d z = 0 } \end{array}$ . Taking imaginary parts gives
Let $U \subset \mathbf { C }$ be a bounded open set containing 0, and let $f : U \to U$ be an analytic function, whose Taylor series at 0 is
$$
f ( z ) = z + a _ { 2 } z ^ { 2 } + a _ { 3 } z ^ { 3 } + . . .
$$
Prove that $a _ { 2 } = 0$ . (Hint : consider the functions $g _ { n } ( z ) = f \circ . . . \circ f ( z )$ obtained by composing f with itself n times.)
## Solution:
Suppose that $U$ is contained in $\{ z : | z | \leq R \}$ for some $R < \infty$ . Then $| g _ { n } ( z ) | \le R$ for all $z \in U$ . The Taylor series expansion of $g _ { n }$ is $g _ { n } ( z ) = z + n a _ { 2 } z ^ { 2 } + . . . .$ . If U contains $\overline { { B ( 0 , \epsilon ) } }$ then
$$
n a _ { 2 } = { \frac { 1 } { 2 \pi i } } \int _ { | z | = \epsilon } { \frac { g _ { n } ( z ) } { z ^ { 3 } } } d z
$$
and $\begin{array} { r } { n | a _ { 2 } | \le \frac { R } { \epsilon ^ { 2 } } } \end{array}$ . Taking $n \to \infty$ implies that $a _ { 2 } = 0$
Please cross out this problem if you do not wish it graded
## Problem 6B.
Score:
Is it possible to find two real $2 \times 2$ matrices A, B such that $A ^ { 2 } = B ^ { 2 } = I d$ (the identity matrix), but AB has eigenvalues 2 and $1 / 2 ?$
Solution:
Yes. Take
$$
A = { \left( \begin{array} { l l } { 1 } & { 0 } \\ { 0 } & { - 1 } \end{array} \right) } \qquad B = { \left( \begin{array} { l l } { a } & { b } \\ { c } & { d } \end{array} \right) }
$$
Then require tr $B = a + d = 0$ , det $B = a d - b c = - 1$ 1, so $d = - a$ . Then require tr $4 B = 2 a =$ $5 / 2$ $d e t A B = a ^ { 2 } + b c = 1$ . Solve for example by
$$
B = \left( \begin{array} { c c } { { 5 / 4 } } & { { 1 } } \\ { { - 2 1 / 4 } } & { { - 5 / 4 } } \end{array} \right)
$$
Suppose that A is an m by n complex matrix and B is an n by m complex matrix, and write $I _ { m }$ for the m by m identity matrix. Show that if $I _ { m } - A B$ is invertible then so is $I _ { n } - B A$ (Hint: what does the condition that $I _ { m } - X$ is not invertible say about eigenvalues and eigenvectors of X?)
## Solution:
$I _ { m } - A B$ fails to be invertible exactly when it has an eigenvalue 0, in other words when there is a nonzero vector v in $R ^ { m }$ fixed by AB. But then Bv is a vector in $R ^ { n }$ fixed by BA, so $I _ { n } - B A$ fails to be invertible.
## Problem 8B.
Score:
Prove that if n is coprime to N = 561 then $n ^ { N - 1 } \equiv 1$ mod N.
## Solution:
The prime factors p of N are 3, 11, and 17 (each of which divides it to just the first power). For each prime factor p of N , N − 1 is divisible by p − 1 so $n ^ { N - 1 } \equiv 1$ mod p by Fermat’s theorem. So $n ^ { N - 1 } \equiv 1$ mod N.
How many irreducible polynomials of degree exactly 6 are there over the finite field with 3 elements?
Solution: $2 ( 3 ^ { 6 } - 3 ^ { 3 } - 3 ^ { 2 } + 3 ^ { 1 } ) / 6$ . The first factor of 2 is the possible leading coefficients, the second factor is the number of elements of the field of order $3 ^ { 6 }$ not in any smaller field, and the third factor of $1 / 6$ comes because each irreducible polynomial of degree 6 has 6 distinct roots generating this field.