Homework 2

1. Every Echelon Form
2. General Form Solutions
3. Integer Solutions
4. Changing Free Variables
- 4.1. (5 points)
- 4.2. (5 points)
5. Back-Substitution (Programming)

The following assignment is due Thursday 9/19 by 11:59 PM. You should submit all your written solutions to Gradescope as a single pdf. Follow the instructions in the programming problem for code solutions.

Your solutions must be exceptionally neat and the final answer in your solution to each problem must be abundantly clear, e.g., surrounded in a very visible box. The graders have license to dock points for illegible or unclear solutions.
For the written part, choose the correct pages corresponding to each problem in Gradescope. Note that Gradescope registers your submission as soon as you submit it, so you don't need to rush to choose the pages. You will receive no credit if you do not choose the correct pages, no exceptions.

1. Every Echelon Form

(10 points) Write down every \(3 \times 3\) RREF matrix with at least two pivot positions whose entries are either \(0\) or \(1\).

2. General Form Solutions

For each of the following linear systems, write down

the RREF of its augmented matrix
its solution in general form (if the system has no solution then write down no solution)

You do not need to show your work. Just write the above information. Hint: As usual, consider using a.rref()

2.1. (3 Points)

\begin{align*} -x - 2y - z &= -4 \\ x + 2y &= 3 \\ -2x -4y + z &= -7 \end{align*}

2.2. (3 Points)

\begin{align*} 88x_1 + 61x_2 + 8x_3 + 61 x_4 &= -68 \\ 37x_1 + 14x_2 + 72x_3 + 41 x_4 &= -460 \\ 57x_1 + 59x_2 + 69x_3 + 75x_4 &= -333 \\ 92 x_1 + 60x_2 + 28x_3 + 72x_4 &= -192 \end{align*}

2.3. (3 Points)

\begin{align*} x_2 + x_3 + x_4 + 3x_5 - x_6 + 2x_7 &= 34 \\ x_3 - x_4 + 4x_5 &= -14 \\ 2x_2 - 4x_3 + 8x_4 - 18x_5 - x_6 &= 110 \\ 3x_3 - 3x_4 + 12 x_5 + 2x_7 &= -18 \\ x_2 + 4x_3 - 2x_4 + 15x_5 - x_6 + 7x_7 &= 52 \end{align*}

2.4. (3 Points)

\begin{align*} 8x_1 + 3x_2 - 3x_3 &= -4 \\ -3x_1 + 8x_2 + 5x_3 &= -4 \\ 6x_1 + 7x_2 - 3x_3 &= -3 \\ 8x_1 + x_2 - x_3 &= -4 \end{align*}

3. Integer Solutions

(10 points) Find a solution to the linear system below with the following properties:

The solution consists entirely of integer values
The values in the solution are relatively prime, i.e., it's not possible to divide the solution by a number to get another integer solution. So \((2, 4, 6)\) does not satisfy this property but \((1, 2, 3)\) does.

In addition to the solution, you must write down the RREF of the augmented matrix of this system, but otherwise, you don't have to show your work.¹

\begin{align*} 4x_2 + x_3 &= 16 \\ 9x_1 - 20x_2 - 8x_3 &= -71 \\ 3x_1 - 8x_2 - 3x_3 &= -29 \end{align*}

4. Changing Free Variables

Consider the following general form solution

\begin{align*} x_1 &= 3x_2 - 2x_3 \\ x_2 &\quad \text{is free} \\ x_3 &\quad \text{is free} \\ x_4 &= 2 + x_3 \end{align*}

4.1. (5 points)

Write down another general form solution which describes the same solution set, but for which \(x_3\) is basic and \(x_4\) is free.

4.2. (5 points)

Write down a RREF matrix which yields the general form solution you wrote down in the previous part.

5. Back-Substitution (Programming)

(20 points) In this programming exercise, you'll be implementing the back-substitution part of Gaussian elimination. You'll also be building some predicates for checking if a matrix is in (row-reduced) echelon form. The primary motivation of this exercise is to get used to manipulating SymPy matrices, particularly via array slicing.

You're given starter code in the file hw02.py. Please do not change the name of this file when you submit it, nor the names of functions included in the starter code. You may add your own functions, but you are not expected to. You're only required to fill in the TODO items in the starter code.

You're required to implement the following functions:

leading_entry_index(a) given a \(1 \times n\) SymPy matrix a, return the index of the first nonzero entry of a. Return None otherwise.
is_echelon(a) given a SymPy matrix a, return True if a is in echelon form and return False otherwise.
is_rref(a) given a SymPy matrix a, return True if a is in reduced echelon from and return False otherwise.
back_sub(a) given a SymPy matrix a in echelon form, update the matrix a so that it is in reduced echelon form.

Some guidelines:

Work incrementally. Don't try to implement the entire program and then debug it once you're done.
Take a look at the SymPy library for matrices. There are a lot of useful functions there, we won't get to all of them. The following may be useful for this exercise:
- sympy.zeros(i, j)
- a.is_zero_matrix
- a.row(i) and a[i,:]
- a.rows
- a.col(j) and a[:,j]
- a.cols

You'll upload the single python file hw02.py to Gradescope with your implementations of TODO items in the code. You won't have access to the tests on Gradescope, but we'll provide a subset of the unit tests which you can run yourself in a directory called tests. You can run python -m unittest to run these tests.

Footnotes:

This is the process we would use to find a valid solution to the problem of balancing chemical equations.