# HG changeset patch # User Rob Beezer # Date 1379186047 25200 # Node ID d551a87adea0696367117974db88c91dd0ee90ff # Parent 0fd66a73e66de019844b3eda078d26ec8e8d01fc "Pivot columns" over "leading 1", Chapter SLE diff --git a/changes.txt b/changes.txt --- a/changes.txt +++ b/changes.txt @@ -3,7 +3,7 @@ Edit: Minor edits in Sections WILA, SSLE, RREF, TSS, HSE, NM Edit: Extended slightly the conclusion of Theorem HSC Change: Theorem ISRN demoted to Exercise TSS.T11 - +Change: Prefer "pivot columns" over "leading 1", Chapter SLE v3.10 2013/08/20 ~~~~~~~~~~~~~~~~ diff --git a/src/section-RREF.xml b/src/section-RREF.xml --- a/src/section-RREF.xml +++ b/src/section-RREF.xml @@ -735,9 +735,9 @@
• The leftmost nonzero entry of a row is the only nonzero entry in its column.
• Consider any two different leftmost nonzero entries, one located in row $i$, column $j$ and the other located in row $s$, column $t$. If $s>i$, then $t>j$.
• -A row of only zero entries will be called a zero row and the leftmost nonzero entry of a nonzero row will be called a leading 1. The number of nonzero rows will be denoted by $r$.

+A row of only zero entries is called a zero row and the leftmost nonzero entry of a nonzero row is a leading 1. A column containing a leading 1 will be called a pivot column. The number of nonzero rows will be denoted by $r$, which is also equal to the number of leading 1's and the number of pivot columns.

-

A column containing a leading 1 will be called a pivot column. The set of column indices for all of the pivot columns will be denoted by $D=\set{d_1,\,d_2,\,d_3,\,\ldots,\,d_r}$ where +

The set of column indices for the pivot columns will be denoted by $D=\set{d_1,\,d_2,\,d_3,\,\ldots,\,d_r}$ where while the columns that are not pivot columns will be denoted as $F=\set{f_1,\,f_2,\,f_3,\,\ldots,\,f_{n-r}}$ where @@ -767,7 +767,7 @@ \end{bmatrix} -This matrix has two zero rows and three leading 1's. So $r=3$. Columns 1, 5, and 6 are pivot columns, so $D=\set{1,\,5,\,6}$ and then $F=\set{2,\,3,\,4,\,7,\,8}$.

+This matrix has two zero rows and three leading 1's. So $r=3$. Columns 1, 5, and 6 are the three pivot columns, so $D=\set{1,\,5,\,6}$ and then $F=\set{2,\,3,\,4,\,7,\,8}$.

@@ -1043,7 +1043,7 @@ -

We will now run through some examples of using these definitions and theorems to solve some systems of equations. From now on, when we have a matrix in reduced row-echelon form, we will mark the leading 1's with a small box. In your work, you can box 'em, circle 'em or write 'em in a different color just identify 'em somehow. This device will prove very useful later and is a very good habit to start developing right now.

+

We will now run through some examples of using these definitions and theorems to solve some systems of equations. From now on, when we have a matrix in reduced row-echelon form, we will mark the leading 1's with a small box. This will help you count, and identify, the pivot columns. In your work, you can box 'em, circle 'em or write 'em in a different color just identify 'em somehow. This device will prove very useful later and is a very good habit to start developing right now.

Solutions for Archetype B diff --git a/src/section-TSS.xml b/src/section-TSS.xml --- a/src/section-TSS.xml +++ b/src/section-TSS.xml @@ -75,7 +75,7 @@ -

The number $r$ is the single most important piece of information we can get from the reduced row-echelon form of a matrix. It is defined as the number of nonzero rows, but since each nonzero row has a leading 1, it is also the number of leading 1's present. For each leading 1, we have a pivot column, so $r$ is also the number of pivot columns. Repeating ourselves, $r$ is the number of nonzero rows, the number of leading 1's and the number of pivot columns. Across different situations, each of these interpretations of the meaning of $r$ will be useful.

+

The number $r$ is the single most important piece of information we can get from the reduced row-echelon form of a matrix. It is defined as the number of nonzero rows, but since each nonzero row has a leading 1, it is also the number of leading 1's present. For each leading 1, we have a pivot column, so $r$ is also the number of pivot columns. Repeating ourselves, $r$ is the number of nonzero rows, the number of leading 1's and the number of pivot columns. Across different situations, each of these interpretations of the meaning of $r$ will be useful, though it may be most helpful to think in terms of pivot columns.

Before proving some theorems about the possibilities for solution sets to systems of equations, let's analyze one particular system with an infinite solution set very carefully as an example. We'll use this technique frequently, and shortly we'll refine it slightly.

@@ -97,7 +97,7 @@ -Let $i$ denote one of the $r=3$ non-zero rows, and then we see that we can solve the corresponding equation represented by this row for the variable $x_{d_i}$ and write it as a linear function of the variables $x_{f_1},\,x_{f_2},\,x_{f_3},\,x_{f_4}$ (notice that $f_5=8$ does not reference a variable). We'll do this now, but you can already see how the subscripts upon subscripts takes some getting used to. +Let $i$ denote any one of the $r=3$ non-zero rows. Then the index $d_i$ is a pivot column. It will be easy in this case to use the equation represented by row $i$ to write an expression for the variable $x_{d_i}$. It will be a linear function of the variables $x_{f_1},\,x_{f_2},\,x_{f_3},\,x_{f_4}$ (notice that $f_5=8$ does not reference a variable, but does tell us the final column is not a pivot column). We will now construct these three expressions. Notice that using subscripts upon subscripts takes some getting used to. @@ -137,7 +137,7 @@ Independent and Dependent Variables -

Suppose $A$ is the augmented matrix of a consistent system of linear equations and $B$ is a row-equivalent matrix in reduced row-echelon form. Suppose $j$ is the index of a column of $B$ that contains the leading 1 for some row ( column $j$ is a pivot column). Then the variable $x_j$ is dependent. A variable that is not dependent is called independent or free.

+

Suppose $A$ is the augmented matrix of a consistent system of linear equations and $B$ is a row-equivalent matrix in reduced row-echelon form. Suppose $j$ is the index of a pivot column of $B$. Then the variable $x_j$ is dependent. A variable that is not dependent is called independent or free.

@@ -166,7 +166,7 @@

-

There are leading 1's in columns 1, 3 and 4, so $D=\set{1,\,3,\,4}$. From this we know that the variables $x_1$, $x_3$ and $x_4$ will be dependent variables, and each of the $r=3$ nonzero rows of the row-reduced matrix will yield an expression for one of these three variables. The set $F$ is all the remaining column indices, $F=\set{2,\,5,\,6}$. The column index $6$ in $F$ means that the final column is not a pivot column, and thus the system is consistent (). The remaining indices in $F$ correspond to free variables, so $x_2$ and $x_5$ (the remaining variables) are our free variables. The resulting three equations that describe our solution set are then, +

Columns 1, 3 and 4 ae pivot columns, so $D=\set{1,\,3,\,4}$. From this we know that the variables $x_1$, $x_3$ and $x_4$ will be dependent variables, and each of the $r=3$ nonzero rows of the row-reduced matrix will yield an expression for one of these three variables. The set $F$ is all the remaining column indices, $F=\set{2,\,5,\,6}$. The column index $6$ in $F$ means that the final column is not a pivot column, and thus the system is consistent (). The remaining indices in $F$ correspond to free variables, so $x_2$ and $x_5$ (the remaining variables) are our free variables. The resulting three equations that describe our solution set are then, @@ -245,16 +245,16 @@ Recognizing Consistency of a Linear System -

Suppose $A$ is the augmented matrix of a system of linear equations with $n$ variables. Suppose also that $B$ is a row-equivalent matrix in reduced row-echelon form with $r$ nonzero rows. Then the system of equations is inconsistent if and only if the leading 1 of row $r$ is located in column $n+1$ of $B$.

+

Suppose $A$ is the augmented matrix of a system of linear equations with $n$ variables. Suppose also that $B$ is a row-equivalent matrix in reduced row-echelon form with $r$ nonzero rows. Then the system of equations is inconsistent if and only if column $n+1$ of $B$ is a pivot column.

-

The first half of the proof begins with the assumption that the leading 1 of row $r$ is located in column $n+1$ of $B$. Then row $r$ of $B$ begins with $n$ consecutive zeros, finishing with the leading 1. This is a representation of the equation $0=1$, which is false. Since this equation is false for any collection of values we might choose for the variables, there are no solutions for the system of equations, and it is inconsistent.

+

The first half of the proof begins with the assumption that column $n+1$ of $B$ is a pivot column. Then the leading 1 of row $r$ is located in column $n+1$ of $B$ and so row $r$ of $B$ begins with $n$ consecutive zeros, finishing with the leading 1. This is a representation of the equation $0=1$, which is false. Since this equation is false for any collection of values we might choose for the variables, there are no solutions for the system of equations, and the system is inconsistent.

-

For the second half of the proof, we wish to show that if we assume the system is inconsistent, then the final leading 1 is located in the last column. But instead of proving this directly, we will form the logically equivalent statement that is the contrapositive, and prove that instead (see ). Turning the implication around, and negating each portion, we arrive at the logically equivalent statement: If the leading 1 of row $r$ is not in column $n+1$, then the system of equations is consistent.

+

For the second half of the proof, we wish to show that if we assume the system is inconsistent, then column $n+1$ of $B$ is a pivot column. But instead of proving this directly, we will form the logically equivalent statement that is the contrapositive, and prove that instead (see ). Turning the implication around, and negating each portion, we arrive at the logically equivalent statement: if column $n+1$ of $B$ is not a pivot column, then the system of equations is consistent.

-

If the leading 1 for row $r$ is located somewhere in columns 1 through $n$, then every preceding row's leading 1 is also located in columns 1 through $n$. In other words, since the last leading 1 is not in the last column, no leading 1 for any row is in the last column, due to the echelon layout of the leading 1's (). We will now construct a solution to the system by setting each dependent variable to the entry of the final column for the row with the corresponding leading 1, and setting each free variable to zero. That sentence is pretty vague, so let's be more precise. Using our notation for the sets $D$ and $F$ from the reduced row-echelon form (): +

If column $n+1$ of $B$ is not a pivot column, the leading 1 for row $r$ is located somewhere in columns 1 through $n$. Then every preceding row's leading 1 is also located in columns 1 through $n$. In other words, since the last leading 1 is not in the last column, no leading 1 for any row is in the last column, due to the echelon layout of the leading 1's (). We will now construct a solution to the system by setting each dependent variable to the entry of the final column for the row with the corresponding leading 1, and setting each free variable to zero. That sentence is pretty vague, so let's be more precise. Using our notation for the sets $D$ and $F$ from the reduced row-echelon form (): @@ -294,7 +294,7 @@ -We can look at the reduced row-echelon form of the augmented matrix and see a leading one in the final column, so we know the system is inconsistent. However, we could just as easily not form the reduced row-echelon form and just look at the list of pivot columns computed by aug.pivots(). Since aug has 5 columns, the final column is numbered 4, which is present in the list of pivot columns, as we expect.

+We can look at the reduced row-echelon form of the augmented matrix and see a pivot column in the final column, so we know the system is inconsistent. However, we could just as easily not form the reduced row-echelon form and just look at the list of pivot columns computed by aug.pivots(). Since aug has 5 columns, the final column is numbered 4, which is present in the list of pivot columns, as we expect.

One feature of Sage is that we can easily extend its capabilities by defining new commands. Here will create a function that checks if an augmented matrix represents a consistent system of equations. The syntax is just a bit complicated. lambda is the word that indicates we are making a new function, the input is temporarily named A (think Augmented), and the name of the function is consistent. Everything following the colon will be evaluated and reported back as the output. consistent = lambda A: not(A.ncols()-1 in A.pivots()) @@ -344,21 +344,16 @@ Consistent Systems, $r$ and $n$ -

Suppose $A$ is the augmented matrix of a consistent system of linear equations with $n$ variables. Suppose also that $B$ is a row-equivalent matrix in reduced row-echelon form with $r$ rows that are not zero rows. Then $r\leq n$. If $r=n$, then the system has a unique solution, - -then the system has infinitely many solutions.

+

Suppose $A$ is the augmented matrix of a consistent system of linear equations with $n$ variables. Suppose also that $B$ is a row-equivalent matrix in reduced row-echelon form with $r$ pivot columns. Then $r\leq n$. If $r=n$, then the system has a unique solution, and if $rn$, then the system has infinitely many solutions.

This theorem contains three implications that we must establish. Notice first that $B$ has $n+1$ columns, so there can be at most $n+1$ pivot columns, $r\leq n+1$. If $r=n+1$, then every column of $B$ is a pivot column, and in particular, the last column is a pivot column. So tells us that the system is inconsistent, contrary to our hypothesis. We are left with $r\leq n$.

-

When $r=n$, we find $n-r=0$ free variables ( $F=\set{n+1}$) and any solution must equal the unique solution given by the first $n$ entries of column $n+1$ of $B$.

+

When $r=n$, we find $n-r=0$ free variables ( $F=\set{n+1}$) and the only solution is given by setting the $n$ variables to the the first $n$ entries of column $n+1$ of $B$.

-

- -we have $n-r>0$ free variables, -corresponding to columns of $B$ without a leading 1, excepting the final column, which also does not contain a leading 1 by . By varying the values of the free variables suitably, we can demonstrate infinitely many solutions.

+

When $rn$, we have $n-r>0$ free variables. Choose one free variable and set all the other free variables to zero. Now, set the chosen free variable to any fixed value. It is possible to then determine the values of the dependent variables to create a solution to the system. By setting the chosen free variable to different values, in this manner we can create infinitely many solutions.

@@ -425,9 +420,9 @@ \path[->] (m-1-3) edge[thick] node[left,xshift=-1em, yshift=0.5em] - + (m-1-3) edge[thick] node[right,xshift=1em, yshift=0.5em] - + % (m-2-2) edge[thick] (m-3-2) @@ -569,7 +564,7 @@ \end{bmatrix}.
-For this system, we have $n = 4$ and $r = 3$. However, with a leading 1 in the last column we see that the original system has no solution by . +For this system, we have $n = 4$ and $r = 3$. However, with a pivot column in the last column we see that the original system has no solution by . @@ -625,7 +620,7 @@ \end{bmatrix}. -For this system, we have $n = 4$ and $r = 3$. However, with a leading 1 in the last column we see that the original system has no solution by . +For this system, we have $n = 4$ and $r = 3$. However, with a pivot column in the last column we see that the original system has no solution by . @@ -745,7 +740,7 @@ \end{bmatrix}. -For this system, we have $n = 3$ and $r = 3$. However, with a leading 1 in the last column we see that the original system has no solution by . +For this system, we have $n = 3$ and $r = 3$. However, with a pivot column in the last column we see that the original system has no solution by .