There are two important matrices associated with a linear system. The coefficient matrix contains the coefficients of the variables, and the augmented matrix is the coefficient matrix augmented by an extra column containing the constant terms.
Example:
Given the system:
\begin{array}{ccccccc} 3x & + & 2y & - & z & = & 1 \\ x & + & y & & & = & -1 \\ 2x &+ & & & 3z & = & 2 \end{array}
the coefficient matrix is
\left[ \begin{array}{ccc} 3 & 2 & -1 \\ 1 & 1 & 0 \\ 2& 0 & 3 \end{array} \right ]
and the augmented matrix is
\left[ \begin{array}{cccc} 3 & 2 & -1 & 1\\ 1 & 1 & 0 & -1 \\ 2& 0 & 3 & 2 \end{array} \right ] .
Notice that if any variable is missing from an equation in the linear system, then we take this to mean it has coefficient zero. If we denote the coefficient matrix by A and the column vector of constant terms by \vec{b}, then the form of the augmented matrix is \left[A | \vec{b} \right].
In solving a linear system, it will not always be possible to reduce the coefficient matrix to a triangular form as in most of our previous examples. However, we can always achieve a staircase pattern in the nonzero entries of the final matrix.
A matrix is in row echelon form if it satisfies the following properties:
1. Any rows consisting entirely of zeros are at the bottom.
2. In each nonzero row, the first nonzero entry (called the leading entry) is in a column to the left of any leading entries below it.
Note that these properties guarantee that the leading entries form a staircase pattern. In particular, in any column containing a leading entry, all entries below the leading entry are zero.
Example:
\left[ \begin{array}{ccccc}1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 \end{array}\right], \left[ \begin{array}{ccc}1 & 0 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 5\end{array}\right]
What would the corresponding systems of equations be? There solutions?
We now describe the procedure by which any matrix can be reduced to a matrix in row echelon form. The allowable operations, called elementary row operations, correspond to the operations that can be performed on a system of linear equations to transform it into an equivalent system.
The following elementary row operations can be performed on a matrix:
1. Interchange two rows
2. Multiply a row by a nonzero constant
3. Add a multiple of a row to another row
We will use the following shorthand notation for the three elementary row operations:
1. R_i \leftrightarrow R_j means interchange rows i and j
2. kR_i means multiply row i by k
3. R_i +kR_j means add k times row j to row i (and replace row i with the result).
The process of applying elementary row operations to bring a matrix into row echelon form, called row reduction, is used to reduce a matrix to echelon form.
Exercise:
Row reduce the following matrix \left[ \begin{array}{ccccc}1 & 2 & 3 & 4 & 5\\ 1 & 1 & 2 & 3 & 2\\ -1 & 0 & 0 & 1 & 2\\ 2 & 1 & 0 & -1 & -2 \end{array}\right]
After a bit of work, you should be able to get the following matrix:
|
Is the row echelon form of a matrix unique?
Matrices A and B are row equivalent if there is a sequence of elementary row operations that converts A into B.
Matrices A and B are row equivalent if and only if they can be reduced to the same row echelon form.
When row reduction is applied to the augmented matrix of a system of linear equations, we create an equivalent system that can be solved by back substitution. The entire process is known as Gaussian elimination.
1. Write the augmented matrix of the system of linear equations.
2. Use elementary row operations to reduce the augmented matrix to row echelon form.
3. Using back substitution, solve the equivalent system that corresponds to the row-reduced matrix.
Remark: When performed by hand, step 2 of Gaussian elimination allows quite a bit of choice. Here are some useful guidelines:
(a) Locate the leftmost column that is not all zeros.
(b) Create a leading entry at the top of this column (1 is a good choice).
(c) Use the leading entry to create zeros below it.
(d) Cover up the row containing the leading entry, and go back to step (a) to repeat the procedure on the remaining submatrix. Stop when the entire matrix is in row echelon form.
Example:
Use Gaussian Elimination to find a solution to \begin{array}{ccccccc} 3x & + & 2y & - & z & = & 1 \\ x & + & y & & & = & -1 \\ 2x &+ & & & 3z & = & 2 \end{array}
|
|
Example:
Solve the system
\begin{array}{ccccccccc} w&-&x&-&y&+&2z&=&1 \\ w&-&x&-&2y&+&z&=&3\\w&-&x&+&y& & &=&1\end{array}
|
In this case the associated system has infinitely many solutions. There is more than one way to assign parameters, but we will proceed to use back substitution, writing the variables corresponding to the leading entries (the leading variables) in terms of the other variables (the free variables).
\begin{array}{ccccccccc} w&-&x& & &+&3z&=&-1\\ &&&&y&+&z&=&-2\\ &&&&&&z&=&-1\end{array}
In this case, the leading variables are w, y, and z, and the free variable is x. Using back substitution,
z = -1, y = -z-2 = -1, and w = x - z -1 = x.
Exercise: If we assign paramters x = s, write down the solution in vector form.
|
|
This example highlights a very important property: In a consistent system, the free variables are just the variables that are not leading variables. The number of leading variables is the number of nonzero rows in the row echelon form of the coefficient matrix. Thus we know the number of free variables (parameters) before we find the solution. We will later prove that the number of nonzero rows in the echelon form is unique (even though the echelon form is not). Since this also matches with our concept of parameters, we now have something closely tied with dimension:
The rank of a matrix is the number of nonzero rows in its row echelon form.
We denote the rank of a matrix A by rank(A).
Let A by the coefficient matrix of a system of linear equations with n variables. If the system is consistent, then
number of free variables = n - rank(A).
A modification of Gaussian elimination greatly simplifies the back substitution phase and is particularly helpful when there are infinitely many solutions. This variant is known as Gauss-Jordan elimination, and it relies on reducing the matrix even further:
A matrix is in reduced row echelon form if it satisfies the following properties:
1. It is in row echelon form
2. The leading entry in each nonzero row is a 1 (called a leading 1)
3. Each column containing a leading 1 has zeros everywhere else.
Exercise:
For 2 \times 2 matrices, what are all possible row echelon forms?
What are all possible reduced row echelon forms?
Is a matrix in reduced row echelon form unique?
1. Write the augmented matrix of the system of linear equations
2. Use elementary row operations to reduce the augmented matrix to reduced row echelon form
3. If the resulting system is consistent, solve for the leading variables in terms of any remaining free variables.
Example:
Find the line of the intersection of the planes x + y + z = 1 and 2x + y -z = 3
|
This gives us the system x -2z = 2 and y +3z = -1. We set the free variable z = t and thus get parametric equations for the line which is the intersection of the two planes: x = 2-2t, y = -3t-1, z = t.
What is this in vector form?
Now lets look at lines in \mathbb{R}^3. Let
P = \left[\begin{array} \\1 \\ 0\\ 0 \end{array} \right], Q = \left[\begin{array}\\ 1 \\ 2\\ 2 \end{array} \right], U = \left[\begin{array}\\ 0 \\ 2\\ 2 \end{array} \right], and V = \left[\begin{array}\\ 2 \\ 3\\ -1 \end{array} \right].
Determine if the lines \vec{x} = P+tU and \vec{x} = Q+sV.
Note: I'm using s as the parameter in the second line because when s = t this doesn't necessarily give us a solution on both lines.
If the lines intersect, we want to find \vec{x} = \left[\begin{array}\\ x \\ y\\ z \end{array} \right] which satisfies both equations simultaneously. So we have
1 = x = 1+2s, 2t = y = 2+3s, and 2t = z = 2-s.
Solving for s in the first equation gives s = 0, and then we find that t = 1.
Thus [1,2,2] is a solution.
|
|
In \mathbb{R}^3, given two lines, what are the possible solution sets?
We have seen that every system of equations has either no solution, a unique solution, or infinitely many solutions. However, there is one type of system that always has at least one solution.
A system of linear equations is called homogeneous if the constant term in each equation is zero.
In otherwords, a homogeneous system has an augmented matrix of the form [ A|0].
Example:
2x + 3y +4z + 5w = 0, x + y + z + w = 0, x + 3w = 0.
In a homogeneous system, what solution do we always have?
If [A|0] is a homogeneous system of m linear equations with n variables, where m< n, then the system has infinitely many solutions.
Exercise: Give a proof using the Rank Theorem.
Exercise: What happens when n > m?
So far, all our examples have been in \mathbb{R}^n. However, we have also seen how other number systems arise, notably \mathbb{Z}_p. When p is a prime number, \mathbb{Z}_p behaves in many respects, like \mathbb{R}. We can add, subtract, multiply, and divide (by nonzero numbers). This is all that is required to solve systems of linear equations when the variables and coefficients belong to \mathbb{Z}_p. In such instances, we refer to solving a system over \mathbb{Z}_p.
Example: Take x + y + z = 1 viewed as an equation over \mathbb{Z}_2. Then this equation has exactly four solutions:
\vec{x} = \left[ \begin{array} \\ x \\ y \\ z \end{array}\right] = \left[ \begin{array} \\ 1 \\ 0 \\ 0 \end{array}\right], \vec{x} = \left[ \begin{array} \\ 0 \\ 1 \\ 0\end{array}\right],\vec{x} = \left[ \begin{array} \\ 0 \\ 0 \\ 1 \end{array}\right], and \vec{x} = \left[ \begin{array} \\ 1\\ 1 \\ 1 \end{array}\right].
What are the solutions to x + z = 0 over \mathbb{Z}_3?
We don't need to use trial-and-error methods; row reduction of augmented matrices works just as well over \mathbb{Z}_p as over \mathbb{R}.
Example: Solve the following system over \mathbb{Z}_5.
x + 2y + 3z = 4, x + y + z = 1, x + z = 2.
(solve on the board).
Exercise: Solve the following system over \mathbb{Z}_2.
x + y + z + w = 1, x + y = 1, y + z = 0, z +w = 0, x + w = 1.
Remark: For linear systems over \mathbb{Z}_p, there can never be infinitely many solutions. (Why not?) Rather, when there is more than one solution, the number of solutions is finite and is a function of the number of free variables and p.
|
|
|
|
|
|