\input amstex
\input amssym.def
\nopagenumbers
\magnification=\magstep1
\centerline{\bf HW  \#1}
\bigskip
\centerline {\bf Math 506A}
\bigskip
\noindent 1. Show that the characteristic polynomial of the companion matrix $C(f)$ is $f$ (up to sign) for any monic polynomial $f$.
\vskip .3in
\noindent 2. Show that the number of similarity classes of $3\times 3$ matrices over $\Bbb Q$ with a given characteristic polynomial  is the same as the number of similarity classes of such matrices over any extension field of $\Bbb Q$.  Give an example to show that this is not true in general for $4\times 4$ matrices.
\vskip .3in
\noindent 3. Show that a square matrix over $k$ is diagonalizable if and only if its minimal polynomial over $k$ is the product of distinct linear factors.
\vskip .3in
\noindent 4. (20 points) Let $q=p^n$ be a power of a prime $p$.  A {\sl deBruijn sequence for $q$} is a sequence $s=a_0\ldots a_{q-1}$ of $q$ symbols, each an element of the field $F_p$ of order $p$, such that every sequence $b_1\ldots b_n$ of $n$ symbols, each an element of $F_p$, occurs exactly once as a consecutive subsequence $a_i\ldots a_{i+n-1}$ of $s$ for $i\in[0,q-1]$; here addition of subscripts takes place modulo $q$, so that the sequence wraps around.  Show that a deBruijn sequence exists by the following steps.  Start with the field $F_q$ of order $q$ and show that it has a nonzero element $x$ of multiplicative order $q-1$.  Let $f$ be the minimal polynomial of $x$ over $F_p$, so that $f$ has degree $n$.  Then the matrix of multiplication by $x$ on $F_q$, regarded as an $n$-dimensional vector space over $F_p$, is the transpose $M=C(f)^t$ of $C(f)$ with respect to some basis, by a result in class.  Now define the sequence $s$ by decreeing first that $v=(a_0,\ldots,a_{n-1}) = (0,\ldots,0,1)$ and then that the vector $(a_i,\ldots,a_{i+n-1})=(M^iv^t)^t$, the transpose of the column vector $M^iv^t$, for $0\le i\le q-n$.  Show that this makes sense and yields a deBruijn sequence $a_0\ldots a_{q-1}$, making sure to check also that $00\ldots 0$ is a consecutive subsequence of $s$.
\end