\documentclass[12pt]{amsart}

\usepackage{amssymb}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\topmargin}{0pt}
\setlength{\marginparsep}{0pt}
\setlength{\marginparwidth}{1in}

\newcommand{\ZZ}{\mathbf{Z}}
\newcommand{\NN}{\mathbf{N}}
\newcommand{\RR}{\mathbf{R}}
\newcommand{\QQ}{\mathbf{Q}}
\newcommand{\CC}{\mathbf{C}}

\newcommand{\on}{\operatorname}
\newcommand{\ra}{\rightarrow}

\author{Math 25}

\title{Homework 10 --- due Dec 5th}

\begin{document}

\maketitle
\setlength{\baselineskip}{18pt}

There are two sections: A and B.
Please return each part
to the proper CA.

\renewcommand{\thesection}{\Alph{section}}

\section{Problems graded by Benjamin}

\subsection{} Find the rank of the matrix $A=(a_{i,j})_{1 \leq i,j
  \leq n}$ in the following cases:
\begin{enumerate}
\item $a_{i,j}=i+j-1$. 
\item $a_{i,j}=\cos(\alpha(i+j))$ where $\alpha \in \RR$.
\item $a_{i,j}=(\alpha+i+j)^2$ where $\alpha \in \RR$.
\end{enumerate}

\subsection{} Let $E$ be a vector space 
over a field $K$,
and let $F$ be a subspace (not
equal to $E$). Prove that $\on{Vect}(E \setminus F)=E$ (i.e. that
every vector in $E$ is a linear combination of vectors of
$E\setminus F$). Make sure your proof works for every field $K$.

\subsection{} Let $K$ be an infinite field, let 
$V$ be a $K$-vector space of dimension $n$ 
and let $W_1, \cdots, W_k$ be subspaces of $V$ of 
dimension $\leq n-1$. Prove that $V \neq \cup_{i=1}^k W_i$.

Show that this is not always true if $K$ is finite. 

\subsection{} Let $V$ be a $K$-vector space of dimension $n$ 
and let $W_1$ and $W_2$ be two subspaces of the same dimension 
$r \leq n-1$. 
Prove that there exists a subspace $U$ of $V$ such that $V = W_1
\oplus U$ and $V = W_2 \oplus U$.

\subsection{} Let $V$ be a finite dimensional 
$K$-vector space and let $u,v,w \in
\mathcal{L}(V,V)$ be three endomorphisms of $V$. Prove the following
inequalities:
\begin{enumerate}
\item $\on{rk}(u+v) \leq \on{rk}(u) + \on{rk}(v)$.
\item $\on{rk}(u+v) \geq |\on{rk}(u) - \on{rk}(v)|$.
\item $\inf(\on{rk}(u),\on{rk}(v)) \geq \on{rk}(uv) \geq \on{rk}(u) +
  \on{rk}(v) - \dim(V)$
\item $\on{rk}(uv) + \on{rk}(vw) \leq \on{rk}(v)+\on{rk}(uvw)$.
\end{enumerate}
Use the last inequality to prove that if $k \geq 1$, 
and $u^k$ denotes $u \times \cdots \times u$ ($k$ times) then:
\[ \on{rk}(u^k) \leq \frac{1}{2} (\on{rk}(u^{k+1}) +
\on{rk}(u^{k-1})). \]

\section{Problems graded by Inna}

\subsection{} Let $e=\{e_1,\cdots,e_n\}$ and $f=\{f_1,\cdots,f_n\}$ be two
bases of a vector space $V$. Check that if $A$ is the matrix of $e$ in
$f$ and if $B$ is the matrix of $f$ in $e$ then $AB=BA=\on{Id}$.

\subsection{} Let $V$ be the space of polynomials $P \in \RR[X]$ whose
degree is at most $n-1$. 
\begin{enumerate}
\item  check that $\{1,X,X^2,\cdots,X^{n-1}\}$ is a basis of $V$ 
and that the map $P(X) \mapsto P(X+1)$ is a
linear map from $V$ to itself. 
\item Write the matrix $M$ of $P(X) \mapsto P(X+1)$ in the above basis.
\item find $M^{-1}$.
\end{enumerate}

\subsection{} Let $V$ be the vector space of all functions from $\RR$
to $\RR$. Prove that the following families are free:
\begin{enumerate}
\item $\{e_1 \cdots e_n\}$ where the $\alpha_i$'s
  are distinct real numbers and $e_i(x)=e^{\alpha_i x}$.
\item $\{f_1 \cdots f_n\}$ where the $\alpha_i$'s
  are distinct real numbers and $f_i(x)=|x-\alpha_i|$.
\end{enumerate}

\subsection{} Let $U, V, W$ be three (finite dimensional) $K$-vector
spaces, and let $w \in \mathcal{L}(U,W)$.
\begin{enumerate}
\item If $u \in \mathcal{L}(U,V)$, prove that there exists $v \in
  \mathcal{L}(V,W)$ such that $w=vu$ if and only if $\ker u \subset
  \ker w$.
\item If $v \in \mathcal{L}(V,W)$,  prove that there exists $u \in
  \mathcal{L}(U,V)$ such that $w=vu$ if and only if $\on{im} w \subset \on{im}
  v$. 
\end{enumerate}

\subsection{} Let $M$ be a $n \times n$ matrix with entries in a
field $K$. 
\begin{enumerate}
\item prove that $M$ is invertible if and only if it has rank $n$.
\item prove that if we write $M=(C_1,\cdots,C_n)$ then 
$M$ is invertible if and only if the dimension of the subspace of
  $K^n$ generated by $C_1, \cdots, C_k$ is $k$ for every $1 \leq k \leq
  n$.
\item \label{all} assume now that $K=\ZZ/p\ZZ$, the field with $p$ elements. How
  many $n \times n$ matrices with entries in $\ZZ/p\ZZ$ are there?
\item how many of them are invertible?
\item (extra credit) let $f(n,r)$ be the number of $n \times n$
  matrices with entries in $\ZZ/p\ZZ$ which have rank $r$. Give a
  formula for $f(n,r)$ and check that $f(n,0)+f(n,1)+\cdots+f(n,n)$
  agrees with the result of (\ref{all}).
\end{enumerate}

\end{document}

