## 403/503- Homework 4

March 21, 2011

This set is due Monday, April 11. The questions in problem 2 are required from everybody, and graduate students should also work on problem 1. (Of course, it would make me happier if everybody attempts problem 1 as well.)

1. Let $V$ be a real finite-dimensional, inner product space. For $T\in {\mathcal L}(V)$, define $\|T\|_1=\sup_{\|u\|=1}\|Tu\|$,

and $\|T\|_2=\sup_{\|u\|=1}|\langle u,Tu\rangle|$.

a. Prove that $\|\cdot\|_1$ is a norm on the vector space ${\mathcal L}(V)$. In particular, $\|T\|_1<\infty$ for all $T$. Also, prove  that $\|Tu\|\le\|T\|_1\|u\|$ for all $u.$
b. Prove that $\|T\|_2\le\|T\|_1$ for all $T$. Is $\|\cdot\|_2$ also a norm?
c. Prove that for any $T$ there are vectors $u_0,u_1$ of norm 1 with $\|T\|_1=\|Tu_0\|$ and $\|T\|_2=|\langle u_1,Tu_1\rangle|$.
d. Suppose now that $T$ is such that $\|T\|_1=\|T\|_2$. Prove (without appealing to the fundamental theorem of algebra and without using determinants) that $T$ admits an eigenvalue $\lambda$ (real) with eigenvector $u_1$ as in item c and, in fact, $\lambda=\langle u_1,Tu_1\rangle$.
e. Prove that for any $T$, we have $\|T^2\|_1\le\|T\|_1^2$.
f. Suppose that $T$ is self-adjoint. Check that so is $T^2$ and that $\|T^2\|_2=\|T^2\|_1$. In particular, this gives a proof that squares of self-adjoint operators on real vector spaces  admit eigenvalues that does not use the fundamental theorem of algebra. Check that the eigenvalues of $T^2$ are non-negative.
g. Again, let $T$ be self-adjoint. (So we know there is an orthonormal basis for $V$ consisting of eigenvectors of $T.$) Assume also that $T$ is invertible, that there is a unique eigenvalue $\lambda$ of $T$ of largest absolute value, and that this $\lambda$ satisfies ${\rm dim}({\rm null}(T-\lambda I))=1$. Let $u$ be an eigenvector of $T$ with eigenvalue $\lambda$ and such that $\|u\|=1$. Starting with a vector $v_0$ of norm 1 (arbitrary except for the fact that $v_0$ is not orthogonal to $u$), define a sequence $v_1,v_2,\dots$ of unit vectors by setting $v_{k+1}=\displaystyle \frac1{\|Tv_k\|}Tv_k$

(and note we are not dividing by 0, so these vectors are well defined). Also, define a sequence of numbers $\lambda_1,\lambda_2,\dots$ by setting $\lambda_k=\langle v_k,Tv_k\rangle.$

Prove that there is a sequence $\epsilon_1,\epsilon_2,\dots$ with each $\epsilon_k$ equal to 1 or $-1$ and such that $\|v_k-\epsilon_k u\|\to 0$

and $|\lambda_k-\lambda|\to 0$

as $k\to\infty$.

2. Solve problems 7.1, 7.3, 7.6, 7.7, 7.11, 7.14 from the book.

Note: In problem 1.f, the eigenvalues of $T^2$ are precisely the squares of the eigenvalues of $T$, but at the moment I do not have a way of showing this directly. As extra-credit, show without appealing to the fundamental theorem of algebra (and without using determinants, of course) that $T$ must have a real eigenvalue.

## 403/503- Homework 3

March 7, 2011

This homework set is due Monday, March 21 at the beginning of lecture. Problems 1-5 are required from everybody, and graduate students should also work on problem 6. (Of course, everybody is more than welcome to work on everything, including the remarks on $f$ mentioned at the end of problem 6.)

1. Solve problems 5.3, 5.6, 5.8, 5.10, 5.11, 5.14, 5.20, 5.21, 5.23 from the book.
2. Solve problems 6.6, 6.7, 6.8 from the book.
3. The taxicab norm on ${\mathbb R}^2$ is defined by setting $\|v\|=|v_1|+|v_2|$ where $v=(v_1,v_2)$. Show that this is indeed a norm, and that there is no inner product $\langle\cdot,\cdot\rangle$ on ${\mathbb R}^2$ for which $\|v\|=\sqrt{\langle v,v\rangle}$. Find two non-congruent non-degenerate triangles with sides of length 1, 1, 2. (Of course, lengths are computed with respect to this norm, not the usual one).
4. Prove Lagrange’s identity: If $P(x_1,\dots,x_n,y_1,\dots,y_n)=$ $\displaystyle \left(\sum_{i=1}^n x_i^2\right)\left(\sum_{i=1}^n y_i^2\right)-\left(\sum_{i=1}^n x_iy_i\right)^2$, then $P(x_1,\dots,x_n,y_1,\dots,y_n)=$ $\displaystyle \sum_{1\le i. Note that this implies the Cauchy-Schwarz inequality for the usual inner product on ${\mathbb R}^n$.
5. Prove the Cauchy-Schwarz inequality for the usual product in ${\mathbb R}^n$ as follows: Given $u,v\in{\mathbb R}^n$, consider the function $f(\lambda)=\|\lambda u+v\|^2$ as a quadratic in $\lambda$, and deduce the inequality by examining the discriminant of $f$.
6. Consider a unit square ${H}$. Inscribe in ${H}$ exactly ${n}$ squares with no common interior point. (The squares do not need to cover all of ${H}$.) Denote by ${e_1,\dots,e_n}$ the side lengths of these squares, and define $\displaystyle f(n)=\max\sum_{i=1}^ne_i.$ Show that ${f(n)\le\sqrt n}$, and that equality holds iff ${n}$ is a perfect square. (An 80+ years old open problem of Erdös is to find all ${n}$ for which ${f(n)=f(n+1)}$. Currently, it is only known that ${f(n) for all ${n}$, ${f(1)=f(2)=1}$, ${f(4)=f(5)=2}$, and that if ${f(n)=f(n+1)}$, then ${n}$ is a perfect square.)

## 403/503- Nim addition and multiplication

March 7, 2011

The notions of Nim addition and Nim multiplication that we discussed in the first homework set are due to John Conway, who studied them in the context of ordinal numbers. The ordinals extend the natural numbers, and what we did was to only consider “an initial segment”. Recently, the excellent blog neverendingbooks by Lieven Le Bruyn has discussed Conway’s construction in detail, in a series of (so far, ten) posts that you may enjoy reading and I highly recommend:

In particular, the posts have links to papers and talks on related subjects.