MAT 119 FALL 2001
MAT 119
FINITE MATHEMATICS
NOTES
PART 1 – LINEAR ALGEBRA
CHAPTER 2
SYSTEMS OF LINEAR EQUATIONS; MATRICES
2.1Systems of linear equations; Substitution; Elimination
Two or more linear equations considered simultaneously form a system of linear equations
Eg: system in two variables
Solution to the system is the point where the two lines intersect (points with coordinates that satisfy both equations).
A system of equations is consistent if it has at least one solution; otherwise it is inconsistent.
If the two lines are parallel,
lines never intersect,
no solution,
system inconsistent
If the two lines intersect,
Lines intersect,
One solution
System consistent and equations independent
If lines are coincident,
Infinitely many solutions
System consistent and equations are dependent
Steps for solving a system of equations by Substitution
1.Pick one of the equations and solve for one of the variables in terms of the remaining variables.
2.Substitute the result in the remaining equations.
3.If one equation in one variable results, solve this equation. Otherwise, repeat steps 1 and 2 until a single equation with one variable remains.
4.Find the values of the remaining variables by back-substitution.
5.Check the solution found.
Rules for obtaining an equivalent system of equations
1.Interchange any two equations in the system.
2.Multiply/divide each side of an equation by the same non-zero constant.
3.Replace any equation in the system by the sum/difference off that equation and any other equation in the system.
Steps for solving a system of equations by Elimination
1.Select two equations from the system and eliminate a variable from them.
2.If there are additional equations in the system, pair of equations and eliminate the same variable from them.
3.Continue steps 1 and 2 on successive systems until one equation containing one variable remains.
4.Solve for this variable and back-substitute in previous equations until all the variables have been found.
2.2Systems of Linear Equations; Matrix Method
matrix – rectangular array of numbers enclosed in brackets
- the numbers are entries of the matrix
- its size is denoted by r x c where r is # of rows and c is # of columns
- includes coefficients of variables with same variables in same column
2x - 3y = 5
x – y = 3
Augmented matrix – matrix including the coefficients and the constants
Row operations
1.Interchange any two rows.
2.Replace any row by a nonzero constant multiple of that row.
3.Replace any row by the sum of that row and a constant multiple of some other row.
Steps for solving a system of linear equations using matrices
1.Write the augmented matrix that represents the system.
2.Perform row operations that place the entry 1 in row 1, column 1.
3.Perform row operations that leave the entry 1 in row 1, column 1 unchanged while causing 0’s to appear below it in column 1.
4.Perform row operations that place the entry 1 in row 2, column 2 and leave the entries in the columns to the left unchanged. If it is impossible to place a 1 in row 2, column 2, then proceed to place a 1 in row 2, column 3. Once a 1 is in place, perform row operations to place 0’s under it.
5.Repeat step 4, placing a 1 in the next row, but one column to the right. Continue until the bottom row or vertical bar is reached.
6.If any rows are obtained that contain only 0’s on the left side of the vertical bar, then place such rows to the bottom of the matrix.
Row-echelon form – form of the remaining matrix after the 6 steps are performed.
Conditions for the row-echelon form of a matrix
1.The entry in row 1, column 1 is a 1, and 0’s appear below it.
2.The first nonzero entry in each row after the first row is a 1, 0’s appear below it, and it appears to the right of the first nonzero entry in any row above.
3.Any rows that contain all 0’s to the left off the vertical bar appear at the bottom.
Reduced row-echelon form – using row operations to continue beyond row-echelon form to make 0’s appear also above all the 1’s in each column. The section of the augmented matrix to the left of the vertical bar is similar to an identity matrix.
Here, the solutions can be picked out without back substitution as in the row-echelon form.
x = 5 and y = 3
For a system with 2 equations in 2 variables, one of the following forms may result after getting the matrix in row-echelon form.
Unique solution -
Infinite number of solutions -
No solution - where d 0.
2.3Systems of m linear equations containing n variables x1, …, xn
where aij and bi are real numbers, i = 1, 2, …, m, j = 1, 2, …, n
Solution to this system: (x1, x2, …, xn)
Conditions for the reduced row-echelon form of a matrix
1.The first nonzero entry in each row is 1 and have only 0’s above and below.
2.The left most 1 in any row is to the right of the left most 1 in the row above.
3.Any rows that contain all 0’s to the left of the vertical bar appear at the bottom.
Steps for solving a system of m linear equations in n variables
1.Write the augmented matrix
2.Find the reduced row-echelon form of the matrix
3.Analyze the matrix to determine if the system has no solution, one solution, or infinitely many solutions.
2.4Matrix Algebra
The dimension of a matrix A is determined by the number of rows and the number of columns of the matrix.
Matrix Am rows, n columnsthe dimension of A is m x n (m by n)
If a matrix has the same number of rows as it has columns, it is a square matrix.
Row matrix (row vector) – has 1 row
Column matrix (column vector) – has 1 column
Matrices A and B are equal if
- they have same dimension
- corresponding entries are equal
Addition of matrices – matrices having the same dimensions can be added by adding corresponding entries.
A = [aij] and B = [bij] A + B = [aij + bij]
Commutative property for addition of matrices
A + B = B + A
Associative property for addition of matrices
A + (B + C) = (A + B) + C
Zero matrix – matrix with all entries being 0’s.
Additive inverse property
For any matrix A,A + (-A) = 0
where –A is the additive inverse of A and all its entries have opposite signs from their corresponding entries in A.
Subtraction of matrices – we can take the difference between two matrices having the same dimensions by taking the difference between corresponding entries.
A = [aij] and B = [bij]A - B = [aij - bij]
A – B = A + (-1)B = A + (-B)
Scalar multiplication of matrices – every entry is multiplied by the scalar value.
For A = [aij],cA = [caij]
Properties of scalar multiplication
For real k and h, A and B are two m x n matrices;
1.k(hA) = (kh)A
2.(k+h)A = kA + hA
3.k(A + B) = kA + kB
2.5Multiplication of Matrices
Matrix multiplication
Let A = [aij] be a matrix of dimension m x r and
let B = [bij] be a matrix of dimension r x n. (# of columns in A must = # of rows in B)
The product A . B is the matrix of dimension m x n, whose ijth entry is the sum of the products of corresponding elements of the ith row of A and the jth column of B.
ie. the ijth entry of A . B is:ai1b1j + ai2b2j + ai3b3j + … + airbrj
a 1 x n row matrix times a n x 1 column matrix gives a 1 x 1 matrix
an n x 1 column matrix times a 1 x n row matrix gives an n x n matrix
Matrix multiplication is not always commutative
Multiplication of matrices is associative
Let A be an m x r matrix, B an r x p matrix, and C a p x n.
A(BC) = (AB)C has dimension m x n.
Distributive Property of Matrices
Let A be an m x r matrix. B and C are r x n matrices. Then
A(B + C) = AB + AC has dimension m x n.
If A is a square matrix of dimension n x n, then AIn = InA = A
where In is an n x n identity matrix (1 in each diagonal and 0’s every where else)
eg. I2 = In =
Identity property of matrices
If A is an m x n matrix, In is the n x n identity matrix, and Im is the m x m identity matrix, then
ImA = Aand AIn = A
2.6Inverse of a Matrix (has to be square)
Let A be an n x n matrix. An n x n matrix B is the inverse of A if AB = BA = In. The inverse of A is denoted as A-1.
Finding the inverse of a matrix
1.Write the augmented matrix [A|In]
2.Use row operations to [A|In] in reduce row-echelon form.
3.If the resulting matrix is of form [In|B], then B is the inverse of A.
A system of linear equations in n variables
AX = B
for which A is a square matrix and A-1 exists, always has a unique solution that is given by
X = A-1B
2.7Applications: Leontief Model; Cryptography; Accounting; The Method of Least Squares
Application 2: Cryptography
Encoding/decoding includes rules known to the people who should have access, otherwise, it is not known by a general audience.
Encoding a message using matrices
- have a reference
- group symbols
- multiply by a matrix that has an inverse
Decode a message using matrices
- do reverse process
- multiply by the inverse of the above matrix
1
DOUGLAS A. WILLIAMS, ARIZONA STATE UNIVERSITY, DEPARTMENT OF MATHEMATICS