$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

# Section4Proof Portfolio

Your proof portfolio is a set of conceptual problems and proofs that you'll write and revise throughout the semester. Choose your problems from the following list, typesetting your solutions in Overleaf. Include both a PDF copy of your entire proof portfolio and its Overleaf read-and-edit link with each course portfolio submission.

The exercises to submit on each portfolio's due date must be chosen from among the following. You are free to add to these during the revision process if you wish, but must on each due date have at least 3-5 of the listed exercises in your portfolio:

• Portfolio 1: Exercises 1-8
• Portfolio 2: Exercises 9-16
• Portfolio 3: Exercises 17-24
• Portfolio 4: Exercises 25-32
• Portfolio 5: Exercises 33-40

To get started with writing your document in Overleaf, the brief video tutorial below can help. Additional tutorials are available here: https://www.overleaf.com/help/category/video_tutorials

## Section4.1Exercises

###### 1

Let $(x_1,y_1)$ and $(x_2,y_2)$ both be solutions of the equation

\begin{gather} 4x - 5y = 0.\tag{4.1.1} \end{gather}
1. Prove that $(x_1+x_2,y_1+y_2)$ is also a solution of (4.1.1).
2. If $c\in \mathbb{R}$ is any real number, prove that $(cx_1,cy_1)$ is also a solution of (4.1.1).
###### 2

Let $(x_1,y_1)$ and $(x_2,y_2)$ both be solutions of the equation

\begin{gather} 4x - 5y = 12.\tag{4.1.2} \end{gather}
1. Prove that $(x_1+x_2,y_1+y_2)$ is not a solution of (4.1.2).
2. Assume $c\in \mathbb{R}$ is a real number. Prove that if $(cx_1,cy_1)$ is a solution of (4.1.2), then we must have $c=1\text{.}$
3. Comparing this problem with the previous, explain: What is the most important difference between (4.1.1) and (4.1.2) that gives rise to these different conclusions? Why?
###### 3

Consider the equation

\begin{gather} x^2 + y = 16.\tag{4.1.3} \end{gather}
1. Let $(x_1,y_1)=(-4,0)$ and $(x_2,y_2) = (2,12)\text{.}$ Prove that $(x_1,y_1)$ and $(x_2,y_2)$ are both solutions of (4.1.3). Also, prove that $(x_1+x_2,y_1+y_2)$ is a solution of (4.1.3).
2. Prove or disprove: For all $x_1,x_2,y_1,y_2\text{,}$ if $(x_1,y_1)$ and $(x_2,y_2)$ are both solutions of (4.1.3), then $(x_1+x_2,y_1+y_2)$ is a solution of (4.1.3).
###### 4

Supply an argument in favor of the following statement: The equation

\begin{equation*} x^3-3x^2y+3xy^2-y^3=0 \end{equation*}

is a linear equation.

Hint

It'll take some "rainy-day algebra," but can you verify the conclusions of Exercise 4.1.1 for this equation?

###### 5

Prove by examples that a linear system of 4 equations and 3 unknowns may have any of the following:

1. No solution.
2. A unique solution.
3. Infinitely many solutions.
Hint

Begin by writing the reduced row-echelon form for each case. You can then use row-operations to "scramble" the system into something more interesting.

###### 6

Prove or disprove that a linear system of 3 equations and 4 unknowns may have each of the following:

1. No solution.
2. A unique solution.
3. Infinitely many solutions.
Hint

Think carefully: When is a single example enough? And when do you need a universal argument?

###### 7

Prove that if a linear system of equations has a unique solution, then it has no free variables.

###### 8

Consider a linear system of $m$ equations and $n$ unknowns.

1. Complete the sentence, and provide a convincing explanation: If this system has $b$ basic variables, then \begin{equation*} b \leq \underline{\qquad}. \end{equation*}
2. Complete the sentence, and provide a convincing explanation: If this system has $f$ free variables, then \begin{equation*} f = \underline{\qquad}. \end{equation*} (Feel 'free' to use some of $m,n,$ and/or $b$ in your equation.)
3. Prove that, if $m\gt n\text{,}$ then this system cannot have a unique solution.
Hint

(a) Your answer might depend on which of $m$ or $n$ is greater. (c) This is a quick proof if you can unite your answers to parts (a)-(b) with Exercise 4.1.7. Don't reinvent the wheel if you've proven those results first!

###### 9

Let ${\bf v_1}, {\bf v_2}, {\bf v_3}$ be arbitrary vectors in $\mathbb{R}^3\text{.}$

1. Prove that there is always a linear combination of ${\bf v}_1, {\bf v}_2, {\bf v}_3$ that is equal to the zero vector ${\bf 0} = (0,0,0)\text{.}$
2. Assume that there is more than one different linear combination that satisfies part (a). Prove that in this case, there must be infinitely many linear combinations of ${\bf v}_1, {\bf v}_2, {\bf v}_3$ that equal the zero vector.
3. True or false, and explain: These results will still hold if the three vectors live in $\mathbb{R}^n$ for any $n \geq 1\text{.}$
Hint

There is a way to do part (b) very quickly, if you can establish that the answer to this question is really the solution of some linear system! (Why? What do we know about how many solutions a linear system may have?)

###### 10

Suppose ${\bf v}_1,{\bf v}_2,\ldots,{\bf v}_n \in \mathbb{R}^m$ is a collection of $m$-dimensional vectors, and suppose that the matrix

\begin{equation*} \left[ \begin{array}{cccc} \vdots \amp \vdots \amp\amp \vdots \\ {\bf v}_1 \amp {\bf v}_2 \amp \cdots \amp {\bf v}_n\\ \vdots \amp \vdots \amp \amp \vdots \end{array}\right] \end{equation*}

has a pivot position in every row.

1. Let ${\bf b} \in \mathbb{R}^m$ be an arbitrary $m$-dimensional vector. Prove that ${\bf b}$ can be written as a linear combination of the vectors ${\bf v}_1,{\bf v}_2,\ldots,{\bf v}_n\text{.}$
2. Prove that, if $m\gt n\text{,}$ the conclusion of part (a) is false.
Hint

Part (a) makes a universal claim ("for all ${\bf b\text{,}$ we have...") and so it must be proven in generality. By contrast, part (b) asks you to disprove a universal claim ("there exists ${\bf b}$ such that we don't have..."). So you can prove (b) with a specific example if you wish. Just be sure you explain what it is about your example that makes it work.

###### 11

Let $A$ be an $m\times n$ matrix and ${\bf b} \in \mathbb{R}^m$ be a vector.

1. Prove that if ${\bf x}_1$ and ${\bf x}_2$ are both solutions of the equation $A{\bf x}={\bf b}\text{,}$ then the vector \begin{equation*} {\bf v} = {\bf x}_1-{\bf x}_2 \end{equation*} is a solution of the equation $A{\bf x} = {\bf 0}.$
2. Assume that the equation $A{\bf x} = {\bf b}$ has a unique solution. Use part (a) to determine the solution set of the equation $A{\bf x} = {\bf 0}.$
3. Conversely, suppose ${\bf x}$ is a vector satisfying $A{\bf x} = {\bf b}\text{,}$ and ${\bf n} \neq {\bf 0}$ is a nonzero vector such that $A{\bf n} = {\bf 0}.$ Prove that \begin{equation*} {\bf v} = {\bf x} + {\bf n} \end{equation*} also satisfies the equation $A{\bf x} = {\bf b}.$
Hint

If you find yourself writing down any actual matrices or even coordinate components, you're probably working too hard. These arguments need only the linearity properties of matrix multiplication to make them work.

###### 12

Let $A$ be an $n\times n$ square matrix. Suppose that ${\bf v}_1, {\bf v}_2 \in {\mathbb R}^n$ are vectors which have the property that

\begin{gather} A{\bf v}_1 = {\bf v_1} \text{ and } A{\bf v}_2 = \frac12 {\bf v}_2.\tag{4.1.4} \end{gather}

Let ${\bf x} \in {\rm span}\{{\bf v}_1,{\bf v}_2\}.$ Prove that, in the limit as $n\to\infty\text{,}$

\begin{equation*} \lim_{n\to\infty} A^n\, {\bf x} = {\bf v}_1. \end{equation*}
Hint

Get a feel for this problem by applying the definition of span to the vector ${\bf x}\text{,}$ then multiplying the resulting expression by the matrix $A\text{.}$ Use (4.1.4) to simplify. Then, multiply that result by $A$ again and repeat. What happens?

###### 13

Let $A$ be an arbitrary $3\times 4$ matrix and $B$ be an arbitrary $4\times 5$ matrix. The dimensions of these matrices make it possible to form the product matrix $P = AB\text{.}$

1. What are the dimensions of the product matrix $P\text{?}$
2. Prove that if the columns of $A$ span $\mathbb{R}^3$ and the columns of $B$ span $\mathbb{R}^4\text{,}$ then we can guarantee the columns of $P$ span $\mathbb{R}^3\text{.}$
Hint

"Do the columns span the whole codomain" is really a question about "is the linear system always consistent?" Try treating the equation $P{\bf x} = {\bf b}$ in two steps:

\begin{align*} A\, (\underbrace{B{\bf x}}_{\bf y}) \amp = {\bf b} \amp\amp \text{can we always solve for y? why?}\\ B{\bf x} \amp = {\bf y} \amp\amp \text{can we always solve for x? why?} \end{align*}
###### 14

Let ${\bf v}_1,{\bf v}_2,{\bf w}$ be a set of vectors that is linearly dependent.

1. Prove that ${\bf w}$ can be written as a linear combination of ${\bf v}_1,{\bf v}_2\text{.}$
2. Let $S = {\rm span}\{{\bf v}_1,{\bf v}_2,{\bf w}\}$ and $T = {\rm span}\{{\bf v}_1,{\bf v}_2\}.$ Prove directly from the definition of span that, as sets, $S = T\text{.}$
Hint

Remember that if $X,Y$ are sets, proving that $X=Y$ requires you to prove two containments:

1. $X \subset Y\text{:}$ Let $x\in X$ be arbitrarily chosen. Prove that $x \in Y.$
2. $Y \subset X\text{:}$ Let $y \in Y$ be arbitrarily chosen. Prove that $y \in X\text{.}$
###### 15

Let $A$ be an $n\times n$ square matrix, and ${\bf e}_1,{\bf e}_2,\ldots,{\bf e}_n$ be the standard vectors in $\mathbb{R}^n.$

Prove that if $A{\bf e}_1, A{\bf e}_2,\ldots, A{\bf e}_n$ are linearly independent, then the equation

\begin{equation*} A{\bf x} = {\bf b} \end{equation*}

has a unique solution for all ${\bf b}.$

Hint

What do you get when you multiply any matrix by the first standard vector ${\bf e}_1\text{?}$ Try it. Does that always work? What does that tell you here?

###### 16

Let $A$ be a $3\times 4$ matrix and $B$ be a $4\times 5$ matrix. Suppose that the product

\begin{equation*} P = AB = O \end{equation*}

is a matrix whose entries are all zero.

1. Prove that either (or both) matrix $A$ and/or $B$ must be "missing a pivot," that is, has at least one row without a pivot.
2. For the matrix \begin{equation*} A = \left[ \begin{array}{rrrr} 1\amp 0 \amp -1 \amp 1\\ 0\amp 1\amp 1\amp -2\\ 1\amp -1\amp 2\amp 0\end{array}\right]\text{,} \end{equation*} find a (nonzero!) $4\times 5$ matrix $B$ for which $AB = O\text{.}$
Hint

If you proved Exercise 4.1.13, you can use the result to make part (a) very quick. In part (b) you can also use the same hint from that exercise:

\begin{align*} A\, (\underbrace{B{\bf x}}_{\bf y}) \amp = 0 \amp\amp \text{which y will satisfy this?}\\ B{\bf x} \amp = {\bf y} \amp\amp \text{how to ensure that Bx is always one of those y's?} \end{align*}