Math 260, Fall 2018, Assignment 2

No doubt many people feel that the inclusion of mathematics among the arts is unwarranted. The strongest objection is that mathematics has no emotional import. Of course this argument discounts the feelings of dislike and revulsion that mathematics induces....

- Morris Kline, Mathematics in Western Culture

Read:

1. Section 1.2.
2. Section 1.3.

Carefully define the following terms, then give one example and one non-example of each:

1. Augmented matrix (of a system of linear equations).
2. Elementary row operation.
3. Row-equivalent (matrices).
4. Reduced row-echelon matrix.
5. Pivot (of a reduced row-echelon matrix).
6. Rank (of a matrix; note that we did not discuss this in class, so you will need to look in the book for the definition).
7. Reduced row-echelon form (of a given matrix $A$; also known as $\mathrm{rref}(A)$).

Carefully describe the following algorithms:

1. Gauss-Jordan elimination algorithm.

Carefully state the following theorems (you do not need to prove them):

1. Theorem relating the solution-sets of linear systems represented by row-equivalent matrices.
2. Theorem concerning the number of reduced row-echelon matrices to which a given matrix is row-equivalent.

Solve the following problems:

1. Section 1.2, problems 1, 5, 7, 9, 11, 18, 19, 21, and 22.
2. Section 1.3, problems 1, 2, and 3.

--------------------End of assignment--------------------

Solutions:

Definitions:

1. The augmented matrix of the $n\times m$ linear system $$\begin{align*}a_{1,1}x_1+\dots+a_{1,m}x_m&=b_1\\&\vdots\\a_{n,1}x_1+\dots+a_{n,m}x_m&=b_n\end{align*}$$ is the $n\times (m+1)$ matrix $$\begin{bmatrix}a_{1,1}&\dots&a_{1,m}&b_1\\\vdots&&\vdots&\vdots\\a_{n,1}&\dots&a_{n,m}&b_n\end{bmatrix}.$$
2. An elementary row operation on a matrix $M$ is one of the following: (i) a single row of $M$ is multiplied by a fixed non-zero constant, (ii) some multiple of one row of $M$ is added to another row, or (iii) two rows of $M$ are swapped.
3. Two matrices $M$ and $N$ are said to be row-equivalent if there is some sequence of elementary row operations that transforms $M$ into $N$.
4. A matrix $M$ is said to be a reduced row-echelon matrix if (i) the first non-zero entry of any non-zero row of $M$ is a $1$ (this entry is called a leading one or pivot of $M$); (ii) if a row of $M$ contains a pivot, then every row above it contains a pivot further to the left; and (iii) if a column of $M$ contains a pivot, then every other entry of that column is zero.
5. If $M$ is a reduced row-echelon matrix, then a pivot or leading one of $M$ is the first non-zero entry of any non-zero row of $M$. (This is necessarily a $1$; see above.)
6. The rank of a matrix $M$ is the number of pivots in $\mathrm{rref}(M)$.
7. Any matrix $M$ is row-equivalent to one and only one reduced row-echelon matrix $\mathrm{rref}(M)$; this matrix is called the reduced row-echelon form of $M$.

Algorithms:

1. The Gauss-Jordan elimination algorithm takes as input an arbitrary matrix $M$, and returns the reduced row-echelon form of $M$. The algorithm is as follows:

1) Place the cursor in the upper left corner of $M$.

2) If the cursor entry is zero, and there are no non-zero entries below the cursor, then move the cursor to the right, and go to (2).

3) If the cursor entry is zero, then swap the cursor row with the first row below it having a non-zero entry in the cursor column.

4) Divide the cursor row by the cursor entry.

5) Add suitable multiples of the cursor row to all of the other rows, so that all other entries of the cursor column become zero.

6) Move the cursor down and to the right, and go to (2).

The algorithm terminates when the cursor leaves the matrix.

Theorems:

1. If two matrices are row-equivalent, then the linear systems that they represent have identical solution sets.
2. A given matrix is row-equivalent to exactly one reduced row-echelon matrix.