Instructions: Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Read the course syllabus in its entirety. If you have questions, ask the instructor.
Read the course FAQ in its entirety. If you have questions, ask the instructor.

Prove one of the distributive laws for $\vee$ and $\wedge$ for logical statements: if $P$, $Q$ and $R$ are statements, then
- $(P \vee (Q \wedge R)) \Leftrightarrow \left((P\vee Q) \wedge (P \vee R)\right)$
- $(P \wedge (Q \vee R)) \Leftrightarrow \left((P\wedge Q) \vee (P \wedge R)\right)$
Is the implication connective associative? That is, if $P$, $Q$ and $R$ are statements, are $(P \Rightarrow Q) \Rightarrow R$ and $P \Rightarrow (Q \Rightarrow R)$ logically equivalent? (Whatever your assertion, you should --- of course --- support it with a rigorous proof.)
Suppose that $P$,$Q$ and $R$ are statements. Reexpress the statement $(P \Rightarrow Q) \Rightarrow \neg R$ in terms of the statements $P$,$Q$ and $R$ combined with the connectives $\wedge$ and $\vee$ and the modifier $\neg$ (together with any relevant parentheses). Prove your assertion. (Note: your answer will begin by stating your intended assertion and then verifying it. A formal proof does not require you to exhibit whence your assertion comes.)
Suppose that $P$,$Q$ and $R$ are statements. Prove that the statement "$P \Rightarrow (Q \vee R)$" is equivalent to the statement "$(P \wedge \neg Q) \Rightarrow R$". (Note: we'll frequently encounter results formulated as in the first statement, and our proof technique will be to verify the second statement.)

Here are some other problems you ought to complete, but you won't submit them as part of the assignment.

You have spent an outsized portion of your mathematical life thinking about functions whose domain and codomain are some subsets of $\mathbb{R}$. Often these functions have been continuous. Sometimes in high school, students learn that a function is continuous if its graph can be drawn without picking up the pen while being drawn. The technical definition is more specific, and relies on what it means for $f$ to be continuous at some point $x_0$. The spiritual content of continuity of a function $f:\mathbb{R} \to \mathbb{R}$ at $x_0$ is as follows: for any specified tolerance, there is some notion of "close enough" so that if $x$ is ``close enough" to $x_0$, then the distance between $f(x_0)$ and $f(x)$ is smaller than the specified tolerance. Write this as a quantified statement, and then write out its negation as a quantified statement. Your statements should take the form of quantified variables followed by a predicate, where your predicate should only include the connectives $\wedge$ and $\vee$, together with the modifier $\neg$ (and any necessary parentheses).
In number theory, Goldbach's conjecture states that every positive even number greater than $2$ can be written as the sum of two prime numbers.
1. Write Goldbach's conjecture in the form of a quantified statement. (You might choose to use $2\mathbb{Z}$ to denote the set of even numbers, and $\mathbb{P}$ to denote the set of primes.)
2. Many mathematicians believe that Goldbach's conjecture is true. What would you need to do in order to prove that Goldbach's conjecture is false?

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

For each of the following systems, compute the set of solutions.
1. $\displaystyle \left\{\begin{array}{rcl}x-z&=&1\\y+2z-w&=&3\\x+2y+3z-w&=&7\end{array}\right\}$
2. $\displaystyle \left\{\begin{array}{rcl}y+w&=&0\\x-y+z&=&0\\3x-2y+3z+w&=&0\\x+z+w&=&0\end{array}\right\}$
Describe the values of $k$ that give rise to no solutions, one solution or many solutions to the following system: $$\mathcal{L} = \left\{\begin{array}{c}x-y = 1\\3x-3y=k\end{array}\right\}.$$ Be sure to justify any assertions you make.
Describe all vectors $$\mathbf{b} = \left[\begin{array}{c}b_1\\b_2\\b_3\\b_4\end{array}\right] \in \mathbb{R}_{4\times 1}$$ so that the following system has solutions: $$\left\{\begin{array}{rcl}x-3y&=&b_1\\3x+y&=&b_2\\x+7y&=&b_3\\2x+4y&=&b_4\end{array}\right\}.$$ Express your answer in the format we've used to describe solution sets for systems of linear equations.

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

Suppose that $\mathcal{L}$ is a system of linear equations over a field $\mathbb{F}$: $$\left\{\begin{array}{c&c&c&c&c&c&c&c&c}a_{1,1}x_1&+&a_{1,2}x_2&+&\cdots&+&a_{1,c}x_c&=&b_1\\a_{2,1}x_1&+&a_{2,2}x_2&+&\cdots&+&a_{2,c}x_c&=&b_2\\&&&&\vdots&&&&&\\a_{r,1}x_1&+&a_{r,2}x_2&+&\cdots&+&a_{r,c}x_c&=&b_r\end{array}\right\}.$$ Write $\text{Sol}(\mathcal{L})$ for the set of solutions to the system $\mathcal{L}$. We say that $\mathcal{L}$ is homogeneous if all the $b_i$ are zero.
1. Prove that any homogeneous system has at least one solution.
2. Prove that if $\mathcal{L}$ is a homogeneous system so that $$\mathbf{s} = \left[\begin{array}{c}s_1\\s_2\\\vdots\\s_c\end{array}\right] \in \text{Sol}(\mathcal{L})\quad \text{ and } \quad \mathbf{t} = \left[\begin{array}{c}t_1\\t_2\\\vdots\\t_c\end{array}\right]\in \text{Sol}(\mathcal{L}),$$ then $\mathbf{s}+\mathbf{t}\in \text{Sol}(\mathcal{L})$.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

In class we stated that if we perform an elementary row operation on the augmented matrix $[A|B]$ and arrive at the augmented matrix $[C|D]$, then the solution sets for $AX=B$ and $CX=D$ will be equal. In this problem, you'll offer a partial proof of this result. Throughout we will assume that we transform $[A|B]$ to $[C|D]$ by performing the row operation $cR_i + R_j$; in other words, we add $c$ copies of row $i$ into row $j$. We will write $r$ for the number of rows of $A$, and $c$ for the number of columns of $A$.
1. Suppose that $X = \left[\begin{array}{c}x_1\\\vdots\\x_c\end{array}\right] \in \mathbb{F}_{c \times 1}$ is a solution to $AX = B$. Recall that this means $$a_{k,1}x_1 + a_{k,2}x_2 + \cdots + a_{k,c}x_c = b_k$$ is a valid equality for all $1 \leq k \leq r$ . Prove that for this same $X$, we also have $CX = D$.
2. Now suppose that $X = \left[\begin{array}{c}x_1\\\vdots\\x_c\end{array}\right] \in \mathbb{F}_{c \times 1}$ is a solution to $CX = D$. Prove that for this same $X$, we also have $AX = B$.
(It's worth knowing that the technique we've employed here is often called a dual containment argument for showing that two sets are equal. In this case, the sets we want to show are equal are the solution sets to the two systems $AX=B$ and $CX=D$. We achieved this by assuming we had an element in one set, and argued it also had to live in the other set.)

Suppose that $A \in \mathbb{F}_{n \times n}$ for some positive integer $n$. (Such matrices are sometimes called "square matrices"). Prove that if there exists some $B \in \mathbb{F}_{n\times 1}$ so that $AX=B$ has a unique solution, then for all $C \in \mathbb{F}_{n \times 1}$ we have $AX=C$ has a unique solution.
Suppose that $E$ is a reduced row echelon matrix $E$, and that $A$ is row equivalent to $E$ via the elementary row operations $\rho_1,\cdots, \rho_n$: $$A \stackrel{\rho_1}{\to} \cdots \stackrel{\rho_n}{\to} E.$$ Suppose further that $E$ has (at least) one row of zeros. Explain how one would construct/find a vector $B$ so that $AX = B$ has no solutions.

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

Suppose that $A \in \mathbb{F}_{r \times c}$. Recall from class that for a given $n \in \mathbb{N}$, we use $I_n$ to denote the $n \times n$ matrix with $1$s along the main diagonal, and $0$s elsewhere. (This is the so-called $n \times n$ identity matrix.) Prove (by resorting to the definition of matrix multiplication from class) that $AI_c = A$ and $I_r A = A$.
Let $$A = \left[\begin{array}{rr}-1&3\\3&-9\end{array}\right].$$ Show that there is no matrix $B$ so that $AB = I_2$. (Hint: let $b_{11}, b_{12}, b_{21}$ and $b_{22}$ be the entries of $B$. What would need to be true about these entries if $AB = I_2$?)
Find explicit matrices $A,B$ and $C$ -- all of whose entries are nonzero -- so that $AB = AC$, and yet $B \neq C$.

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

Suppose that $A \in \mathbb{F}_{r \times c}$ with $r < c$, and suppose that $B$ is any column vector in $\mathbb{F}_{r \times 1}$. Prove that $AX=B$ cannot have precisely one solution.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

($\star$) Prove the socks and shoes theorem: if $A$ and $B$ are $n \times n$ matrices so that $A^{-1}$ and $B^{-1}$ exist, then $AB$ has a multiplicative inverse, and that inverse is $B^{-1}A^{-1}$. [Hint: use uniqueness of inverses.]
If $A,B \in \mathbb{F}_{n \times n}$, we say that $A$ is similar to $B$ --- denoted $A \approx B$ --- if and only if there exists some invertible $P\in \mathbb{F}_{n \times n}$ with $A = PBP^{-1}$. Prove that $\approx$ is an equivalence relation; i.e., check the following three properties
1. (Reflexivity) for all $A \in \mathbb{F}_{n \times n}$, we have $A \approx A$;
2. (Symmetry) if $A \approx B$, then $B \approx A$; and
3. (Transitivity) if $A \approx B$ and $B \approx C$, then $A \approx C$.
Compute the inverse of the following matrix: $$A=\left[\begin{array}{rrr}1&0&-1\\-1&1&1\\1&1&1\end{array}\right].$$ Then express $A^{-1}$ as a product of elementary matrices.

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

($\star$) In class we stated that if $\rho$ is an elementary row operation, then $E_\rho$ is invertible, with $(E_\rho)^{-1} = E_{\rho^{-1}}$. We proved this in the case when $\rho$ is an elementary row operation of the first kind (i.e., when $\rho$ exchanges a pair or rows). Provide a proof of this fact when $\rho$ is an elementary operation of the third kind: i.e., $\rho = sR_i + R_j$ for some $s \in \mathbb{F}$ and $i \neq j$.
Prove that a $2 \times 2$ matrix $A = \left[\begin{array}{cc}a&b\\c&d\end{array}\right]$ is invertible if and only if $ad-bc \neq 0$. When $ad-bc \neq 0$, prove that $A^{-1} = \frac{1}{ad-bc}\left[\begin{array}{rr}d&-b\\-c&a\end{array}\right]$.
A matrix $A\in \mathbb{F}_{n \times }$ is called upper triangular if $a_{ij} = 0$ for all $i > j$; it is called strictly triangular if $a_{ij} = 0$ for all $i \geq j$. For the purposes of this problem, we'll write $Z$ for the matrix in $\mathbb{F}_{n \times 1}$ whose entries are all zero.
1. Prove that if $A \in \mathbb{F}_{n \times n}$ is strictly triangular, then the first and second columns of $A^2 = AA$ both equal $Z$.
2. Suppose you knew that for any strictly triangular matrix $A \in \mathbb{F}_{n \times n}$ and any $2 \leq k < n$, the first $k$ columns of $A^k$ were all equal to $Z$. Prove that the $k+1$st column of $A^{k+1}$ is equal to $Z$.
[Note: this problem gives a step-by-step approach to using a technique known as mathematical induction to prove the fact that for a strictly upper triangular matrix $A \in \mathbb{F}_{n \times n}$ and any $1 \leq m \leq n$, the first $m$ columns of $A^m$ are equal to $Z$. In particular, this means that $A^{n}$ is the zero matrix.]

Here are some other problems you ought to complete, but you won't submit them as part of the assignment.

For each of the following matrices $A$, determine if $A$ is nonsingular. If it is, compute $A^{-1}$. If it isn't, explain why.
1. $A = \left[\begin{array}{rrrr}1&2&-3&-4\\-3&-1&4&5\\2&4&-6&-3\\-4&2&2&7\end{array}\right]$
2. $A = \left[\begin{array}{rrr}1&1&0\\1&0&1\\0&1&1\end{array}\right]$
3. The three matrices from Exercise 1 of Section 1.9 of our text,.

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

You should work on this problem by yourself, or with the assistance of the instructor.

Prove that if $A,B \in \mathbb{F}_{n \times n}$ satisfy the property that $AB$ is invertible, then both $A$ and $B$ are invertible.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

In class we said that for any $A \in \mathbb{F}_{r\times c}$ and $M \in \mathbb{F}_{c \times \ell}$, we have $$CS(AM) \subseteq CS(A).$$ Prove this assertion. Then, prove that if we additionally know that $CS(M) = \mathbb{F}_{c \times 1}$, we have $CS(AM) = CS(A)$.
Prove that $RS(A) = \{Y^T: Y \in CS(A^T)\}$. [Note: this problem asks you to verify a set equality. Approach this by giving a "dual containment" argument.]
Consider the matrix $A$ $$A = \left[\begin{array}{rrrr}5&2&9&11\\2&1&4&5\\3&2&7&9\\1&-1&-1&-2\end{array}\right].$$
1. Determine the set of vectors in $NS(A)$. [Hint: explain why this is the same as finding all solutions to the system $AX = 0$. Then, find all solutions to the system.]
2. Determine the set of vectors in $CS(A)$. [Hint: determine how this question is related to problem 3 from assignment 2. Then adapt the technique for answering that problem to provide an answer for this problem. There will be fractions!]
As ever, be sure to justify any assertions you make.

Here are some other problems you should work through, but I won't be submitted as a part of your problem set.

Let $A$ be the matrix from problem 3 above. Determine the set of vectors in $RS(A)$. [Consider problem 2 from this assignment as well as your approach to 3(b)]

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

Suppose that $A \in \mathbb{F}_{n \times n}$ is invertible. Prove that for a collection $\{v_1,\cdots,v_k\} \subseteq \mathbb{F}_{n \times 1}$, we have that $\{v_1,\cdots,v_k\}$ is linearly independent if and only if $\{Av_1,\cdots,Av_k\}$ is linearly independent.
Suppose that $\{v,w,z\}$ are independent elements in some vector space $V$. Prove that $\{v+w,w+z,v+z\}$ is an independent set.
Consider the matrix $A$ $$A = \left[\begin{array}{rrrr}5&2&9&11\\2&1&4&5\\3&2&7&9\\1&-1&-1&-2\end{array}\right].$$
1. Determine a basis for $NS(A)$.
2. Determine a basis for $CS(A)$.
As ever, be sure to justify any assertions you make.

Here are some other problems you should work through, but won't be submitted as a part of your problem set.

Suppose that $A \in \mathbb{F}_{r \times c}$ and that $M \in \mathbb{F}_{\ell \times c}$. In class before fall break I asserted that $NS(A) = NS(MA)$ if and only if $NS(M) = \{0\}$. It turns out this is wrong! Instead, prove that $NS(A) = NS(MA)$ if and only if $NS(A) \cap NS(M) = \{0\}$, where here the ``$\cap$" symbol denotes the intersection of these two sets.
[Note: It is still true that if $NS(M) = \{0\}$, then this implies $NS(A) = NS(MA)$. The issue is that the equality $NS(A) = NS(MA)$ does not necessarily imply $NS(M) = \{0\}$.]
Suppose that $W_1,W_2$ are subspaces of a vector space $V$. Prove that $$W_1+W_2 = \{w_1+w_2: w_1 \in W_1 \text{ and }w_2 \in W_2\}$$ is a subspace of $V$.
Prove that $RS(A) = RS(MA)$ if and only if $RS(M)+\widetilde{NS}(A) = \mathbb{F}_{r \times 1}$, where $\widetilde{NS}(A) = \{Z \in \mathbb{F}_{1 \times r}: ZA = 0\}$.

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

Suppose that $W_1$ and $W_2$ are both subspaces of a vector space $V$. Furthermore, suppose that $W_1 \subseteq W_2$. Prove that $\dim(W_1) \leq \dim(W_2)$.
If $W$ is a subspace of $V$ for which $\dim(W) = \dim(V)$, prove that $W = V$.
A matrix $A \in \mathbb{F}_{3 \times 3}$ is called symmetric if $A = A^T$.
1. Prove that $S = \{A \in \mathbb{F}_{3 \times 3}: A \text{ is symmetric}\}$ is a subspace of $\mathbb{F}_{3 \times 3}$.
2. Give a basis for $S$. (Be sure to prove your claim.)
3. What is $\dim(S)$?

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

You should work on this problem by yourself, or with the assistance of the instructor.

Let $\mathbb{F}_n[x] = \{a_0 + a_1 x +\cdots+a_nx^n : a_0,a_1,\cdots,a_n \in \mathbb{F}\}$. Give a basis for $\mathbb{F}_n[x]$, and then use this to give $\dim(\mathbb{F}_n[x])$.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

Suppose that $\dim(V) = n$ and that $\{v_1,\cdots,v_n\}$ is a linearly independent set. Prove that $\{v_1,\cdots,v_n\}$ is a basis. [Note: this is an incredibly powerful theorem, because it tells you that if you already know the dimension of a space, you have a "short cut" for verifying that a particular set is a basis. Assuming the set has the right number of elements, you can get away with checking only linear independence.]
Suppose that $W$ and $V$ are subspaces of a vector space $Z$ which satisfy $W \cap V = \{0_Z\}$. (This simply means that the only element which is in both $W$ and $V$ is the zero vector from $Z$.) Prove that $\dim(W+V) = \dim(W)+\dim(V)$. [Note: When we write $W+V$, we mean the subspace defined in the optional problems of assignment 8.]
Suppose that $A$ and $B$ are matrices so that $AB$ is defined. Prove that $\text{rk}(AB) \leq \min\{\text{rk}(A),\text{rk}(B)\}.$

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

If $A \in \mathbb{F}_{r \times c}$ is given, then we can view "multiplication by $A$" as a function whose domain is $\mathbb{F}_{c \times 1}$ and whose codomain is $\mathbb{F}_{r \times 1}$. After all, if we take a given $X \in \mathbb{F}_{c \times 1}$, then the result of multiplying $A$ against $X$ is a vector $AX \in \mathbb{F}_{r \times 1}$. For simplicity in thinking of matrix multiplication as a function, let's write $f_A:\mathbb{F}_{c \times 1} \to \mathbb{F}_{r \times 1}$ to be the function which sends any given $X \in \mathbb{F}_{c \times 1}$ to $AX \in \mathbb{F}_{r \times 1}$: $$f_A:\mathbb{F}_{c \times 1} \to \mathbb{F}_{r \times 1} \text{ is defined by }f_A(X) = AX.$$
1. Prove that $f_A$ is injective if and only if $NS(A) = \{0\}$.
2. Prove that $f_A$ is surjective if and only if $CS(A) = \mathbb{F}_{r \times 1}$.
3. Prove that $f_A$ is bijective if and only if $A$ is invertible.
Suppose that $W$ is a subspace of $\mathbb{F}_{5\times 1}$, and that the following set is a basis for $W$: $$\mathbb{B} = \left\{\left(\begin{array}{r}1\\-1\\2\\0\\-2\end{array}\right),\left(\begin{array}{r}2\\1\\4\\0\\3\end{array}\right),\left(\begin{array}{r}0\\2\\1\\0\\-1\end{array}\right),\left(\begin{array}{r}4\\4\\4\\0\\4\end{array}\right)\right\}.$$

Compute $\displaystyle \text{Crd}_{\mathbb{B}}\left(\left(\begin{array}{r}-11\\66\\22\\0\\-11\end{array}\right)\right).$
($\star$) What vector $w \in W$ has $\text{Crd}_{\mathbb{B}}(w) = \left(\begin{array}{r}2\\-1\\1\\3\end{array}\right)$?

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

Suppose that $\dim(V) = n$ and that $\{v_1,\cdots,v_n\}$ satisfies $\text{span}\{v_1,\cdots,v_n\} = V$. Prove that $\{v_1,\cdots,v_n\}$ is a basis. [Note: this is an incredibly powerful theorem, because it tells you that if you already know the dimension of a space, you have a "short cut" for verifying that a particular set is a basis. Assuming the set has the right number of elements, you can get away with checking only that it spans the space.]

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

For each of the following statements, determine whether it is true or false. Prove your assertion. [Hint: One is true and the other is false. Also: the negation of each of these statements is a "there exists" statement. Hence to prove that a given statement is false, you need to provide a specific counterexample. You might consider using bean diagrams for your provided counterexample.]

For any $f:A\to B$ and $g:B \to C$, if $g\circ f$ is injective, then $g$ is injective.
For any $f:A \to B$ and $g: B \to C$, if $g \circ f$ is injective, then $f$ is injective.

Suppose that $U,V,W$ are all vector spaces over $\mathbb{F}$, where we use $+$ and $\cdot$ for the addition and scaling operations on $U$, we use $\oplus$ and $\odot$ for the addition and scaling operations on $V$, and we write $\boxplus$ and $\boxdot$ for the addition and scaling operations in $W$. Suppose that $f:U \to V$ and $g:V \to W$ are both functions that preserve the relevant addition and scaling operations; for instance, this means (among other things) that for all $u_1,u_2 \in U$ we have $$f(u_1+u_2) = f(u_1)\oplus f(u_2).$$ Prove that $g\circ f:U \to W$ preserves addition and scaling operations.
Let $\{w_1,w_2,w_3\}$ be a basis for a vector space $W$. It is a fact (that you don't have to prove) that the following sets are also bases for $W$: \begin{align*} \mathbb{B}&=\{w_1+2w_2-w_3,2w_1+5w_2-2w_3,w_1+w_2\}\\ \mathbb{D} &= \{w_1+w_2+2w_3,-w_1-2w_2,2w_1+5w_2+5w_3\} \end{align*} Compute the matrix $P$ which has the property that for all $w \in W$, we get $$P\text{Crd}_\mathbb{B}(w)= \text{Crd}_\mathbb{D}(w).$$ Then compute the matrix $Q$ which has the property that for all $w \in W$ we get $$Q\text{Crd}_\mathbb{D}(w) = \text{Crd}_{\mathbb{B}}(w).$$ As ever, justify your assertions.
[Hint: suppose we write $\mathbb{B} = \{b_1,b_2,b_3\}$ for convenience. How are the vectors $P\text{Crd}_\mathbb{B}(b_i)$ related to the columns of $P$?]

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

Suppose $V$ and $W$ are vector spaces, with operations $+$ and $\cdot$ for $V$ and operations $\oplus$ and $\odot$ for $W$. Suppose that $f:V \to W$ preserves both addition and scaling. Prove that
1. $f$ sends the neutral element in $V$ to the neutral element in $W$; and
2. For any $v \in V$, the function $f$ sends the additive inverse of $v$ in $V$ to the additive inverse of $f(v)$ in $W$.
[Hint: how can you check that a given element is the neutral element? how can you check if a particular vector is the additive inverse of some other vector?]

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

Suppose that $T:W \to V$ is an isomorphism, and let $U$ be any subspace. Prove that the function $\Phi:\mathcal{L}(V,U) \to \mathcal{L}(W,U)$ given by $\Phi(S) = S \circ T$ is an isomorphism.
Suppose that $T \in \mathcal{L}(V,W)$ and $S \in \mathcal{L}(W,U)$. Prove that $\ker(T) \subseteq \ker(S \circ T)$, and that $\text{im}(S\circ T) \subseteq \text{im}(S)$.
Suppose that $\dim(V) = 3$ and $T \in \mathcal{L}(V,V)$. Suppose further that there exists some $v \in V$ so that $(T \circ T)(v) \neq \mathbf{0}$ and yet $(T\circ T \circ T)(v) = 0_V$.
1. Prove that $\mathbb{B} = \{v,T(v),T(T(v))\}$ is a basis for $V$.
2. Compute $\text{Mtx}_{\mathbb{B},\mathbb{B}}(T)$.

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

Let $\{\mathbf{w}_0,\cdots,\mathbf{w}_5\}$ be linearly independent vectors in $\mathbb{R}^n$, and define \begin{align*}W_3 &= \text{span}\{\mathbf{w}_0,\mathbf{w}_1,\mathbf{w}_2,\mathbf{w}_3\} \\W_4 &= \text{span}\{\mathbf{w}_0,\mathbf{w}_1,\mathbf{w}_2,\mathbf{w}_3,\mathbf{w}_4\} \\W_5 &= \text{span}\{\mathbf{w}_0,\mathbf{w}_1,\mathbf{w}_2,\mathbf{w}_3,\mathbf{w}_3,\mathbf{w}_5\}. \end{align*} Define functions $T \in \mathcal{L}(W_5,W_4)$, $S \in \mathcal{L}(W_4,W_3)$ and $R \in \mathcal{L}(W_5,W_3)$ by \begin{align*} T(c_0\mathbf{w}_0 + c_1 \mathbf{w}_1 + c_2\mathbf{w}_2+c_3\mathbf{w_3}+c_4\mathbf{w}_4+c_5\mathbf{w}_5) &= c_1 \mathbf{w}_0 + 2c_2\mathbf{w}_1+3c_3\mathbf{w_2}+4c_4\mathbf{w}_3+5c_5\mathbf{w}_4\\ S(c_0\mathbf{w}_0 + c_1 \mathbf{w}_1 + c_2\mathbf{w}_2+c_3\mathbf{w_3}+c_4\mathbf{w}_4) &= c_1 \mathbf{w}_0 + 2c_2\mathbf{w}_1+3c_3\mathbf{w_2}+4c_4\mathbf{w}_3\\ R(c_0\mathbf{w}_0 + c_1 \mathbf{w}_1 + c_2\mathbf{w}_2+c_3\mathbf{w_3}+c_4\mathbf{w}_4+c_5\mathbf{w}_5) &= 2c_2\mathbf{w}_0+6c_3\mathbf{w_1}+12c_4\mathbf{w}_2+20c_5\mathbf{w}_3. \end{align*}
1. It is a fact (that you don't have to prove) that the following sets are bases for $W_5$ and $W_3$ (respectively): \begin{align*} \mathbb{B} &= \{\mathbf{w}_0+\mathbf{w}_2,\mathbf{w}_1+\mathbf{w}_3,\mathbf{w}_2+\mathbf{w}_4,\mathbf{w}_3+\mathbf{w}_5,\mathbf{w}_4+\mathbf{w}_0,\mathbf{w}_5+\mathbf{w}_1\}\\ \mathbb{D} &= \{\mathbf{w}_0,\mathbf{w}_0+\mathbf{w}_1,\mathbf{w}_0+\mathbf{w}_1+\mathbf{w}_2,\mathbf{w}_0+\mathbf{w}_1+\mathbf{w}_2+\mathbf{w}_3\}. \end{align*} Compute $\text{Mtx}_{\mathbb{D},\mathbb{B}}(R)$.
2. Use your answer to calculate $\text{Crd}_\mathbb{D}\left(R((\mathbf{w}_0+\mathbf{w}_2)+(\mathbf{w}_1+\mathbf{w}_3)-(\mathbf{w}_3+\mathbf{w}_5))\right)$ via a matrix product.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

Define $T:\mathbb{F}_2[x] \to \mathbb{F}_3[x]$ and $S:\mathbb{F}_3[x] \to \mathbb{F}_4[x]$ to be the functions which take a polynomial $f(x)$ and return the antiderivative $\int f(x)~dx$ whose constant term is zero. (So, for instance, $T(1+x-x^2) = x + \frac{1}{2}x^2 - \frac{1}{3}x^3$.) Let $\mathbb{B} = \{1+x,x+x^2,1+x+x^2\}$, $\mathbb{D} = \{1,1+x,1+x+x^2,1+x+x^2+x^3\}$ and $\mathbb{E} = \{1,x,x^2,x^3,x^4\}$; it is a fact that these are bases of (respectively) $\mathbb{F}_2[x],\mathbb{F}_3[x]$ and $\mathbb{F}_4[x]$.
1. Compute the matrix representations for $T$, $S$ and $S \circ T$ relative to these bases.
2. Verify (by direct computation) that the matrices you calculated in the previous part satisfy $$\text{Mtx}_{\mathbb{E},\mathbb{B}}(S\circ T) = \text{Mtx}_{\mathbb{E},\mathbb{D}}(S)\text{Mtx}_{\mathbb{D},\mathbb{B}}(T).$$
Prove that for any $T \in \mathcal{L}(V,W)$ and bases $\mathbb{B} = \{v_1,\cdots,v_n\}$ of $V$ and $\mathbb{D} = \{w_1,\cdots,w_m\}$ of $W$ we have $$NS(\text{Mtx}_{\mathbb{D},\mathbb{B}}(T)) = \{\text{Crd}_\mathbb{B}(v): v \in \ker(T)\}.$$

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

I'm giving you a few extra days on this pset since I didn't post it until later than expected. You will still have another set (Assignment 16) due on Friday, December 1 as well.

If $A \in \mathbb{F}_{n \times n}$ is a matrix, then an eigenvector for $A$ is a vector $X \in \mathbb{F}_{n \times 1}$ for which there exists some $\lambda \in \mathbb{F}$ with $AX = \lambda X$. A scalar $\lambda \in \mathbb{F}$ is called an eigenvalue for $A$ if there exists some nonzero $X \in \mathbb{F}_{n \times 1}$ with $AX = \lambda X$. [These are the same definitions we gave for linear transformations, but now adapted for matrices.
1. Prove the following assertion or given an explicit counterexample: if $A$ and $B$ are similar matrices in $\mathbb{F}_{n \times n}$ and $X$ is an eigenvector for $A$, then $X$ is an eigenvector for $B$.
2. Prove that if $A$ and $B$ are similar matrices in $\mathbb{F}_{n \times n}$ and $\lambda$ is an eigenvalue for $A$, then $\lambda$ is an eigenvalue of $B$.
Suppose that $T \in \mathcal{L}(V,V)$, and that $v_1,\cdots,v_n \in V$ are all NONZERO eigenvectors with corresponding eigenvalues $\lambda_1,\cdots,\lambda_n$, and furthermore that $\lambda_i \neq \lambda_j$ for all $i \neq j$. Prove that $\{v_1,\cdots,v_n\}$ are independent. [Hint: Consider $(T-\lambda_1 \text{id}_V)\circ\cdots\circ(T-\lambda_{i-1} \text{id}_V)\circ(T-\lambda_{i+1} \text{id}_V)\circ\cdots\circ(T-\lambda_n\text{id}_V).$]

Here are the Solutions.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects.

This assignment is optional in the sense that if you choose not to submit it, it will not be factored into your overall homework grade, nor will it count as your drop grade. Even stronger: if you submit it and the grade doesn't help your overall homework average, I'll drop this assignment without counting it as your drop grade.

Without relying on the determinant, prove that the derivative operator $D:\mathbb{R}_n[x] \to \mathbb{R}_n[x]$ has only $0$ as an eigenvalue. Use this to argue that $D$ is not diagonalizable when $n>0$. [Hint: for the first question, if $p(x) = a_0 + a_1x + \cdots + a_nx^n \in \mathbb{R}_n[x]$ is given, let $m$ be as large as possible so that $a_m \neq 0$. Assume that $D[p(x)] = \lambda p(x)$ for $\lambda \neq 0$ and reach a contradiction.]
Suppose that $\dim(V) = n$ and $T \in \mathcal{L}(V,V)$ is a transformation which has $n$ distinct eigenvalues $\lambda_1,\cdots,\lambda_n \in \mathbb{F}$. Prove that $T$ is diagonalizable.

Here are the Solutions.

Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat. The overall guiding principle in your writing is to remember that your work is meant to be read by a a skeptical peer; your job is to write a (logically) convincing argument to this audience.

Responses will be graded on both mathematical correctness and quality of exposition. Your work will be submitted in a folder separate from the regular homework folder, so make sure this solution is written independent of your regular homework set.

Suppose that $\{v_1,v_2,v_3\}$ is a basis for $V$, and that $T$ is a linear transformation defined by $$T(v_1) = v_1+v_2 \quad \quad T(v_2) = v_1+v_3 \quad \quad T(v_3) = v_2+v_3.$$ It is a fact (that you don't have to prove) that the eigenvalues for $T$ are precisely $1,-1$ and $2$. Use this information to find a basis $\mathbb{D}$ for $V$ that is an eigenbasis for $V$, and also provide $\text{Mtx}_{\mathbb{D},\mathbb{D}}(T)$.

This is not an assignment. I'm providing these questions (and their solutions) so that you'll have some problems involving determinants and eigenvectors to work through.

Use row reduction to compute the determinants of the following matrices: $$A = \left[\begin{array}{rrrr}1&1&1&1\\1&1&4&4\\1&-1&2&-2\\1&-1&8&-8\end{array}\right] \quad \quad B = \left[\begin{array}{rrrrr}0&0&0&0&2\\1&0&0&0&3\\0&1&0&0&4\\0&0&1&0&5\\0&0&0&1&6\end{array}\right].$$
For the following matrices, find all eigenvalues (assuming that $\mathbb{F} = \mathbb{R}$). Then for each eigenvalue, compute both the algebraic and geometric multiplicities. Find a basis for each eigenspace. Finally, determine if the matrix is diagonalizable:$$A = \left[\begin{array}{rrr}1&1&0\\0&-1&-1\\2&2&0\end{array}\right] \quad \quad B = \left[\begin{array}{rrrr}0&0&0&0\\0&1&0&1\\0&0&0&0\\0&0&0&1\end{array}\right].$$
Prove that for any $A \in \mathbb{F}_{n \times n}$ we have $\det(A) = \det(A^T)$.
Prove that similar matrices have the same characteristic polynomial.

Here are the Solutions.

Homework Assignments

assignments