\documentstyle[12pt]{article} %\pagestyle{empty} \newcount\probno \probno=0 \def\prob{\advance\probno by 1 \bigskip\par\noindent\the\probno . } \def\by{\times} \def\entry{{\rm entry}} \def\span{{\rm span}} \def\mat{{\rm MAT}} \def\topz{{\rm T}} \def\reals{{\bf R}} \begin{document} \centerline{A. Miller \hfill M340 \hfill Exam 2 \hfill April 97} \bigskip You may use without proof any theorem proved in class, all of which are on the fourteen page handout; however when you do so, you should {\bf state the result} you are using. You may also use any assigned exercise, but in this case you should {\bf state the exercise and give a full proof} of the exercise in your solution. \bigskip \prob Suppose $V$ is a vector space, $W$ is a subset of $V$, and $v_1,v_2,\ldots,v_n$ are elements of $V$. \par Define \begin{enumerate} \begin{enumerate} \item $W$ is a subspace of $V$. \item $\span(\{v_1,v_2,\ldots,v_n\})$. \item $v_1,v_2,\ldots,v_n$ are linearly independent. \item $v_1,v_2,\ldots,v_n$ are linearly dependent. \item $v_1,v_2,\ldots,v_n$ are a basis for $V$. \end{enumerate} \end{enumerate} \prob A. Let $u_1,u_2,u_3$ be elements of a vector space. Suppose $$v_1=u_1-u_2$$ $$v_2=u_2-u_3$$ $$v_3=u_3-u_1$$ Prove that $v_1,v_2,v_3$ are linearly dependent. B. Suppose $u_1,u_2,u_3$ is a basis of the vector space $V$. Let $$v_1=u_1+u_2$$ $$v_2=u_2+u_3$$ $$v_3=u_1+u_3$$ Prove that $v_1,v_2,v_3$ is a basis of $V$. \prob A matrix $A_{n\times n}$ is Toplitz iff it is constant on all its `diagonals'. For example: $$A= \left[ \begin{array}{rrrr} 0 & 6 & -4 & 0 \\ -8 & 0 & 6 & -4 \\ -2 & -8 & 0 & 6 \\ 6 & -2 & -8 & 0 \\ \end{array} \right] $$ So $\entry_{i,j}(A)=0$ if $i=j$ or $i-j=0$, $\entry_{i,j}(A)=-8$ if $i-j=1$, $\entry_{i,j}(A)=6$ if $i-j=-1$, etc. More precisely an $n\times n$ matrix $A$ is Toplitz iff for all $i,j,i^\prime, j^\prime$ between $1$ and $n$ $$\mbox{ if }i-j=i^\prime-j^\prime \mbox{ then } \entry_{i,j}(A)=entry_{i^\prime,j^\prime}(A).$$ A. Prove that $$\topz_n=\{A\in \mat_{n\times n}: A \mbox{ is Toplitz }\}$$ is a subspace of $\mat_{n\times n}$. If you would prefer you may assume $n=4$, i.e., show $\topz_4$ is a subspace of the $4\times 4$ matrices. B. Find a formula for the dimension of $\topz_n$ in terms of $n$, i.e., $$\dim(\topz_n)=?$$ Justify your formula by writing down a basis for $\topz_3$ and $\topz_4$. \prob Let $A$ be the following matrix: $$A= \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0\\ \end{array} \right] $$ Let $W$ be defined as follows: $$W=\{B\in\mat_{2,2}: AB=BA\}$$ Find a basis for $W$ and prove that it is a basis. \prob Suppose $A$ is any $n\times n$ matrix. Prove there exists a polynomial $$p(x)=a_0+a_1x+a_2x^2+\cdots+a_kx^k$$ of degree $k$ with $1\leq k\leq n^2$ such that $$p(A)=a_0I+a_1A+a_2A^2+\cdots+a_kA^k=Z$$ where $I$ is the $n\times n$ identity matrix and $Z$ is the $n\times n$ zero matrix. \bigskip Hint: What is the dimension of $\mat_{n,n}$ and what is the size of the set $\{0,1,2,\ldots,n^2\}$? \newpage \begin{center} Answers \end{center} \bigskip \par 1a. $u,v\in W$ implies $u+v\in W$ and $au\in W$. \par 1b. $\span(\{u_1,\ldots,u_n\})=\{a_1u_1+\cdots+a_nu_n: a_1,...,a_n \mbox{ scalars}\}$ \par 1c. $a_1v_1+a_2v_2+\cdots+a_nv_n=z$ implies $a_1=a_2=\cdots=a_n=0$ \par 1d. not linearly indendent. \par 1e. linearly independent and spans $V$. \bigskip 2A. $v_1+v_2+v_3=(u_1-u_2)+(u_2-u_3)+(u_3-u_1)=z$. 2B. We show $v_1,v_2,v_3$ are linearly independent. Suppose $$av_1+bv_2+cv_3=z.$$ Then $$a(u_1+u_2)+b(u_2+u_3)+c(u_1+u_3)=z \mbox{ so } (a+c)u_1+(a+b)u_2+(b+c)u_3=z.$$ Since $u_1,u_2,u_3$ are linearly independent we have $a+c=0$, $a+b=0$, and $b+c$=0. Solving for $a,b,c$ we get $a=-c=b$ so $a=b$. But $a=-b$ also so $b=-b$ and so $b=0$. Since $a=-c=b$, we have $a=0$ and $c=0$. This shows $v_1,v_2,v_3$ are linearly independent. Since any $n$ linearly independent vectors in a vector space of dimension $n$ is a basis, it follows that $v_1,v_2,v_3$ is a basis. Remark: Many students asserted without proof that $$\span(\{u_1,u_2,u_3\})=\{(a+c)u_1+(a+b)u_2+(b+c)u_3:a,b,c\in\reals\}$$ But if $u_1,u_2,u_3$ are linearly independent, then $$\span(\{u_1,u_2,u_3\})\not= \{(a-c)u_1+(b-a)u_2+(c-a)u_3:a,b,c\in\reals\}$$ (This follows from the fact the $v_1,v_2,v_3$ in part A are linearly dependent.) So something must be proved. A correct proof can be given by showing that for any $a_1,a_2,a_3$ there exists $a,b,c$ so that $a+b=a_1$, $b+c=a_2$, and $b+c=a_3$. \bigskip 3.A. Suppose $A,B\in\topz_n$. Suppose $i-j=i^\prime-j^\prime$ and $a,b$ are scalars. Then since $A$ and $B$ are Toplitz, $$\entry_{i,j}(A)=\entry_{i^\prime,j^\prime}(A) \mbox{ and } \entry_{i,j}(B)=\entry_{i^\prime,j^\prime}(B).$$ But then $$\entry_{i,j}(aA+bB)=a\entry_{i,j}(A)+ b\entry_{i,j}(B)= $$ $$a\entry_{i^\prime,j^\prime}(A)+b\entry_{i^\prime,j^\prime}(B)= \entry_{i^\prime,j^\prime}(aA+bB)$$ Hence $(aA+bB)\in\topz_n$. 3.B $\dim(\topz_n)=2n-1$. $$ \left[ \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \\ \end{array} \right], \left[ \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right], \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right], \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{array} \right], \left[ \begin{array}{ccc} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right]$$ is a basis for $\topz_3$. (Similarly for $\topz_4$.) Each basis vector is determined by a diagonal and there are $2n-1$ diagonals. (Count the number of entries in a $n\times n$ matrix which are in either the first row or first column. The $-1$ is there because the $1,1$ is counted twice.) \bigskip 4. $$ \left[ \begin{array}{cc} a & b \\ c & d \\ \end{array} \right] \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right] = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right] \left[ \begin{array}{cc} a & b \\ c & d \\ \end{array} \right] $$ gives us $$ \left[ \begin{array}{cc} c & d \\ a & b \\ \end{array} \right] = \left[ \begin{array}{cc} b & a \\ d & c \\ \end{array} \right] $$ and therefore $a=d$ and $b=c$. So $$ W=\{B\in\mat_{2,2}: AB=BA\}=\{ \left[ \begin{array}{cc} a & b \\ b & a \\ \end{array} \right]: a,b \in\reals\}$$ We show $$ \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right], \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right] $$ is a basis for $W$. To see they are linearly independent, suppose $$ a\left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right]+ b\left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right]= \left[ \begin{array}{cc} a & b \\ b & a \\ \end{array} \right]= \left[ \begin{array}{cc} 0 & 0 \\ 0 & 0 \\ \end{array} \right].$$ But then $a=b=0$. To see that they span $W$: $$\span(\{\left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right], \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right]\})= \{ a\left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right]+ b\left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right]: a,b\in\reals\}= $$ $$ =\{ \left[ \begin{array}{cc} a & b \\ b & a \\ \end{array} \right]: a,b \in\reals\}=W$$ \bigskip 5. The dimension of the vector space $\mat_{n,n}$ is $n^2$. The {\bf Main Theorem} proved in class is that if a vector space is spanned by $m$ vectors, then any sequence of $m+1$ vectors is linearly dependent. The sequence of $n\times n$ matrices $$I_{n\times n},A,A^2,A^3,\ldots,A^{n^2}$$ has length $n^2+1$ and is therefore linearly dependent. So there exists a nontrivial linear combination $$a_0I_{n\times n}+a_1A+a_2A^2+\cdots+a_{n^2}A^{n^2}=Z_{n\times n}$$ Let $k$ be the largest such that $a_k\not=0$, clearly $k>0$ because $a_0I\not=Z$ if $a_0\not=0$, and so $$p(x)=a_0+a_1x+a_2x^2+\cdots+a_kx^k$$ is a polynomial with degree $k$ ($1\leq k\leq n^2$) such that $p(A)=Z$. \bigskip \bigskip \hrule \bigskip Grading Key: 1. 4 pts each definition, 2 if partially right 2. 10 part A, 10 part B - 5 each for span,lin indep 3. 10 each part 4. 10 for a correct basis, 5 each for showing lin indep and spans 5. 2 each for $\dim(\mat_{n,n})=n^2$ and size of $\{0,1,\ldots,n^2\}$ is $n^2+1$. \end{document}